結果
問題 |
No.1964 sum = length
|
ユーザー |
![]() |
提出日時 | 2023-03-07 08:35:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 542 ms / 2,000 ms |
コード長 | 1,290 bytes |
コンパイル時間 | 4,060 ms |
コンパイル使用メモリ | 251,772 KB |
最終ジャッジ日時 | 2025-02-11 06:08:22 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll=int; using ld=long double; ld pie=3.14159265359; ll inf=1001; ll mod=998244353; ll dp[200][501][501]; int main(){ ll n; cin >> n; ll ans=0; for (ll i = 1; i < 10; i++) { dp[0][i][1]=1; } for (ll i = 10; i <100; i++) { dp[0][i][2]=1; } for (ll i = 100; i < 500; i++) { dp[0][i][3]=1; } for (ll i = 1; i < n; i++) { for (ll j = 0; j < 500; j++) { for (ll k = 0; k < 500; k++) { if (dp[i-1][j][k]==0) { continue; } if (k+2>500) { continue; } for (ll l = 1; l < 10&&l+j<500; l++) { dp[i][j+l][k+2]+=dp[i-1][j][k]; if (dp[i][j+l][k+2]>mod) { dp[i][j+l][k+2]-=mod; } } if (k+3>500) { continue; } for (ll l = 10; l < 100&&l+j<500; l++) { dp[i][j+l][k+3]+=dp[i-1][j][k]; if (dp[i][j+l][k+3]>mod) { dp[i][j+l][k+3]-=mod; } } if (k+4>500) { continue; } for (ll l = 100; l < 500&&l+j<500; l++) { dp[i][j+l][k+4]+=dp[i-1][j][k]; if (dp[i][j+l][k+4]>mod) { dp[i][j+l][k+4]-=mod; } } } } } for (ll i = 0; i < 500; i++) { ans+=dp[n-1][i][i]; ans%=mod; } cout << ans << endl; }