2020-2021:teams:legal_string:jxm2001:contest:edu_102
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:edu_102 [2021/01/16 16:16] jxm2001 [题解] |
2020-2021:teams:legal_string:jxm2001:contest:edu_102 [2021/01/17 13:59] (当前版本) jxm2001 [G. Tiles] |
||
|---|---|---|---|
| 行 197: | 行 197: | ||
| } | } | ||
| enter(ans-solver.Maxflow(s,t)); | enter(ans-solver.Maxflow(s,t)); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== G. Tiles ===== | ||
| + | |||
| + | 快速傅里叶变换好题 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=5005,MAXV=2e5+5,Mod=998244353; | ||
| + | int quick_pow(int a,int k){ | ||
| + | int ans=1; | ||
| + | while(k){ | ||
| + | if(k&1)ans=1LL*ans*a%Mod; | ||
| + | a=1LL*a*a%Mod; | ||
| + | k>>=1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | namespace Poly{ | ||
| + | const int G=3; | ||
| + | int rev[MAXN<<2],Pool[MAXN<<3],*Wn[30]; | ||
| + | void init(){ | ||
| + | int lg2=0,*pos=Pool,n,w; | ||
| + | while((1<<lg2)<MAXN*2)lg2++; | ||
| + | n=1<<lg2,w=quick_pow(G,(Mod-1)/(1<<lg2)); | ||
| + | while(~lg2){ | ||
| + | Wn[lg2]=pos,pos+=n; | ||
| + | Wn[lg2][0]=1; | ||
| + | _for(i,1,n)Wn[lg2][i]=1LL*Wn[lg2][i-1]*w%Mod; | ||
| + | w=1LL*w*w%Mod; | ||
| + | lg2--;n>>=1; | ||
| + | } | ||
| + | } | ||
| + | int build(int k){ | ||
| + | int n,pos=0; | ||
| + | while((1<<pos)<=k)pos++; | ||
| + | n=1<<pos; | ||
| + | _for(i,0,n)rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1)); | ||
| + | return n; | ||
| + | } | ||
| + | void NTT(int *f,int n,bool type){ | ||
| + | _for(i,0,n)if(i<rev[i]) | ||
| + | swap(f[i],f[rev[i]]); | ||
| + | int t1,t2; | ||
| + | for(int i=1,lg2=1;i<n;i<<=1,lg2++){ | ||
| + | for(int j=0;j<n;j+=(i<<1)){ | ||
| + | _for(k,j,j+i){ | ||
| + | t1=f[k],t2=1LL*Wn[lg2][k-j]*f[k+i]%Mod; | ||
| + | f[k]=(t1+t2)%Mod,f[k+i]=(t1-t2)%Mod; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | if(!type){ | ||
| + | reverse(f+1,f+n); | ||
| + | int div=quick_pow(n,Mod-2); | ||
| + | _for(i,0,n)f[i]=(1LL*f[i]*div%Mod+Mod)%Mod; | ||
| + | } | ||
| + | } | ||
| + | void Mul(int *f,int _n,int *g,int _m,int xmod=0){ | ||
| + | int n=build(_n+_m-2); | ||
| + | _for(i,_n,n)f[i]=0;_for(i,_m,n)g[i]=0; | ||
| + | NTT(f,n,true);NTT(g,n,true); | ||
| + | _for(i,0,n)f[i]=1LL*f[i]*g[i]%Mod; | ||
| + | NTT(f,n,false); | ||
| + | if(xmod)_for(i,xmod,n)f[i]=0; | ||
| + | } | ||
| + | } | ||
| + | int frac[MAXV],invfrac[MAXV],a[MAXN],b[MAXN]; | ||
| + | int C(int n,int m){ | ||
| + | if(m<0||m>n)return 0; | ||
| + | return 1LL*frac[n]*invfrac[m]%Mod*invfrac[n-m]%Mod; | ||
| + | } | ||
| + | int dp[MAXN<<2],temp[MAXN<<2],c[MAXN<<2]; | ||
| + | int main() | ||
| + | { | ||
| + | Poly::init(); | ||
| + | int n=read_int(); | ||
| + | _for(i,0,n)a[i]=read_int(),b[i]=read_int(); | ||
| + | frac[0]=1; | ||
| + | _for(i,1,MAXV) | ||
| + | frac[i]=1LL*frac[i-1]*i%Mod; | ||
| + | invfrac[MAXV-1]=quick_pow(frac[MAXV-1],Mod-2); | ||
| + | for(int i=MAXV-1;i;i--) | ||
| + | invfrac[i-1]=1LL*invfrac[i]*i%Mod; | ||
| + | dp[0]=1; | ||
| + | int len=1; | ||
| + | _for(i,0,n){ | ||
| + | _for(j,0,2*len+a[i]-b[i]-1) | ||
| + | c[j]=C(a[i]+b[i],j+b[i]-len+1); | ||
| + | Poly::Mul(dp,len,c,2*len+a[i]-b[i]-1); | ||
| + | _for(j,0,len+a[i]-b[i]) | ||
| + | dp[j]=dp[j+len-1]; | ||
| + | len+=a[i]-b[i]; | ||
| + | } | ||
| + | int ans=0; | ||
| + | _for(i,0,len) | ||
| + | ans=(ans+dp[i])%Mod; | ||
| + | enter(ans); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/edu_102.1610784990.txt.gz · 最后更改: 2021/01/16 16:16 由 jxm2001
