首页 > 代码库 > hdu_4869_ 费马小引理+快速幂
hdu_4869_ 费马小引理+快速幂
Turn the pokers
题意：
给定m张牌，初始状态均为反面朝上。给定n次操作，每次指定所要翻的牌数，求n次操作后的牌的状态总数 mod 1000000009。
输入：
第一行n和m，代表n次操作和m张牌；
第二行n个数，代表每次要翻的牌的张数。
输出：
方案数 mod 1000000009。
思路：
设反面为0，正面为1。对于一张牌翻两次和两张牌翻一次 得到的奇偶性相同，所以结果中最少的1（S）和最多的1（E）的奇偶性相同。如果找到了S和E，那么，介于这两个数之间且与这两个数奇偶性相同的数均可取到，然后在这个区间内组合数求解即可。
因此这道题要解决好两个问题，一是求边界条件S和E，另一个是求在这之间内组合数求解。
注意到这道题数据很大，C(n， m) = n!/(m!*(n-m)!)，除法运算变得不合适。由 费马小定理 a^(p-1) = 1%p，那么，a^(p-2) = 1/a%p，利用这个公式，得到1/(m!*(n-m)!) = (m!*(n-m)!)^(p-2) mod p，即C(n, m) = n!*(m!*(n-m)!)^(p-2) mod p，这样就可以变除为乘。(也可以用求逆元 ing…)
求(n-m)!)^p-2 mod p中用快速幂简化运算。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #define X 100005 6 using namespace std; 7 8 long long f[X]; 9 long long mod = 1000000009;10 11 void initial()12 {13 f[0] = 1;14 for(int i = 1; i < X; i++)15 f[i] = (f[i-1]*i)%mod;16 }17 18 // 快速幂19 long long PowerMod(long long a, long long b)20 {21 long long ans = 1;22 a = a % mod;23 while(b>0) {24 if(b % 2 == 1)25 ans = (ans * a) % mod;26 b = b/2;27 a = (a * a) % mod;28 }29 return ans;30 }31 32 int main()33 {34 int n, m, x;35 int s, e, S, E;36 37 initial(); // 求出n的阶乘38 39 while(scanf("%d%d", &n, &m) != EOF)40 {41 s = 0; e = 0;42 for(int i = 0; i < n; i++) { // 找出最多和最少的1的个数43 scanf("%d", &x);44 if(x <= s) S = s - x;45 else if(e >= x) S = (s%2 == x%2)?0:1;46 else S = x - e;47 if(e+x <= m) E = e + x;48 else if(s+x <= m) E = (((s+x)%2) == (m%2)?m:m-1);49 else E = 2*m-(s+x);50 s = S;51 e = E;52 }53 long long ans = 0;54 for(int i = S; i <= E; i+=2) // 使用快速幂和费马小定理得出结果55 ans += ((f[m]%mod)*(PowerMod((f[i]*f[m-i])%mod, mod-2)%mod))%mod;56 printf("%lld\n", ans%mod);57 }58 return 0;59 }
Ps：看了别人的代码，感觉都和别人的一样了，不熟练这样还可以理解，以后就再这样不行了。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。