首页 > 代码库 > Bzoj4870 [SXOI2017]组合数问题
Bzoj4870 [SXOI2017]组合数问题
Submit: 155 Solved: 78
Description
.jpg)
Input
第一行有四个整数 n, p, k, r，所有整数含义见问题描述。
1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2^30 − 1
Output
一行一个整数代表答案。
Sample Input
2 10007 2 0
Sample Output
8
HINT
Source
黑吉辽沪冀晋六省联考
数学问题 组合数
震惊！考场上花式骗分竟然可以拿到80分！
正解：
这个东西当然没有什么既成的公式，需要用DP推公式，和平常的公式推DP正好反过来了。
发现这个式子的项覆盖了nk内所有%k==r的位置，那么可以考虑这个式子的组合意义——
在全部nk个物品中，选出任意个物品使得选出的物品数%k==r的方案数！
设f[考虑到第i个物品][选出数量%k==j]=方案数，于是变成了可以$O(n^3)$推出来的背包问题？
还可以更加简单粗暴，$f[2n][(i+j)%k]=\sum f[n][i]*f[n][j] $ $O(n^2 logn)$倍增出解。
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #define LL long long 9 using namespace std;10 const int mxn=100010;11 int read(){12 int x=0,f=1;char ch=getchar();13 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}14 while(ch>=‘0‘ && ch<=‘9‘){x=x*10-‘0‘+ch;ch=getchar();}15 return x*f;16 }17 int n,P,k,r;18 struct num{19 int x[52];20 void init(){21 memset(x,0,sizeof x);22 }23 }f;24 num calc(const num &a,const num &b){25 num res;26 res.init();27 for(int i=0;i<=k;i++)28 for(int j=0;j<=k;j++)29 (res.x[(i+j)%k]+=(LL)a.x[i]*b.x[j]%P)%=P;30 return res;31 }32 num ksm(num a,LL t){33 num res;34 res.init();res.x[0]=1;35 while(t){36 if(t&1)res=calc(res,a);37 a=calc(a,a);38 t>>=1;39 }40 return res;41 }42 int main(){43 int i,j;44 n=read();P=read();k=read();r=read();45 f.x[0]=1;46 f.x[1%k]+=1;47 f=ksm(f,(LL)n*k);48 // for(i=0;i<=k;i++)printf("%d\n",f.x[i]);49 printf("%d\n",f.x[r]);50 return 0;51 }
Bzoj4870 [SXOI2017]组合数问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。