洛谷P3746 [六省联考2017]组合数问题
2018-06-17 21:01:08来源:未知 阅读 ()
题目描述
组合数 C_n^mCnm? 表示的是从 n 个互不相同的物品中选出 m 个物品的方案数。举个例子,从 (1;2;3) 三个物品中选择两个物品可以有 (1;2);(1;3);(2;3) 这三种选择方法。根据组合数的定义,我们可以给出计算组合数 C_n^mCnm? 的一般公式:
C_n^m = \frac{n!}{m!(n-m)!}Cnm?=m!(n−m)!n!?
其中 n! = 1 × 2 × · · · × n。(特别的,当 n = 0 时, n! = 1 ,当 m > n 时, C_n^m =0Cnm?=0 )
小葱在 NOIP 的时候学习了 C_i^jCij? 和 k 的倍数关系,现在他想更进一步,研究更多关于组合数的性质。小葱发现, C_i^jCij? 是否是 k 的倍数,取决于 C_i^j mod kCij?modk 是否等于 0,这个神奇的性质引发了小葱对 mod 运算(取余数)的兴趣。现在小葱选择了是四个整数n; p; k; r,小葱现在希望知道
\sum_{i=0}^{\inf} C_{nk}^{ik+r} mod p∑i=0inf?Cnkik+r?modp
的值。
输入输出格式
输入格式:
第一行有四个整数 n; p; k;r,所有整数含义见问题描述。
输出格式:
一行一个整数代表答案。
输入输出样例
2 10007 2 0
8
20 10007 20 0
176
说明
• 对于 30% 的测试点, 1 ≤ n; k ≤ 30, p 是质数;
• 对于另外 5% 的测试点, p = 2;
• 对于另外 5% 的测试点, k = 1;
• 对于另外 10% 的测试点, k = 2;
• 对于另外 15% 的测试点, 1 ≤ n ≤ 10^3; 1 ≤ k ≤ 50, p 是质数;
• 对于另外 15% 的测试点, 1 ≤ n × k ≤ 10^6, p 是质数;
• 对于另外 10% 的测试点, 1 ≤ n ≤ 10^9; 1 ≤ k ≤ 50, p 是质数;
• 对于 100% 的测试点, 1 ≤ n ≤ 10^9; 0 ≤ r < k ≤ 50; 2 ≤ p ≤ 2^30 − 1。
作为省选的T3出题人居然给了60分的暴力分,太良心了QWQ..
不过正解是死活想不到啊
设$C[i][j]$表示从$i$个元素中,拿所有满足$x \%k=j $ 的 $x$个元素的方案数
那么对于第$i$个元素,
不选的方案数为$C[i-1][j]$
选的方案数为$C[i-1][(j-1+k)%k]$
很显然
可以用矩阵快速幂优化
然后就做完了
这题的关键是把杨辉三角的递推与题目中给出的式子相结合,找到题目中式子的一般规律,
进而通过更高科技的算法优化
注意$k=1$的特殊情况
#include<cstdio> #include<queue> #include<algorithm> #include<cstring> #define int long long using namespace std; const int MAXN=1e6; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int N,mod,k,r; int C[51][51]; struct Matrix { int a[51][51]; Matrix(){memset(a,0,sizeof(a));} }; Matrix mul(Matrix x,Matrix y) { Matrix c; for(int kk=0;kk<=k-1;kk++) for(int i=0;i<=k-1;i++) for(int j=0;j<=k-1;j++) c.a[i][j]=(c.a[i][j]+x.a[i][kk]*y.a[kk][j]%mod)%mod; return c; } void out(Matrix x) { for(int i=0;i<=k-1;i++,puts("\n")) for(int j=0;j<=k-1;j++) printf("%d ",x.a[i][j]); } Matrix fastpow(Matrix a,int p) { Matrix base; for(int i=0;i<=k;i++) base.a[i][i]=1; while(p) { if(p&1) base=mul(base,a); a=mul(a,a); p>>=1; } return base; } main() { #ifdef WIN32 freopen("a.in","r",stdin); #endif N=read(),mod=read(),k=read(),r=read(); Matrix tmp; for(int i=0;i<=k-2;i++) tmp.a[i][i]=tmp.a[i][i+1]=1; tmp.a[k-1][0]++;tmp.a[k-1][k-1]++; Matrix ans; ans.a[0][0]=1; tmp=fastpow(tmp,N*k); ans=mul(ans,tmp); printf("%lld",ans.a[0][r]); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:我的C++学习之旅
- 洛谷P1164->小A点菜 2020-05-18
- 洛谷P1907口算练习题 2020-03-24
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
- 洛谷P1034 矩形覆盖 2020-03-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash