首页 > 代码库 > Bzoj2655 calc
Bzoj2655 calc
Submit: 255 Solved: 162
Description
一个序列a1,...,an是合法的,当且仅当:
长度为给定的n。
a1,...,an都是[1,A]中的整数。
a1,...,an互不相等。
一个序列的值定义为它里面所有数的乘积,即a1a2...an。
求所有不同合法序列的值的和。
两个序列不同当且仅当他们任意一位不一样。
输出答案对一个数mod取余的结果。
Input
一行3个数,A,n,mod。意义为上面所说的。
Output
一行结果。
Sample Input
9 7 10007
Sample Output
3611
HINT
数据规模和约定
0:A<=10,n<=10。
1..3:A<=1000,n<=20.
4..9:A<=10^9,n<=20
10..19:A<=10^9,n<=500。
全部:mod<=10^9,并且mod为素数,mod>A>n+1
Source
数学问题 伯努利数 容斥 脑洞题
设$ f[i] $表示长度为i的合法序列,$ g[i]=\sum{j=1}^{A} j^i $
然后容斥一下:
$ f[i]=g[i]*f[i-1] - C_{i-1}^{1}*(2-1)!*g[2]*f[i-2]+ C_{i-1}^{2}*(3-1)!*g[3]*f[i-3] - ...$
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #define LL long long 7 using namespace std; 8 const int mxn=511; 9 int read(){10 int x=0,f=1;char ch=getchar();11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}13 return x*f;14 }15 int A,n,mod;16 int c[mxn][mxn],inv[mxn],fac[mxn];17 LL B[mxn],g[mxn],f[mxn];18 void init(){19 int i,j;20 int mxn=n+2;21 for(i=0;i<mxn;i++)c[i][0]=1;22 for(i=1;i<mxn;i++)23 for(j=1;j<mxn;j++)24 c[i][j]=((LL)c[i-1][j-1]+c[i-1][j])%mod;25 inv[0]=inv[1]=1;fac[0]=fac[1]=1;26 for(i=2;i<mxn;i++){27 inv[i]=((-mod/i*(LL)inv[mod%i]%mod)+mod)%mod;28 fac[i]=(LL)fac[i-1]*i%mod;29 }30 B[0]=1;31 for(i=1;i<mxn;i++){32 for(j=0;j<i;j++)33 B[i]=(B[i]-c[i+1][j]*B[j])%mod;34 B[i]=B[i]*inv[i+1]%mod;35 if(B[i]<0)B[i]+=mod;36 }37 return;38 }39 void solve(){40 int i,j,k;41 for(k=1;k<=n;k++){42 int tmp=A+1,bas=tmp;43 for(i=1;i<=k+1;i++){44 g[k]=g[k]+c[k+1][i]*B[k+1-i]%mod*tmp%mod;45 if(g[k]>=mod)g[k]-=mod;46 tmp=(LL)tmp*bas%mod;47 }48 g[k]=g[k]*inv[k+1]%mod;49 }50 f[0]=1;51 for(i=1;i<=n;i++){52 LL F=1;53 for(j=1;j<=i;j++){54 f[i]=(f[i]+F*g[j]*c[i-1][j-1]%mod*f[i-j]%mod*fac[j-1])%mod;55 F=-F;56 }57 }58 printf("%lld\n",(f[n]+mod)%mod);59 return;60 }61 int main(){62 int i,j;63 A=read();n=read();mod=read();64 init();65 solve();66 return 0;67 }
Bzoj2655 calc
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。