之前挖了两个大坑
一个是day1下午的第二题
另一个是day2上午的第五题
先说day1下午的第二题吧
我们显然不能O(n^2)的dp,所以我们只能算贡献
首先对于任意一个边界点而言,他对答案的贡献路径有很多,但是贡献的系数都形如a^c*b^d的形式
而且很容易发现贡献系数是一个定值,那么贡献次数就等于贡献路径的条数,就等于从这个点走到(n,n)的方案数
这是能用组合数算出来的
可以得出贡献系数为 C(2n-i-2,n-i)*a^(n-1)*b^(n-i)或者C(2n-i-2,n-i)*a^(n-i)*b^(n-1)
也就是所有边界点的贡献我们可以在O(n)的时间内算出,接下来考虑c的贡献
不妨还是利用上面的思路,可以得到c的贡献为c*sigma(C(2n-i-j,n-i)*a^(n-j)*b^(n-i))
不难发现这是个卷积形式,我们不妨设
f(i+j)=(2n-i-j)!
g(j)=a^(n-j)/(n-j)!
h(i)=b^(n-i)/(n-i)!
然后利用FFT求出g(j)*h(i),之后枚举i+j O(n)扫一遍计算就可以啦
模数不太优美,所以采用将数分解成k*blo+b的形式做FFT
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const int maxn=600010,mod=1000003,M=1000; int n,a,b,c,k,N,L,ans; int pa[maxn],pb[maxn]; int jc[maxn],rev[maxn],inv[maxn]; int a0[maxn],b0[maxn],a1[maxn],b1[maxn]; int aa[maxn],bb[maxn],C[maxn]; const long double pi=acos(-1.0); struct cpx{ long double r,i; cpx(long double r=0,long double i=0):r(r),i(i){} cpx cp(){return cpx(r,-i);} }A[maxn],B[maxn]; cpx operator +(const cpx &A,const cpx &B){return cpx(A.r+B.r,A.i+B.i);} cpx operator -(const cpx &A,const cpx &B){return cpx(A.r-B.r,A.i-B.i);} cpx operator *(const cpx &A,const cpx &B){return cpx(A.r*B.r-A.i*B.i,A.r*B.i+A.i*B.r);} void read(int &num){ num=0;char ch=getchar(); while(ch<'!')ch=getchar(); while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar(); } int pow_mod(int v,int p){ int tmp=1; while(p){ if(p&1)tmp=1LL*tmp*v%mod; v=1LL*v*v%mod;p>>=1; }return tmp; } void init_a(){ read(k); for(int i=2;i<=n;++i){ read(k); ans=ans+1LL*jc[(n<<1)-i-2]*inv[n-i]%mod*pa[n-1]%mod*pb[n-i]%mod*k%mod; if(ans>=mod)ans-=mod; }return; } void init_b(){ read(k); for(int i=2;i<=n;++i){ read(k); ans=ans+1LL*jc[(n<<1)-i-2]*inv[n-i]%mod*pa[n-i]%mod*pb[n-1]%mod*k%mod; if(ans>=mod)ans-=mod; }return; } void FFT(cpx A[],int n,int type){ for(int i=1;i<n;++i)if(i<rev[i])swap(A[i],A[rev[i]]); for(int k=0;(1<<k)<n;++k){ int m=(1<<k),m2=(m<<1); long double o=pi*2/m2*type; cpx wn(cos(o),sin(o)); for(int i=0;i<n;i+=m2){ cpx w(1,0); for(int j=0;j<m;++j){ cpx x=A[i+j],y=A[i+j+m]*w; A[i+j]=x+y;A[i+j+m]=x-y; w=w*wn; } } } if(type==-1)for(int i=0;i<n;++i)A[i].r/=n; } void mul(int *a,int *b,int *c){ for(int i=0;i<N;++i)A[i]=cpx(a[i],0); for(int i=0;i<N;++i)B[i]=cpx(b[i],0); FFT(A,N,1);FFT(B,N,1); for(int i=0;i<N;++i)A[i]=A[i]*B[i]; FFT(A,N,-1); for(int i=0;i<N;++i)c[i]=((LL)(A[i].r+0.5))%mod; } void mul_mod(int *a,int *b,int *c){ for(int i=0;i<N;++i)a0[i]=a[i]/M,b0[i]=b[i]/M; mul(a0,b0,a0); for(int i=0;i<N;++i){ c[i]=1LL*a0[i]*M*M%mod; a1[i]=a[i]%M;b1[i]=b[i]%M; } mul(a1,b1,a1); for(int i=0;i<N;++i){ c[i]=c[i]+a1[i]; if(c[i]>=mod)c[i]-=mod; a0[i]=a0[i]+a1[i]; if(a0[i]>=mod)a0[i]-=mod; a1[i]=a[i]/M+a[i]%M; b1[i]=b[i]/M+b[i]%M; } mul(a1,b1,a1); for(int i=0;i<N;++i){ c[i]=c[i]+1LL*M*(a1[i]-a0[i]+mod)%mod; if(c[i]>=mod)c[i]-=mod; }return; } int main(){ read(n);read(a);read(b);read(c); pa[0]=pb[0]=1;jc[0]=1; for(int i=1;i<=n;++i)pa[i]=1LL*pa[i-1]*a%mod; for(int i=1;i<=n;++i)pb[i]=1LL*pb[i-1]*b%mod; for(int i=1;i<=(n<<1);++i)jc[i]=1LL*jc[i-1]*i%mod; inv[n<<1]=pow_mod(jc[n<<1],mod-2); for(int i=(n<<1)-1;i>=0;--i)inv[i]=1LL*inv[i+1]*(i+1)%mod; init_a();init_b();ans=1LL*ans*inv[n-2]%mod; for(N=1,L=0;N<=n;N<<=1,L++);N<<=1,L++; for(int i=0;i<N;++i)rev[i]=rev[i>>1]>>1|((i&1)<<(L-1)); for(int i=2;i<=n;++i)aa[i]=1LL*pa[n-i]*inv[n-i]%mod; for(int i=2;i<=n;++i)bb[i]=1LL*pb[n-i]*inv[n-i]%mod; mul_mod(aa,bb,C); for(int i=4;i<=(n<<1);++i){ ans=ans+1LL*C[i]*jc[(n<<1)-i]%mod*c%mod; if(ans>=mod)ans-=mod; }printf("%d ",ans); return 0; }
day2上午第五题
不难发现这道题是要求概率的,由于是要求连续赢了m盘,所以我们只需要知道队头连续赢了多少就可以了
不妨设f(i,j)表示队头连续赢了i局,队里的第j个人获胜的概率
然后分j=1,2,3,4和j>4分类讨论就可以啦,列出方程之后发现是有环的
然后高斯消元解一下就可以了
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #include<cmath> #define eps 1e-5 using namespace std; const int maxn=120; int T,cnt,kase; int n,m,k; double a[maxn][maxn]; int idx[maxn][maxn]; void Gauss(int n){ int to; for(int i=1;i<=n;++i){ for(to=i;to<=n;++to)if(fabs(a[to][i])>eps)break; if(to!=i)for(int j=1;j<=n+1;++j)swap(a[to][j],a[i][j]); double tmp=a[i][i]; for(int j=1;j<=n+1;++j)a[i][j]/=tmp; for(int j=1;j<=n;++j){ if(j==i)continue; double tmp=a[j][i]/a[i][i]; for(int k=1;k<=n+1;++k){ a[j][k]-=tmp*a[i][k]; } } }return; } int main(){ scanf("%d",&T); while(T--){ scanf("%d%d%d",&n,&m,&k); cnt=0; for(int i=0;i<=m;++i){ for(int j=1;j<=n;++j)idx[i][j]=++cnt; } memset(a,0,sizeof(a)); for(int i=0;i<m;++i){ for(int j=1;j<=n;++j){ int now=idx[i][j],cur; a[now][now]--; if(j==1){ cur=idx[i+1][j]; a[now][cur]+=0.25; cur=idx[1][n-2]; a[now][cur]+=0.75; }else if(j==2){ cur=idx[1][1]; a[now][cur]+=0.25; cur=idx[i+1][n-2]; a[now][cur]+=0.25; cur=idx[1][n-1]; a[now][cur]+=0.5; }else if(j==3){ cur=idx[1][1]; a[now][cur]+=0.25; cur=idx[i+1][n-1]; a[now][cur]+=0.25; cur=idx[1][n-1]; a[now][cur]+=0.25; cur=idx[1][n]; a[now][cur]+=0.25; }else if(j==4){ cur=idx[1][1]; a[now][cur]+=0.25; cur=idx[i+1][n]; a[now][cur]+=0.25; cur=idx[1][n]; a[now][cur]+=0.5; }else{ cur=idx[i+1][j-3]; a[now][cur]+=0.25; cur=idx[1][j-3]; a[now][cur]+=0.75; } } } for(int i=1;i<=n;++i){ int now=idx[m][i]; a[now][now]--; if(i==1)a[now][cnt+1]=-1; } Gauss(cnt);kase++; printf("Case #%d: %.6lf ",kase,a[idx[0][k]][cnt+1]); }return 0; }