CSES Array Description
// compile: make data
// run: ./data < data.in
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) _debug_print(#x, x);
#define Debug(x...) _debug_print_format(#x, x);
std::ifstream terminal("/dev/tty");
#define PP cerr<<"\033[1;30mpause...\e[0m",terminal.ignore();
#else
#define debug(x...)
#define Debug(x...)
#define PP
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define VI vector<int>
#define VII vector<vector<int>>
#define VIII vector<vector<vector<int>>>
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define FIND(a, x) ((find(a.begin(),a.end(),(x))!=a.end())?1:0)
#define cmin(x,...) x=min({(x), __VA_ARGS__})
#define cmax(x,...) x=max({(x), __VA_ARGS__})
#define INTMAX (int)(9223372036854775807)
#define INF (int)(1152921504606846976)
#define NaN (int)(0x8b88e1d0595d51d1)
#define double long double
#define int long long
#define uint unsigned long long
#define MAXN 200010
#define P 1000000007

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, ub; cin >> n >> ub;
    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];
    vector<vector<int>> dp(n, vector<int>(ub+1, 0));
    if (a[0]) dp[0][a[0]] = 1;
    else fill(dp[0].begin()+1, dp[0].end(), 1);
    rep(i, 1, n) {
        if (a[i]) {
            for (int k = a[i]-1; k <= a[i]+1; ++k) {
                if (k >= 1 && k <= ub) {
                    dp[i][a[i]] += dp[i-1][k];
                    dp[i][a[i]] %= P;
                }
            }
        }
        else {
            rep(j, 1, ub+1) {
                for (int k = j-1; k <= j+1; ++k) {
                    if (k >= 1 && k <= ub) {
                        dp[i][j] += dp[i-1][k];
                        dp[i][j] %= P;
                    }
                }
            }
        }
    }
    int ans;
    if (a[n-1]) ans = dp[n-1][a[n-1]];
    else ans = accumulate(dp[n-1].begin()+1, dp[n-1].end(), 0LL) % P;
    cout << ans << endl;

    return 0;
}

Comments

  1. 4 weeks ago
    2026-8-24 5:41:02

    [190]555win12 – Nhà Cái Casino Uy Tín Số 1 | Đăng Nhập & Tải App 555win12,555win12 là nhà cái casino uy tín số 1 hiện nay, cung cấp các trò chơi trực tuyến hấp dẫn với tỷ lệ thưởng cao. Truy cập 555win12 để đăng nhập, tải app nhanh chóng và trải nghiệm không gian cá cược chuyên nghiệp, bảo mật và minh bạch nhất. visit: 555win12

Send Comment Edit Comment


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
Previous
Next