結果
問題 | No.2810 Have Another Go (Hard) |
ユーザー |
![]() |
提出日時 | 2024-07-07 15:17:25 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 423 ms / 3,000 ms |
コード長 | 4,520 bytes |
コンパイル時間 | 1,809 ms |
コンパイル使用メモリ | 178,948 KB |
実行使用メモリ | 7,764 KB |
最終ジャッジ日時 | 2024-07-07 15:18:22 |
合計ジャッジ時間 | 16,652 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 61 |
ソースコード
#include<atcoder/modint> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace atcoder; using namespace __gnu_pbds; using mint=modint998244353; int mem=0; mint Q_data[62][7]; gp_hash_table<long long,mint> mp; mint Bostan_Mori(long long N){ if(mp.find(N)!=mp.end()){ return mp[N]; } if(N==0){ mint ans=1; mp[N]=ans; return ans; } if(N<=6){ mint ans=mint(2).pow(N-1); mp[N]=ans; return ans; } long long M=N; mint Q[7]; if(mem>0){ copy(begin(Q_data[0]),end(Q_data[0]),begin(Q)); } if(mem==0){ Q[0]=1; for(int i=1;i<=6;i++){ Q[i]=-1; } copy(begin(Q),end(Q),begin(Q_data[0])); mem++; } mint P[6]; P[0]=1; for(int i=1;i<6;i++){ P[i]=0; } int count=0; while(N>0){ count++; if(mem<=count){ mint nQ[7]; for(int i=0;i<=6;i++){ nQ[i]=0; for(int j=max(0,2*i-6);j<=min(2*i,6);j++){ if(j%2==0){ nQ[i]+=Q[j]*Q[2*i-j]; continue; } nQ[i]-=Q[j]*Q[2*i-j]; } } copy(begin(nQ),end(nQ),begin(Q_data[mem])); mem++; } mint nP[6]; if(N%2==0){ for(int i=0;i<12;i+=2){ nP[i/2]=0; for(int j=max(0,i-5);j<=min(6,i);j++){ if(j%2==0){ nP[i/2]+=Q[j]*P[i-j]; continue; } nP[i/2]-=Q[j]*P[i-j]; } } copy(begin(nP),end(nP),begin(P)); } if(N%2==1){ for(int i=1;i<12;i+=2){ nP[i/2]=0; for(int j=max(0,i-5);j<=min(6,i);j++){ if(j%2==0){ nP[i/2]+=Q[j]*P[i-j]; continue; } nP[i/2]-=Q[j]*P[i-j]; } } copy(begin(nP),end(nP),begin(P)); } copy(begin(Q_data[count]),end(Q_data[count]),begin(Q)); N/=2; continue; } mp[M]=P[0]; return P[0]; } int main(){ int k; long long N,M; scanf("%lld%lld%d",&N,&M,&k); mint W=0; for(int i=5;i>=0;i--){ if(i==4){ continue; } W+=Bostan_Mori(N*M+i)*(i-4); } M--; long long M_sub=M; mint mul[6][6]; mint mul_sub[6][6]; mint P[6][6]; mint Q[6]; mint R[6]; for(;k--;){ M=M_sub; int C; scanf("%d",&C); for(int i=0;i<6;i++){ if(i==C){ Q[i]=0; continue; } if(C<i){ Q[i]=Bostan_Mori(i)-Bostan_Mori(C)*Bostan_Mori(i-C); continue; } Q[i]=Bostan_Mori(i); } for(int j=0;j<6;j++){ mint P_sub=0; for(int i=5;i>=0;i--){ if(i==C){ P[j][i]=0; continue; } if(j==C){ P[j][i]=0; continue; } if(i<C && j<C){ P[j][i]=Bostan_Mori(N+j-i)-Bostan_Mori(C-i)*Bostan_Mori(N+j-C); P[j][i]-=P_sub; P_sub+=P[j][i]+P_sub; continue; } if(C<j && C<i){ P[j][i]=Bostan_Mori(N+j-i)-Bostan_Mori(N+C-i)*Bostan_Mori(j-C); P[j][i]-=P_sub; P_sub+=P[j][i]+P_sub; continue; } if(i<C && C<j){ mint res1=Bostan_Mori(C-i); mint res2=Bostan_Mori(N); mint res3=Bostan_Mori(j-C); mint res4=Bostan_Mori(N+C-i); mint res5=Bostan_Mori(N+j-C); mint res6=Bostan_Mori(N+j-i); P[j][i]=res6-res1*res5-res4*res3+res1*res2*res3; P[j][i]-=P_sub; P_sub+=P[j][i]+P_sub; continue; } P[j][i]=Bostan_Mori(N+j-i); P[j][i]-=P_sub; P_sub+=P[j][i]+P_sub; } } for(int i=0;i<6;i++){ for(int j=0;j<6;j++){ if(i==j){ mul[i][j]=1; } else{ mul[i][j]=0; } } } while(M){ if(M&1){ for(int i=0;i<6;i++){ for(int j=0;j<6;j++){ mul_sub[i][j]=0; } } for(int i=0;i<6;i++){ for(int k=0;k<6;k++){ for(int j=0;j<6;j++){ mul_sub[i][j]+=mul[i][k]*P[k][j]; } } } for(int i=0;i<6;i++){ for(int j=0;j<6;j++){ mul[i][j]=mul_sub[i][j]; } } } for(int i=0;i<6;i++){ for(int j=0;j<6;j++){ mul_sub[i][j]=0; } } for(int i=0;i<6;i++){ for(int k=0;k<6;k++){ for(int j=0;j<6;j++){ mul_sub[i][j]+=P[i][k]*P[k][j]; } } } for(int i=0;i<6;i++){ for(int j=0;j<6;j++){ P[i][j]=mul_sub[i][j]; } } M/=2; } for(int i=0;i<6;i++){ P[i][0]=0; for(int j=0;j<6;j++){ P[i][0]+=mul[i][j]*Q[j]; } } for(int j=0;j<6;j++){ R[j]=0; if(j==4){ continue; } mint R_sub=0; for(int i=5;i>=0;i--){ if(P[i][0]==0){ continue; } if(i<C){ mint res=Bostan_Mori(C-i)*Bostan_Mori(N+j-C); res=Bostan_Mori(N+j-i)-res; res-=R_sub; R_sub+=res+R_sub; R[j]+=res*P[i][0]; continue; } mint res=Bostan_Mori(N+j-i); res-=R_sub; R_sub+=res+R_sub; R[j]+=res*P[i][0]; } } mint ans=0; for(int i=5;i>=0;i--){ ans+=R[i]*(i-4); } ans=W-ans; printf("%d\n",ans.val()); } }