/* 题意: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
搜索
最新评论

|
|