結果
問題 | No.2302 Carry X Times |
ユーザー | shobonvip |
提出日時 | 2023-05-12 22:21:13 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,876 bytes |
コンパイル時間 | 3,804 ms |
コンパイル使用メモリ | 265,460 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-28 18:49:35 |
合計ジャッジ時間 | 4,583 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; typedef modint998244353 mint; typedef long long ll; mint dp[20][20][4][2]; void solve(){ ll n; int x; cin >> n >> x; // dp[i][j][k][l] : keta i, now kuriagari, now kakutei (4), go kuriagari for (int i=0; i<20; i++){ for (int j=0; j<20; j++){ for (int k=0; k<4; k++){ for (int l=0; l<2; l++){ dp[i][j][k][l] = 0; } } } } string ss = to_string(n); int siz = ss.size(); vector<int> s(siz); for (int i=0; i<siz; i++){ s[i] = ss[i] - '0'; } dp[0][0][0][0] = 1; dp[0][0][0][1] = 1; for (int num=0; num<siz; num++){ for (int mode=0; mode<4; mode++){ int ti = 10; int tj = 10; if ((mode >> 0 & 1) == 0) ti = s[num] + 1; if ((mode >> 1 & 1) == 0) tj = s[num] + 1; for (int i=0; i<ti; i++){ for (int j=0; j<tj; j++){ if (i+j <= 8){ for (int k=0; k<=x; k++){ dp[num+1][k][mode|((int)(s[num]>i)<<0)|((int)(s[num]>j)<<1)][0] += dp[num][k][mode][0]; dp[num+1][k][mode|((int)(s[num]>i)<<0)|((int)(s[num]>j)<<1)][1] += dp[num][k][mode][0]; } }else if (i+j == 9){ for (int k=0; k<=x; k++){ dp[num+1][k][mode|((int)(s[num]>i)<<0)|((int)(s[num]>j)<<1)][0] += dp[num][k][mode][0]; } } if (i+j == 9){ for (int k=0; k<x; k++){ dp[num+1][k+1][mode|((int)(s[num]>i)<<0)|((int)(s[num]>j)<<1)][1] += dp[num][k][mode][1]; } }else if (i+j >= 10){ for (int k=0; k<x; k++){ dp[num+1][k+1][mode|((int)(s[num]>i)<<0)|((int)(s[num]>j)<<1)][0] += dp[num][k][mode][1]; dp[num+1][k+1][mode|((int)(s[num]>i)<<0)|((int)(s[num]>j)<<1)][1] += dp[num][k][mode][1]; } } } } } } mint ans = 0; for (int i=0; i<4; i++){ ans += dp[siz][x][i][0]; } cout << ans.val() << endl; } int main(){ int t; cin >> t; while(t--) solve(); }