結果

問題 No.1847 Good Sequence
コンテスト
ユーザー 👑 potato167
提出日時 2025-04-17 11:13:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,323 bytes
コンパイル時間 2,339 ms
コンパイル使用メモリ 205,080 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-17 11:13:17
合計ジャッジ時間 5,286 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;

// Multiply matrices A and B of size S×S
vector<vector<ll>> mul(const vector<vector<ll>>& A, const vector<vector<ll>>& B) {
    int S = A.size();
    vector<vector<ll>> C(S, vector<ll>(S));
    for(int i = 0; i < S; i++){
        for(int k = 0; k < S; k++){
            if (!A[i][k]) continue;
            ll av = A[i][k];
            for(int j = 0; j < S; j++){
                C[i][j] = (C[i][j] + av * B[k][j]) % MOD;
            }
        }
    }
    return C;
}

// Fast exponentiation of matrix M to power e
vector<vector<ll>> mpow(vector<vector<ll>> M, long long e) {
    int S = M.size();
    vector<vector<ll>> R(S, vector<ll>(S));
    for(int i = 0; i < S; i++) R[i][i] = 1;
    while(e > 0){
        if(e & 1) R = mul(R, M);
        M = mul(M, M);
        e >>= 1;
    }
    return R;
}

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

    long long L;
    int N, M;
    cin >> L >> N >> M;
    vector<int> K(M);
    for(int i = 0; i < M; i++) cin >> K[i];
    // Map each symbol s (1..N) to its forbidden run-length K_s (0 if none)
    vector<int> forb(N+1, 0);
    for(int x : K) forb[x] = x;
    int maxK = 0;
    for(int i = 1; i <= N; i++) maxK = max(maxK, forb[i]);
    int cap = maxK + 1; // ℓ = 1..maxK, and ℓ=cap means ≥maxK+1

    // Build state indices: (s,ℓ) -> idx
    // s from 1..N, ℓ from 1..cap
    int S = N * cap;
    auto idx = [&](int s, int l){ return (s-1)*cap + (l-1); };

    // Build transition matrix T of size S×S
    vector<vector<ll>> T(S, vector<ll>(S, 0));
    for(int s = 1; s <= N; s++){
        int fs = forb[s];
        for(int l = 1; l <= cap; l++){
            int i = idx(s,l);
            // 1) continue same symbol: go to (s, min(l+1, cap))
            int nl = (l < cap ? l+1 : cap);
            T[i][ idx(s,nl) ] = 1;
            // 2) switch to t ≠ s: only if l != fs
            if(l != fs){
                for(int t = 1; t <= N; t++){
                    if(t == s) continue;
                    // start new run length = 1
                    T[i][ idx(t,1) ] = (T[i][ idx(t,1) ] + 1) % MOD;
                }
            }
        }
    }

    // Initial vector v: at length 1, run length = 1 at each symbol
    vector<ll> v(S, 0);
    for(int s = 1; s <= N; s++){
        v[ idx(s,1) ] = 1;
    }
    if(L == 1){
        // Sum over valid end states: ℓ != forbidden for that symbol
        ll ans = 0;
        for(int s = 1; s <= N; s++){
            for(int l = 1; l <= cap; l++){
                if(l == forb[s]) continue;
                ans = (ans + v[idx(s,l)]) % MOD;
            }
        }
        cout << ans << "\n";
        return 0;
    }

    // Compute T^{L-1}
    auto Texp = mpow(T, L-1);

    // Multiply v * Texp -> v2
    vector<ll> v2(S,0);
    for(int j = 0; j < S; j++){
        ll sum = 0;
        for(int i = 0; i < S; i++){
            sum = (sum + v[i] * Texp[i][j]) % MOD;
        }
        v2[j] = sum;
    }

    // Answer = sum of v2 over states (s,l) with l != forb[s]
    ll ans = 0;
    for(int s = 1; s <= N; s++){
        for(int l = 1; l <= cap; l++){
            if(l == forb[s]) continue;
            ans = (ans + v2[idx(s,l)]) % MOD;
        }
    }
    cout << ans << "\n";
    return 0;
}
0