結果
問題 | No.3096 Snake Path |
ユーザー |
![]() |
提出日時 | 2025-04-06 17:22:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 1,782 bytes |
コンパイル時間 | 4,118 ms |
コンパイル使用メモリ | 256,136 KB |
実行使用メモリ | 50,864 KB |
最終ジャッジ日時 | 2025-04-06 17:22:43 |
合計ジャッジ時間 | 6,221 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001LL mint gu(int N,int K){ vector dp(1<<(N*3),vector(N*3,vector(K+1,0))); dp[1][0][0] = 1; rep(i,1<<(N*3)){ rep(j,N*3){ rep(k,K+1){ if(dp[i][j][k]==0)continue; rep(l,N*3){ if((i>>l)&1)continue; int nk = k; if(j/3 == l/3){ if(abs(j%3-l%3)!=1)continue; } else{ if(abs((j/3-l/3))!=1)continue; if((j+l)%6!=5)continue; { if(abs(j-l)!=1)nk++; } } if(nk>K)continue; dp[i|(1<<l)][l][nk] += dp[i][j][k]; } } } } mint ans = 0; rep(i,1<<(N*3)){ rep(j,K+1){ ans += dp[i][N*3-1][j]; } } return ans; } mint dp[1005][2000][3][2]; int main(){ int N,K; cin>>N>>K; //cout<<gu(N,K).val()<<endl; dp[0][0][0][0] = 1; rep(i,N){ rep(j,K+1){ rep(k,3){ rep(l,2){ if(dp[i][j][k][l]==0)continue; { rep(kk,3){ int ni = i+1,nj = j,nk = kk,nl = 0; if(i%2==0 && k!=0)nj++; if(i%2==1 && k!=2)nj++; dp[ni][nj][nk][nl] += dp[i][j][k][l]; } } if(k!=1){ int ni = i+2; int nj = j; int nk = 2-k; int nl = 1; if(i%2==0 && k!=0)nj++; if(i%2==1 && k!=2)nj++; nj+=2; dp[ni][nj][nk][nl] += dp[i][j][k][l]; } if(l==1){ int ni = i+1; int nj = j; int nk = k; int nl = 1; nj+=2; dp[ni][nj][nk][nl] += dp[i][j][k][l]; } } } } } int c; if(N%2==1)c = 2; else c = 0; mint ans = 0; rep(i,K+1){ ans += dp[N][i][c][0] + dp[N][i][c][1]; } cout<<ans.val()<<endl; return 0; }