题意 : m张牌,可以翻n次,每次翻xi张牌,问最后能得到多少种形态。
思路 :0定义为反面,1定义为正面,(一开始都是反), 对于每次翻牌操作,我们定义两个边界lb,rb,代表每次中1最少时最少的个数,rb代表1最多时的个数。一张牌翻两次和两张牌翻一次 得到的奇偶性相同,所以结果中lb和最多的rb的奇偶性相同。如果找到了lb和rb,那么,介于这两个数之间且与这两个数奇偶性相同的数均可取到,然后在这个区间内求组合数相加(若lb=3,rb=7,则3,5,7这些情况都能取到,也就是说最后的结果就是在所有的牌中选3张翻过去+选5张+选7张)。所以,要根据情况先求出边界。
由于数据相当大,所以要将组合中的除法变成乘法,C(n, m) = n!/(m!*(n-m)!),由 费马小定理:若p是质数 , 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,这样就可以变除为乘。而 求(n-m)!)^(p-2 )mod p中用快速幂简化运算。
here这个人的代码对于边界解释的较为详尽。
官方题解 :
最终的结果一定是连续出现的,只需要求出最终的区间。
因为如果对同一张牌进行两次操作,牌的状态不改变。故牌的翻转次数一定是减少偶数次。如果所有数的和是奇数,那么最终结果也一定是奇数。同理,偶数也是一样的。
所以只要递推求出最后的区间,计算sum(C(xi,m)(i=0,1,2。。。)),m是总牌数,xi是在区间内连续的奇数或偶数,在模10^9+9就是最终的答案。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 5 using namespace std ; 6 7 #define mod 1000000009 8 #define LL __int64 9 10 LL f[100010] ; 11 void mul() 12 { 13 f[0] = 1 ; 14 for(int i = 1 ; i < 100010 ; i++) 15 f[i] = (f[i-1] * i)%mod ; 16 } 17 18 LL multimod(LL a,LL b) 19 { 20 LL res = 1 ; 21 while(b) 22 { 23 if(b & 1) 24 { 25 res *= a ; 26 res %= mod ; 27 } 28 b >>= 1 ; 29 a *= a ; 30 a %= mod ; 31 } 32 return res ; 33 } 34 int main() 35 { 36 int n , m ; 37 mul() ; 38 while(scanf("%d %d",&n,&m) != EOF) 39 { 40 int x ; 41 scanf("%d",&x) ; 42 int lb = x, rb = x ; 43 for(int i = 1 ; i < n ; i++) 44 { 45 scanf("%d",&x) ; 46 int l = lb - x ; 47 int r = rb + x ; 48 if(l < 0) { 49 if(rb - x <= 0 ) l = x - rb ; 50 else l = ( (lb - x)%2 + 2)%2 ;//类似于奇数张牌中翻奇数张最后肯定是偶数,奇数翻偶数张肯定是奇数,肯定会有一个中间状态得到最后非0即1 51 //此时,正处于lb<x<rb的时候,当翻x张牌时,若x的奇偶性与lb,rb相同时,则代表刚好是翻牌已经达到的某个状态,也就是说把剩下的x张都反过来即可,而奇偶若是不同,说明要么多一张或者是少一张,所以就是1. 52 } 53 if(r > m){ 54 if(lb + x <= m) r = m - (rb + x)%2; 55 else r = m-(lb+x - m) ; 56 } 57 lb = l ; 58 rb = r ; 59 } 60 LL ans = 0 ; 61 for(int i = lb ; i <= rb ; i += 2) 62 ans += ((f[m] % mod) * (multimod((f[i]*f[m-i]) % mod,mod-2)))%mod ; 63 cout << ans % mod << endl ; 64 } 65 return 0 ; 66 }
2014多校第一场 I 题 || HDU 4869 Turn the pokers(费马小定理+快速幂模),布布扣,bubuko.com
2014多校第一场 I 题 || HDU 4869 Turn the pokers(费马小定理+快速幂模)
原文:http://www.cnblogs.com/luyingfeng/p/3866563.html