結果
問題 | No.2810 Have Another Go (Hard) |
ユーザー |
![]() |
提出日時 | 2024-06-21 22:33:26 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,908 bytes |
コンパイル時間 | 4,920 ms |
コンパイル使用メモリ | 306,904 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-24 13:32:52 |
合計ジャッジ時間 | 10,420 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 50 |
ソースコード
#include<stdio.h> #include<vector> #include<bits/stdc++.h> #include<atcoder/modint> #include<atcoder/convolution> using namespace std; using namespace atcoder; using mint=modint998244353; #pragma GCC target "arch=skylake" #pragma GCC optimize "Ofast" mint Bostan_Mori(long long N){ int d=6; vector<mint> Q(d+1); Q[0]=1; for(int i=1;i<=d;i++){ Q[i]=-1; } vector<mint> P(d); P[0]=1; int z=16; mint iz=935854081; mint w=929031873; mint iw=337190230; mint W[z/2]; W[0]=1; for(int i=1;i<z/2;i++){ W[i]=W[i-1]*iw; } auto rev=[](int i){ int j=0; int k=3; for(;k--;){ j=j*2+i%2; i/=2; } return j; }; while(N>0){ Q.resize(z/2); vector<mint> Q_minus=Q; for(int i=1;i<=d;i+=2){ Q_minus[i]*=-1; Q[i]*=-1; } internal::butterfly(Q_minus); mint res=1; for(mint &i : Q){ i*=res; res*=w; } internal::butterfly(Q); Q_minus.insert(Q_minus.end(),Q.begin(),Q.end()); for(int i=0;i<z/2;i++){ Q[i]=Q_minus[i*2+1]*Q_minus[i*2]; } internal::butterfly_inv(Q); for(mint &i : Q){ i*=iz*2; } Q.resize(d+1); P.resize(z/2); vector<mint> P_sub=P; internal::butterfly(P); res=1; for(mint &i : P_sub){ i*=res; res*=w; } internal::butterfly(P_sub); P.insert(P.end(),P_sub.begin(),P_sub.end()); for(int i=0;i<z;i++){ P[i]*=Q_minus[i]; } if(N%2==0){ for(int i=0;i<z/2;i++){ P[i]=(P[i*2]+P[i*2+1])*mint(499122177); } P.resize(z/2); internal::butterfly_inv(P); for(mint &i : P){ i*=iz*2; } P.resize(d); N/=2; continue; } for(int i=0;i<z/2;i++){ P[i]=(P[i*2]-P[i*2+1])*mint(499122177); P[i]*=W[rev(i)]; } P.resize(z/2); internal::butterfly_inv(P); for(mint &i : P){ i*=iz*2; } P.resize(d); N/=2; continue; } return P[0]/Q[0]; } template<typename T> struct matrix{ int H,W; vector<vector<T>> table; matrix(int h,int w) : H(h),W(w){ table.resize(h,vector<T>(w)); } int size(){ return H; } matrix pow(long long N){ assert(H==W); assert(0<=N); matrix x=*this; matrix r(H,H); for(int i=0;i<H;i++){ r[i][i]=1; } while(N){ if(N&1)r*=x; x*=x; N>>=1; } return r; } vector<T>& operator[](int index){ assert(index<H); return table[index]; } matrix& operator+=(const matrix &other){ for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ if((int)(other.table.size())<=i){ continue; } if((int)(other.table[i].size())<=j){ continue; } (*this)[i][j]+=other.table[i][j]; } } return *this; } matrix operator*=(const matrix &other){ int h=other.H; int w=other.W; assert(h==W); //結果はH*w行列になる matrix result(H,w); for(int i=0;i<H;i++){ for(int k=0;k<W;k++){ for(int j=0;j<w;j++){ result.table[i][j]+=table[i][k]*other.table[k][j]; } } } *this=result; return *this; } }; int main(){ int N,k; long long M; scanf("%d%lld%d",&N,&M,&k); //1,1,2,4,8,16で始まり,前6項を足す線型漸化式に使うvectorを用意しておく vector<mint> A(6); A[0]=1; A[1]=1; A[2]=2; A[3]=4; A[4]=8; A[5]=16; vector<mint> c(6,mint(1)); for(;k--;){ int C; scanf("%d",&C); vector<vector<mint>> P(6,vector<mint>(6)); //P[i][j]:X=iからスタートして,X=N+j(ピッタリ)で終わるサイコロの振り方であって,常にX \not \equiv C (mod N)である場合 for(int i=0;i<6;i++){ for(int j=0;j<6;j++){ if(i==C){ P[i][j]=0; continue; } if(j==C){ P[i][j]=0; continue; } if(i<C && j<C){ P[i][j]=Bostan_Mori(C-i); P[i][j]*=Bostan_Mori(N+j-C); P[i][j]=Bostan_Mori(N+j-i)-P[i][j]; continue; } if(C<j && C<i){ P[i][j]=Bostan_Mori(N+C-i); P[i][j]*=Bostan_Mori(j-C); P[i][j]=Bostan_Mori(N+j-i)-P[i][j]; 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[i][j]=res6-res1*res5-res4*res3+res1*res2*res3; continue; } P[i][j]=Bostan_Mori(N+j-i); } } matrix<mint> Q(6,6); for(int i=0;i<6;i++){ for(int j=0;j<6;j++){ Q[i][j]=P[j][i]; } } Q=Q.pow(M-2);//to do:M=1の場合に場合分けして書く matrix<mint> R(6,1); for(int i=0;i<6;i++){ R[i][0]=P[0][i]; } Q*=R; vector<mint> S(6); for(int i=0;i<6;i++){ if(Q[i][0]==0){ continue; } for(int j=0;j<6;j++){ //iからN+jに動く //N~N+jの間のCについては無視 if(i<C){ mint res=Bostan_Mori(C-i)*Bostan_Mori(N+j-C); res=Bostan_Mori(N+j-i)-res; S[j]+=res*Q[i][0]; continue; } assert(i!=C); mint res=Bostan_Mori(N+j-i); S[j]+=res*Q[i][0]; } } mint ans=0; for(int i=5;i>=0;i--){ for(int j=i-1;j>=0;j--){ S[i]-=S[j]; } ans+=S[i]; } printf("%d\n",ans.val()); } }