結果

問題 No.3182 recurrence relation’s intersection sum
ユーザー ooaiu
提出日時 2025-07-27 10:30:00
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 468 ms / 2,000 ms
コード長 1,373 bytes
コンパイル時間 3,369 ms
コンパイル使用メモリ 286,304 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-07-27 10:30:13
合計ジャッジ時間 12,471 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:27:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
   27 | main() {
      | ^~~~
main.cpp: In function ‘int main()’:
main.cpp:28:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   28 |     scanf("%ld%ld%ld", &K, &L, &R);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
long K, L, R, i, j, k;
using v = std::vector<mint>;
using vv = std::vector<v>;
#define m(x) vv x(K + 4, v(K + 4))
vv op(vv a, vv b) {
    m(r);
    for (i = 0; i < K + 4; i++)
        for (k = 0; k < K + 4; k++)
            for (j = 0; j < K + 4; j++) {
                r[i][j] += a[i][k] * b[k][j];
            }
    return r;
}
vv pw(vv a, long n) {
    m(r);
    for (i = 0; i < K + 4; i++) r[i][i] = 1;
    while (n) {
        if (n & 1) r = op(r, a);
        a = op(a, a);
        n >>= 1;
    }
    return r;
}
main() {
    scanf("%ld%ld%ld", &K, &L, &R);
    vv A(K + 4, v(K + 4));
    for (i = 0; i <= K; i++) {
        A[i][0] = A[i][i] = 1;
        for (j = 1; j < i; j++) {
            A[i][j] = A[i - 1][j - 1] + A[i - 1][j];
        }
    }
    A[K + 1][K + 1] = K, A[K + 1][K] = A[K + 1][K + 2] = 1;
    A[K + 2][K + 2] = K;
    A[K + 3][K + 3] = 1, A[K + 3][K + 1] = K, A[K + 3][K] = A[K + 3][K + 2] = 1;
    mint ans = 0;
    v B(K + 4);
    B[0] = B[K + 1] = B[K + 2] = B[K + 3] = 1;
    {
        auto RA = pw(A, R);
        for (i = 0; i < K + 4; i++)
            ans += RA[K + 3][i] * B[i];
    }
    if (L - 1 >= 0) {
        auto LA = pw(A, L - 1);
        for (i = 0; i < K + 4; i++)
            ans -= LA[K + 3][i] * B[i];
    }
    printf("%d", ans.val());
}
0