/* 題意:n個開關,每個控制對應的燈,現要求m步使得最終狀態的前v個燈亮 每一步可同時按多個開關,也可以都不按,每一步都不能相同 問有多少種方法(如果兩種方法所有步的集合相同(即無序),則認為是同一種)
看解題報告的 可選的步驟集合是{0,1}^n 即2^n種 求的是無序的,可以先求有序的 設所求答案為fm(v),令gm(v) = m!fm(v) (gm(v)是有步驟的) 選擇前面m-1個的方法有(m-1)!C(2^n,m-1) 這樣,確定前面m-1個了,則第m個即為vm = v⊕v1⊕v2 ⊕vm-1 但這樣有一個問題,因為題目要求兩步不能相同,上面式子有可能vm = vi 假設是vm=v1,則,v2 ⊕vm-1 = v 這就是規模為m-2的!!! 所以gm(v) = (m-1)!C(2^n,m-1) - (m-1)(2^n-(m-2))gm-2(v) 選擇跟某一個vi相同,而該vi可選的范圍是(2^n-(m-2)),剩下的m-2個就是gm-2(v) 則fm(v) = 1/m*C(2^n,m-1) - 1/m*(2^n-(m-2))*gm-2(v) 注意的是初始條件!! f[0] = (v==0)
還有一個地方,答案是取模一個素數的 對于素數的話 逆元 (1/x) mod p = x^-1 mod p = x^(p-2) mod p 因為素數 x^(p-1) %p= 1 */
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <string> #include <vector> #include <algorithm>
using namespace std;
const int MAXN = 1010; const int MOD = 10567201;
long long f[MAXN]; long long pow2[MAXN],inv[MAXN];
long long mpow(int a,int n) { if(n==1)return a%MOD; long long ans = mpow(a,n/2); ans = ans*ans%MOD; if(n&1)ans = ans*a%MOD; return ans; }
void init() { pow2[0] = 1; for(int i=1;i<=1000;i++) { pow2[i] = (pow2[i-1]<<1) % MOD; inv[i] = mpow(i,MOD-2); } } long long comb(long long n,int m) { long long ans = 1; for(int i=0;i<m;i++) ans = ans*(n-i)%MOD; for(int i=1;i<=m;i++) ans = ans*inv[i]%MOD; return ans; }
int main() { init(); int n,m,v; while(scanf("%d%d%d",&n,&m,&v),n) { f[0] = (v==0); f[1] = 1; //f[m] = 1/m(comb(2^n,m-1) - (2^n - (m-2))*f[m-2]) for(int i=2;i<=m;i++) { f[i] = (comb(pow2[n],i-1) - (pow2[n]-(i-2))*f[i-2]%MOD + MOD )%MOD; f[i] = f[i]*inv[i]%MOD; } printf("%lld\n",f[m]); } return 0; }
|
|
常用鏈接
隨筆分類
Links
搜索
最新評論

|
|