这是一道做法显然的状压DP
先看题意, 题目让我们求使得一个已有 k 个点被钦定的nm01矩阵各行各列异或和皆为1的方案数。
有一个数据 n 、m奇偶性不同，用PY想想就知道答案显然为零。
1. 最 naive 的想法，状压一维，扫另一维，问题就可以在 nm2min(n,m) 的时间内求解。
台下的吃瓜群众们：“然而无论是 n 还是m都达到了 105 的数量级，怎么破？”
2. 是时候考察 k 了。我们发现k始终 ⩽10m(n) ，由抽屉原理可得存在一列，其的被钦定点数 ⩽10 ，不妨取被钦定点数最小的一列 x ，被钦定点数为p，那么除这p行以外的行最终都可以由第 x 列下的自由格纠正异或值。到此为止，我们已经把行数的数量级降到了10以内。
那列的数量级如何缩小呢？
3. 我们找出所有列构成 B 使得每一列都存在那p列以外的自由格，那么无论其他格如何操作，都预留一个自由格来进行最后的纠正，那么 B 中每一列对答案乘数的贡献是2那p列之外自由格数−1。那么那p列之中呢？我们发现我们可以一并计算这 |B|+1 列在那 p 行中分别异或成0或 1 的方案数，然后DP那p行和剩下的列就可以了。由于剩下的列里都至少有 n−p≈n 格被钦定，所以这些列的总数不超过 kn ,总复杂度为 O(预处理(大概是n+m+k)+k2nm∗2km) 。
#include<cstdio> #include<cmath> #include<algorithm> #include<iostream> #include<assert.h> #include<cstring> #include<vector> using namespace std; #define re_ return #define in_ inline #define st_ static #define op_ operator #define co_ const #define ct_ continue #define br_ break #define tp_ template #define tn_ typename #define gc() getchar() #define inc(l, i, r) for(i=l; i<r; ++i) #define dec(r, i, l) for(i=r; i>l; --i) #define mp(a, b) make_pair(a, b) #define fr_ first #define sc_ second #define let(a, b) st_ ll a; a=b typedef long long ll; tp_<tn_ x> in_ ll mxe(x& a, x b) {re_ a<b?(a=b, 1):0;} tp_<tn_ x> in_ ll mne(x& a, x b) {re_ a>b?(a=b, 1):0;} struct io { in_ ll op_ !(void) { st_ ll s, r, c; for(s=1, r=0; (c=gc())<48||57<c;) if(c=='-') s=-1; for(;c>47&&58>c; c=gc()) r=10*r+c-48; return s*r; } in_ io& op_ & (ll& a) {re_ a=!(*this), *this;} in_ io& op_ | (co_ char* s) {re_ printf("%s", s), *this;} in_ io& op_ | (ll a) {re_ printf("%I64d ", a), *this;} in_ io& op_ ^ (ll a) {re_ printf("%I64d\n", a), *this;} } jio; co_ ll mxn=100001, mxm=200002, mxk=2000002, mod=998244353; bool cvr[mxn]; ll n, nn, m, anum[mxn], acnt[66], apos[66][2], acol[66], tb, bline[mxm], mm, cline[mxm], c[30][30], cxor[66], f[30][13][1<<10][2]; vector<pair<ll, ll> > fxd[mxm]; in_ ll pw0(ll a, ll b) { st_ ll r; for(r=1; b; a=a*a%mod, b>>=1) b&1?r=r*a%mod:0; re_ r; } in_ ll pw(ll b) { st_ ll r, a; for(r=1, a=2; b; a=a*a%mod, b>>=1) b&1?r=r*a%mod:0; re_ r; } int main() { freopen("matrix2.in", "r", stdin); freopen("1.out", "w", stdout); ll i, j, k, l, x, ans=1; if(jio&n, n==2333) re_ jio^0, 0; jio&m&k; inc(0, i, k) jio&x&l&j, fxd[l].push_back(mp(x, j)); //--------------------------------------------- #define siz(i) fxd[i].size() #define yco(i, j) fxd[i][j].fr_ #define col(i, j) fxd[i][j].sc_ inc((x=1, 2), i, m+1) if(siz(i)<siz(x)) x=i; nn=siz(x); inc(0, i, nn) anum[yco(x, i)]=i+1; inc(1, i, m+1) if(i^x) { inc(k=0, j, siz(i)) k+=anum[yco(i, j)]>0; if((l=n-nn-siz(i)+k-1)>=0) bline[tb++]=i, ans=ans*pw(l)%mod; else cline[mm++]=i; } //--------------------------------------------- inc(1, i, nn+1) acol[i]=col(x, i-1); inc(0, i, tb) { let(bi, bline[i]); inc(0, j, siz(bi)) { cvr[k=anum[yco(bi, j)]]=1; if(k) acol[k]^=col(bi, j); } inc(1, j, nn+1) { if(!cvr[j]) ++acnt[j]; } inc(0, j, siz(bi)) cvr[anum[yco(bi, j)]]=0; } inc(1, i, nn+1) if(acnt[i]) apos[i][0]=apos[i][1]=pw(acnt[i]-1); else apos[i][acol[i]]=1; //--------------------------------------------- inc(0, i, mm) { let(ci, cline[i]); cxor[i+1]=0; inc(0, j, siz(ci)) if(k=anum[yco(ci, j)]) c[i+1][k]=col(ci, j)+1; else cxor[i+1]^=col(ci, j); } f[1][0][0][cxor[1]]=1; inc(1, i, mm+1) { #define upd(a, b) (a=(a+(b))%mod) #define updf(a) upd(a, f[i][j-1][k][l]) inc(1, j, nn+1) inc(0, k, 1<<nn) inc(0, l, 2) { if(c[i][j]<2) updf(f[i][j][k][l]); if(c[i][j]!=1) updf(f[i][j][k^1<<j-1][l^1]); } ll a=0; inc(0, k, 1<<nn) f[i+1][0][k][cxor[i+1]]=f[i][nn][k][1]; } inc(l=0, k, 1<<nn) { inc((j=f[mm+1][0][k][0], 1), i, nn+1) j=j*apos[i][k>>i-1&1^1]%mod; l+=j; } jio^l*ans%mod; re_ 0; } //记得取模