首页 > 代码库 > 2014多校第一场 I 题 || HDU 4869 Turn the pokers（费马小定理+快速幂模）

2014多校第一场 I 题 || HDU 4869 Turn the pokers（费马小定理+快速幂模）

2024-07-13 21:53:39   225人阅读

题目链接

题意 ： 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即151             //此时，正处于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 }
View Code


联系
我们