結果
問題 | No.1761 Sequence Distance |
ユーザー | chocorusk |
提出日時 | 2021-11-20 16:52:32 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 663 ms / 8,000 ms |
コード長 | 2,905 bytes |
コンパイル時間 | 3,649 ms |
コンパイル使用メモリ | 188,876 KB |
実行使用メモリ | 19,588 KB |
最終ジャッジ日時 | 2023-09-02 12:13:03 |
合計ジャッジ時間 | 11,612 ms |
ジャッジサーバーID (参考情報) |
judge16 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 8 ms
19,256 KB |
testcase_01 | AC | 8 ms
19,304 KB |
testcase_02 | AC | 169 ms
19,388 KB |
testcase_03 | AC | 8 ms
19,256 KB |
testcase_04 | AC | 9 ms
19,356 KB |
testcase_05 | AC | 8 ms
19,256 KB |
testcase_06 | AC | 9 ms
19,400 KB |
testcase_07 | AC | 8 ms
19,460 KB |
testcase_08 | AC | 10 ms
19,360 KB |
testcase_09 | AC | 9 ms
19,360 KB |
testcase_10 | AC | 10 ms
19,332 KB |
testcase_11 | AC | 10 ms
19,360 KB |
testcase_12 | AC | 9 ms
19,296 KB |
testcase_13 | AC | 9 ms
19,296 KB |
testcase_14 | AC | 9 ms
19,332 KB |
testcase_15 | AC | 10 ms
19,332 KB |
testcase_16 | AC | 10 ms
19,256 KB |
testcase_17 | AC | 9 ms
19,296 KB |
testcase_18 | AC | 10 ms
19,492 KB |
testcase_19 | AC | 10 ms
19,256 KB |
testcase_20 | AC | 9 ms
19,416 KB |
testcase_21 | AC | 129 ms
19,300 KB |
testcase_22 | AC | 16 ms
19,568 KB |
testcase_23 | AC | 528 ms
19,456 KB |
testcase_24 | AC | 163 ms
19,300 KB |
testcase_25 | AC | 435 ms
19,396 KB |
testcase_26 | AC | 474 ms
19,588 KB |
testcase_27 | AC | 160 ms
19,308 KB |
testcase_28 | AC | 135 ms
19,360 KB |
testcase_29 | AC | 388 ms
19,344 KB |
testcase_30 | AC | 78 ms
19,256 KB |
testcase_31 | AC | 209 ms
19,304 KB |
testcase_32 | AC | 21 ms
19,484 KB |
testcase_33 | AC | 263 ms
19,332 KB |
testcase_34 | AC | 9 ms
19,368 KB |
testcase_35 | AC | 38 ms
19,264 KB |
testcase_36 | AC | 342 ms
19,300 KB |
testcase_37 | AC | 49 ms
19,360 KB |
testcase_38 | AC | 78 ms
19,328 KB |
testcase_39 | AC | 192 ms
19,484 KB |
testcase_40 | AC | 72 ms
19,360 KB |
testcase_41 | AC | 586 ms
19,256 KB |
testcase_42 | AC | 658 ms
19,260 KB |
testcase_43 | AC | 663 ms
19,568 KB |
testcase_44 | AC | 8 ms
19,360 KB |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #include <atcoder/all> #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair<int, int> P; using mint=modint998244353; mint f[2000010], invf[2000010]; void fac(int n){ f[0]=1; for(ll i=1; i<=n; i++) f[i]=f[i-1]*i; invf[n]=f[n].inv(); for(ll i=n-1; i>=0; i--) invf[i]=invf[i+1]*(i+1); } mint comb(int x, int y){ if(!(0<=y && y<=x)) return 0; return f[x]*invf[y]*invf[x-y]; } // mint dp[5050][1010]; // mint dp2[5050][1010]; mint dp[33][1010]; int main() { int n,m;cin>>n>>m; dp[0][0]=1; for(int i=0; i<n; i++){ mint ndp[33][1010]; for(int j=0; j*j<=m; j++){ for(int k=0; k<=m; k++){ if(j==0){ ndp[j+1][k]+=dp[j][k]*2; ndp[j][k]+=dp[j][k]*2; }else if(k+j<=m){ ndp[j+1][k+j]+=dp[j][k]; ndp[j-1][k+j]+=dp[j][k]; ndp[j][k+j]+=dp[j][k]*2; } } } for(int j=0; j*j<=m; j++){ for(int k=0; k<=m; k++){ dp[j][k]=ndp[j][k]; } } } cout<<dp[0][m].val()<<endl; // mint dp[55][111][10101]; // dp[0][n][n*n]=1; // for(int i=0; i<n; i++){ // for(int j=n-i; j<=n+i; j++){ // for(int k=n*n-i*i; k<=n*n+i*i; k++){ // dp[i+1][j][k]+=2*dp[i][j][k]; // if(j==n){ // dp[i+1][j+1][k-i]+=2*dp[i][j][k]; // }else if(j>n){ // dp[i+1][j+1][k-i]+=dp[i][j][k]; // dp[i+1][j-1][k+i]+=dp[i][j][k]; // } // } // } // } // cout<<dp[n][n][m+n*n].val()<<endl; // for(int i=0; i<=n; i++){ // for(int j=0; j<=m; j++){ // for(int p=1; p<i; p++){ // for(int q=0; q<=j; q++){ // dp[i][j]+=dp2[p][q]*dp[i-p][j-q]*2; // } // } // for(int x=0; x<=i-2 && x+1<=j; x++){ // dp2[i][j]+=dp[x][j-x-1]*(mint(2).pow(i-x-2)); // if(x+1==j){ // dp2[i][j]+=mint(2).pow(i-2); // } // } // dp[i][j]+=dp2[i][j]; // } // } // mint ans=0; // for(int i=0; i<=n; i++){ // ans+=dp[i][m]*2*mint(2).pow(n-i); // } // cout<<ans.val()<<endl; return 0; }