Turn the pokers

大意：給出n次操作，給出m個(gè)撲克，然后給出n個(gè)操作的個(gè)數(shù)a[i]，每個(gè)a[i]代表可以翻的撲克的個(gè)數(shù)，求最后可能出現(xiàn)的撲克的組合情況。

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)

思路：要說清楚不是很容易。官方題解是這么說的：

“最終的結(jié)果一定是連續(xù)出現(xiàn)的，只需要求出最終的區(qū)間。

因?yàn)槿绻麑?duì)同一張牌進(jìn)行兩次操作，牌的狀態(tài)不改變。故牌的翻轉(zhuǎn)次數(shù)一定是減少偶數(shù)次。如果所有數(shù)的和是奇數(shù)，那么最終結(jié)果也一定是奇數(shù)。同理，偶數(shù)也是一樣的。

所以只要遞推求出最后的區(qū)間，計(jì)算sum（C（xi，m）（i=0，1，2。。。）），m是總牌數(shù)，xi是在區(qū)間內(nèi)連續(xù)的奇數(shù)或偶數(shù)，在模10^9+9就是最終的答案?！?/span>

?

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 ///求組合數(shù) 逆元 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 100005 12 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 } 官方題解的解組合

轉(zhuǎn)載于:https://www.cnblogs.com/Silence-AC/p/3864103.html

總結(jié)

以上是生活随笔為你收集整理的HDU 4869 Turn the pokers（思维+组合公式+快速幂）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。