思路：費馬小+快速冪
? ? ? 無論怎么翻，每一步的1出現的可能個數的奇偶性是一樣的，因為奇數 - 偶數 = 奇數，偶數 - 偶數 = 偶數，有一張牌被重疊了，那么就減去一個偶數2，所以怎么重疊都不會變（當前奇偶性與當前總翻牌數奇偶性一樣），所以我們只要找到1的最大可能數，和最小可能數（當然最大和最小奇偶性一定相同），然后排列組合求和就行了，假如一共有10張牌，1出現的最大可能數是6 ，最小是2，那么ans = C(10 ,2) + C(10 ,4) + C(10 ,6).
最大和最小之間的同奇偶的數一定可以出現，就是搓1位，自己可以畫畫，這樣又有一個蛋疼的問題，就是排列組合必然會涉及到除法，可是除法怎么處理這個 (a / b) % c因為他不等于 (a % c) / (b % c) ,乘法還可以，其實我們可以除法轉化成乘法，使得(a / b) % c = a * pow(b ,c - 2) % c,這里的c是質數，下面證明一下
根據費馬小定理有
a^(p - 1) % p = 1 % p
那么
(a^(p - 1) / a) % p = (1 / p) % p ?則 a^(p - 2) = (1 / a) % p
除以a只要乘以1/a也就是乘以等號左側，這樣就把除法變成乘法。
注意成立的原因是在本題目里 a^(p-1)/p是一個大于等于p的數。?

對于求1可能出現的次數min ,和max，就是分情況討論，直接看代碼自己模擬一下代碼就懂了，這里就不解釋了，全解釋了讀者看完也就沒意思了。 ?

#include<stdio.h>#define MOD 1000000009 __int64 X[110000]; __int64 C[110000];__int64 quick_pow(__int64 a ,__int64 b) {__int64 c = 1;while(b){if(b&1) c *= a;a *= a ,b /= 2;c %= MOD ,a %= MOD;}return c; }int main () {int n ,m ,i;while(~scanf("%d %d" ,&m ,&n)){for(i = 1 ;i <= m ;i ++)scanf("%I64d" ,&X[i]);__int64 MIN = 0 ,MAX = 0;for(i = 1 ;i <= m ;i ++){__int64 mi ,ma;if(X[i] <= MIN) mi = MIN - X[i];else if(X[i] > MAX) mi = X[i] - MAX;else mi = (X[i]&1) != (MIN&1);if(X[i] + MAX <= n) ma = X[i] + MAX;else if(X[i] + MIN > n) ma = n * 2 - (MIN + X[i]);else ma = ((X[i] + MIN) & 1) == (n & 1) ? n : n - 1;MAX = ma ,MIN = mi;}__int64 sum = 0;C[0] = 1;if(MIN == 0) sum ++;for(i = 1 ;i <= MAX ;i ++){if(n - i < i) C[i] = C[n-i];else C[i] = C[i-1] * (n - i + 1) % MOD * quick_pow(i ,MOD - 2) % MOD;if(i >= MIN && (i&1) == (MIN&1))sum = (sum + C[i]) % MOD; }printf("%I64d\n" ,sum);}return 0; } ?? ?

總結

以上是生活随笔為你收集整理的hdu4869 费马小+快速幂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。