之前挖了两个大坑
一个是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\n",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\n",kase,a[idx[0][k]][cnt+1]);
}return 0;
}