Gym - 102470C Lights

Statement:

      $Givenv\in \{0,1{\}}^n,howmanysetsofmdistinctvectorsin\{0,1{\}}^{n}suchthat{v}_1\oplus v_2\oplus ...\oplus v_m=v(additionisbitwiseXOR).$

Solution:

      我们任意选择 $m-1$ 个向量$v_1,v_2,....v_{m-1}$,一定存在一个向量$v_m$让其异或和为$v$.但考虑到可能$v_m$和前$m-1$个向量的某个向量相同,我们考虑去除这一部分.       因为$v_m$与某个向量相同,即$v_m\oplus v_i=0$,我们不妨把这两个向量提出来,剩下的$m-2$个向量的异或和依旧为$v$,即选择$m-2$个向量的方案数.可以通过这种方式递推,最后求解.

      此外,我们发现$$\left(\genfrac{}{}{0ex}{}{m}{bi{t}_n}\right)中bi{t}_n很大.$$ 利用卢卡斯定理 $$\left(\genfrac{}{}{0ex}{}{m}{bi{t}_n}\right)modp=\left(\genfrac{}{}{0ex}{}{mmodp}{bi{t}_{n}modp}\right)\cdot \left(\genfrac{}{}{0ex}{}{\lfloor \frac{m}{p}\rfloor }{\lfloor \frac{bi{t}_n}{p}\rfloor }\right)$$

其中$\lfloor \frac{m}{p}\rfloor$为0,所以该部分为 1,结果等于前部分

Code:

#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <stack> #include <bitset> #include <vector> #include <map> #include <string> #include <cstring> #define fir first #define sec second using namespace std; typedef long long ll; const ll mod = 10567201; const int maxn = mod; ll bit[maxn],fac[maxn]; ll fast(ll a,ll b) { ll sum = 1; while(b) { if(b&1) sum = sum*a%mod; a = a*a %mod; b >>= 1; } return sum; } ll inv(int x) {return fast(x,mod-2);} ll C(int x,int y) { if(y > x) return 0; return fac[x] * inv(fac[y])%mod * inv(fac[x-y])%mod; } int n,m,v; ll solve(int n,int m,int v) { if(m == 0 || m == 1) { if(m == 1) return 1; if(m == 0) return v? 0:1; } ll res = C(bit[n],m-1); return (res %mod- (bit[n] - m+2 + mod) %mod * solve(n,m-2,v)%mod+mod)*inv(m)%mod; } int main() { bit[0] = fac[0] = 1; for(int i=1;i<=mod;i++) { bit[i] = (bit[i-1]<<1)%mod; fac[i] = (fac[i-1]*i)%mod; } while(scanf("%d%d%d",&n,&m,&v) && n && m ) { printf("%lld\n", solve(n,m,v)); } return 0; }