首页 > 代码库 > HDU 4869 Turn the pokers（思维+组合公式+快速幂）

HDU 4869 Turn the pokers（思维+组合公式+快速幂）

2024-07-13 17:14:27   211人阅读

Turn the pokers

大意：给出n次操作，给出m个扑克，然后给出n个操作的个数a[i]，每个a[i]代表可以翻的扑克的个数，求最后可能出现的扑克的组合情况。

Hint

Sample Input：

3 3

3 2 3

For the this example:

0 express face down,1 express face up

Initial state 000

The first result:000->111->001->110

The second result:000->111->100->011

The third result:000->111->010->101

So, there are three kinds of results(110,011,101)

思路：要说清楚不是很容易。官方题解是这么说的：

“最终的结果一定是连续出现的，只需要求出最终的区间。

因为如果对同一张牌进行两次操作，牌的状态不改变。故牌的翻转次数一定是减少偶数次。如果所有数的和是奇数，那么最终结果也一定是奇数。同理，偶数也是一样的。

所以只要递推求出最后的区间，计算sum（C（xi，m）（i=0，1，2。。。）），m是总牌数，xi是在区间内连续的奇数或偶数，在模10^9+9就是最终的答案。”

 

 1 #define LL long long 2  3 const int MOD = 1000000009; 4 LL J[100005]; 5  6 void Init() 7 {///初始化阶乘表 8     J[0] = 1; 9     for(int i = 1; i <= 100005; ++i){10         J[i] = J[i-1]*i%MOD;11     }12 }13 14 ///快速幂取模15 LL modexp(LL a,LL b,LL n)16 {17     LL ret=1;18     LL tmp=a;19     while(b)20     {21        if(b&1) ret=ret*tmp%n;22        tmp=tmp*tmp%n;23        b>>=1;24     }25     return ret;26 }27 ///求组合数 逆元 C(n, m) = n! * (m!*(n-m)!)^(MOD-2)28 LL C(LL n, LL m)29 {30     return J[n]*modexp(J[m]*J[n-m]%MOD, MOD-2, MOD)%MOD;31 }32 33 int a[100010];34 35 int main()36 {37     int n, m;38     Init();39     while(~scanf("%d%d", &n, &m))40     {41         for(int i = 0; i < n; ++i)42         {43             scanf("%d", &a[i]);44         }45         int l = 0;46         int r = 1;47         int t = 0;48         for(int i = 0; i < n; ++i)49         {50             int ll = min(abs(l-a[i]), abs(r-a[i]));51             if(l <= a[i] && r >= a[i])52             {53                 ll = 0;54             }55             int rr = max(m-abs(l+a[i]-m), m-abs(r+a[i]-m));56             if(l <= m-a[i] && r >= m-a[i])57             {58                 rr = m;59             }60 61             t = (t+a[i])%2;62             l = ll;63             r = rr;64         }65         long long ans = 0;66         for(int i = l; i <= r; ++i)67         {68             if(i%2 == t)69             {70                 ans += C(m, i);71                 ans %= MOD;72             }73         }74         printf("%I64d\n", ans);75     }76 77     return 0;78 }
自己写的

 

 1 #include<stdio.h> 2 #include<string.h> 3 #include<iostream> 4 #include<cmath> 5 using namespace std; 6 int a[100005]; 7 __int64 pmod = 1000000009; 8 __int64 inv[100005]; 9 __int64 ba[100005];10 __int64 rba[100005];11 #define M 10000512 void pre() {13     inv[0] = inv[1] = 1;14     ba[0] = ba[1] = 1;15     rba[0] = rba[1] = 1;16     for (int i = 2; i < M; i++) {17         inv[i] = ((pmod - pmod / i) * inv[pmod % i]) % pmod;18         ba[i] = (ba[i - 1] * i)%pmod;19         rba[i] = (rba[i - 1] * inv[i])%pmod;20     }21 }22 __int64 C(int n, int k) {23     return (ba[n] * rba[k] % pmod )* rba[n - k] % pmod;24 }
官方题解的解组合


联系
我们