結果
問題 | No.1964 sum = length |
ユーザー |
![]() |
提出日時 | 2022-04-21 20:27:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 1,111 bytes |
コンパイル時間 | 3,661 ms |
コンパイル使用メモリ | 174,900 KB |
最終ジャッジ日時 | 2025-01-28 19:28:39 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <deque>#include <queue>#include <string>#include <iomanip>#include <set>#include <unordered_set>#include <map>#include <unordered_map>#include <utility>#include <stdio.h>#include <math.h>#include <assert.h>#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endifusing namespace std;using ll=long long;#define read(x) cin>>(x);#define readll(x) ll (x);cin>>(x);#define readS(x) string (x);cin>>(x);#define readvll(x,N) vector<ll> (x)((N));for(int i=0;i<(N);i++){cin>>(x)[i];}int main(){int n;cin>>n;vector<ll> C(2*n);ll a=1;ll digit=0;ll f=10;while(a-digit<=2*n-1){C[a-digit]++;a++;if(a%f==0){digit++;f*=10;}}const ll mod=998244353;vector<vector<ll>> dp(n+1,vector<ll>(2*n));dp[0][0]=1;for(ll i=0;i<n;i++){for(ll j=0;j<2*n;j++){for(ll k=1;k<2*n;k++){if(j+k<2*n){dp[i+1][j+k]+=dp[i][j]*C[k];dp[i+1][j+k]%=mod;}}}}cout<<dp[n][2*n-1]<<endl;return 0;}