結果

問題 No.2867 NOT FOUND 404 Again
コンテスト
ユーザー Shirotsume
提出日時 2024-08-30 21:57:01
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,575 bytes
コンパイル時間 1,059 ms
コンパイル使用メモリ 95,776 KB
実行使用メモリ 12,368 KB
最終ジャッジ日時 2024-08-30 21:57:07
合計ジャッジ時間 5,893 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 TLE * 1 -- * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:8:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    8 | const int INF = 1e18;
      |                 ^~~~

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MOD = 998244353;
const int INF = 1e18;

int main() {
    string N;
    cin >> N;
    int n = N.size();
    
    // Initialize dp arrays
    vector<vector<long long>> dp(2, vector<long long>(100, 0));
    dp[0][0] = 1;

    for (int i = 0; i < n; ++i) {
        vector<vector<long long>> edp(2, vector<long long>(100, 0));
        int ni = N[i] - '0'; // Convert char to int
        
        for (int j = 0; j < 100; ++j) {
            int to = 10 * j;
            
            // Loop for dp[0]
            for (int k = 0; k <= ni; ++k) {
                if (to + k != 404) {
                    int nx = (to + k) % 100;
                    if (k < ni) {
                        edp[1][nx] += dp[0][j];
                        edp[1][nx] %= MOD;
                    } else if (k == ni) {
                        edp[0][nx] += dp[0][j];
                        edp[0][nx] %= MOD;
                    }
                }
            }
            
            // Loop for dp[1]
            for (int k = 0; k < 10; ++k) {
                if (to + k != 404) {
                    int nx = (to + k) % 100;
                    edp[1][nx] += dp[1][j];
                    edp[1][nx] %= MOD;
                }
            }
        }
        dp = edp;
    }

    long long ans = 0;
    for (int i = 0; i < 100; ++i) {
        ans += dp[0][i] + dp[1][i];
        ans %= MOD;
    }
    ans = (ans - 1 + MOD) % MOD; // Ensuring non-negative modulo result

    cout << ans << endl;
    return 0;
}
0