結果
問題 | No.2302 Carry X Times |
ユーザー |
|
提出日時 | 2023-05-13 16:23:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 1,482 bytes |
コンパイル時間 | 758 ms |
コンパイル使用メモリ | 77,372 KB |
最終ジャッジ日時 | 2025-02-13 00:04:25 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>using namespace std;using ll=long long;#define rep(i,n) for(int i=0;i<n;i++)#define rrep(i,n) for(int i=(n)-1;i>=0;i--)#define all(v) v.begin(),v.end()#define rall(v) v.rbegin(),v.rend()template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;}template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;}const ll MOD=998244353;void solve(){string s;int x;cin>>s>>x;int n=s.size();ll dp[20][20][2][2][2];rep(i,20)rep(j,20)rep(k,2)rep(l,2)rep(m,2)dp[i][j][k][l][m]=0;dp[0][0][0][0][0]=1;reverse(all(s));rep(i,n){rep(j,19){rep(k,2)rep(l,2)rep(m,2){rep(p,10)rep(q,10){int fp=(p>s[i]-'0')||(p==s[i]-'0'&&l);int fq=(q>s[i]-'0')||(q==s[i]-'0'&&m);if(p+q+k>=10){dp[i+1][j+1][1][fp][fq]+=dp[i][j][k][l][m];dp[i+1][j+1][1][fp][fq]%=MOD;}else{dp[i+1][j][0][fp][fq]+=dp[i][j][k][l][m];dp[i+1][j][0][fp][fq]%=MOD;}}}}}ll ans=(dp[n][x][1][0][0]+dp[n][x][0][0][0])%MOD;cout<<ans<<"\n";}int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;cin>>t;while(t--){solve();}}