首页 > 其他 > 详细

BZOJ 3027 [Ceoi2004]Sweet

时间:2018-06-21 10:52:23      阅读:167      评论:0      收藏:0      [点我收藏+]

BZOJ 3027 [Ceoi2004]Sweet

生成函数


题解:

求出 <= b 的答案减去 <=a-1 的答案

先写出每个物品的生成函数

\((1+x+x^{2}+x^{3} \cdots)=\frac{1-x^{m_{i}+1}}{1-x}\)

然后把他们乘起来

\(\prod_{i=1}^{n}\frac{1-x^{m_{i}+1}}{1-x}\)

\(=(1+x+x^{2}+x^{3}+\cdots)^{n}\prod_{i=1}^{n}(1-x^{m_{i}+1})\)

然后暴力展开后面的式子,最多有\(2^{n}\)

对于前面的式子,\(x^{i}\)这一项的系数由隔板法得到为 \(C_{i+n-1}^{n-1}\)
对于后面的\(k \times 2^{y}\)项,他对答案的贡献是

\(k \times (C_{n-1}^{n-1}+C_{1+n-1}^{n-1}+C_{2+n-1}^{n-1}+ \cdots +C_{a-y+n-1}^{n-1})\)

然后发现这其实是杨辉三角的一列,然后式子化成\(=k \times C_{a-y+n}^{n}\)

模数不是质数所以可能没有逆元

\(C_{a-y+n}^{n}=\frac{(a-y+n)!}{n!(a-y)!}=\frac{(a-y+n)^{\underline{n}}}{n!}\)

算组合数的时候,先算在 \(\text{mod}(P*n!)\) 下的结果,然后再 \(/n!\)

时间复杂度 \(O(n \times 2^{n})\)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mm=2004;
const int maxn=20;

int n,mx,mi;
long long ans=0;
int a[maxn];


long long nt=1;

long long C(int n,int m){
    if(n<0||m<0)return 0;
    if(n<m)return 0;
    long long ret=1;
    for(int i=n-m+1;i<=n;++i)ret=ret*i%(mm*nt);
    return ret/nt;
}

int limx;
long long Dfs(int x,int f,int t){
    if(x==n+1){
        long long ret=0;
        return (f*C(limx-t+n,n)+mm)%mm;
    }
    
    return (Dfs(x+1,f,t)+Dfs(x+1,-f,t+a[x]+1))%mm;
}
long long GetAns(int m){
    limx=m;
    return Dfs(1,1,0);
}

int main(){
    scanf("%d%d%d",&n,&mi,&mx);
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i)nt=nt*i;
    
    ans=(GetAns(mx)-GetAns(mi-1)+mm)%mm;
    
    cout<<ans<<endl;
    
    return 0;
}

BZOJ 3027 [Ceoi2004]Sweet

原文:https://www.cnblogs.com/zzyer/p/9207000.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!