結果
問題 | No.1761 Sequence Distance |
ユーザー |
![]() |
提出日時 | 2021-11-20 16:52:32 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 780 ms / 8,000 ms |
コード長 | 2,905 bytes |
コンパイル時間 | 15,679 ms |
コンパイル使用メモリ | 228,232 KB |
最終ジャッジ日時 | 2025-01-25 22:03:37 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#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; }