kcz 出的一道比赛题
第一次写带修改的线性基
ps: 我觉得我计数计的好麻烦
首先是这个可以认为第二个矩阵是 \(q\) 个 \(s\) 位数, 如果这 \(q\) 个数的线性基可以消掉 \(C\) 中每一行, 那么答案就应该是, 设线性基个数是 \(x\), 则应该是 \(2^{q - x}\) 随便选, 然后剩下的用线性基消掉即可, 所以系数是 \(2^{p(q - x)}\)(因为第一个矩阵有 \(p\) 行)
那么问题就来了, 我们要统计以下两个东西
1.\(q\) 个 \(s\) 位数组成 \(x\) 个线性基的方案数
2. 找到 \(x\) 个线性基, 这些线性基可以消掉 \(p\) 个给定的数的方案数, 线性基不同仅当它们组成的数字不同
第一个我们分两步, 按照我们加入线性基的思路来说, 设 \(dp[i][j]\) 为前 \(i\) 个数有 \(j\) 个线性基
为了方便, 这里分两步, 认为我们加入的线性基是固定的数, 然后再求出 \(j\) 个线性基有多少种不同的数字方案
所以就是如果要加入一个线性基, 就 \(dp[i][j] \rightarrow dp[i + 1][j + 1]\)
否则就是前 \(j\) 个线性基可以组成的数,\(2^{j}dp[i][j] \rightarrow dp[i + 1][j]\)
然后线性基有 \(j\) 个, 有多少种不同的数字能构成呢
就是 \((2^{j} - 2^{0})(2^{j} - 2^{1})(2^{j} - 2^{2})....(2^{j} - 2^{j - 1})\)
就是第一个数字有 \(2^{j} - 1\) 种选法, 第二个数字要减去第一个可以拼出来的......
然后我们把两个东西乘起来得到 \(f[x]\) 表示第一步的答案
设 \(p\) 个数字组成的线性基个数是 \(cnt\)
那么可以把 \(x\) 个线性基变成 \(x - cnt\) 个, 值域变成 \(2^{s - cnt}\)
这显然是等价的
我们如果选了 \(k\) 个, 则下一个的可选的个数是 \(2^{s - cnt} - 2^{k}\)
算完之后除去方案数即可 (因为等价的线性基会算重方案数那么多次)
最后再乘上系数 \(2^{p(q- x)}\) 即可
- #include <bits/stdc++.h>
- #define fi first
- #define se second
- #define pii pair<int,int>
- #define mp make_pair
- #define pb push_back
- #define space putchar(' ')
- #define enter putchar('\n')
- #define eps 1e-10
- #define ba 47
- #define MAXN 100005
- //#define ivorysi
- using namespace std;
- typedef long long int64;
- typedef unsigned int u32;
- typedef double db;
- template<class T>
- void read(T &res) {
- res = 0;T f = 1;char c = getchar();
- while(c <'0' || c> '9') {
- if(c == '-') f = -1;
- c = getchar();
- }
- while(c>= '0' && c <= '9') {
- res = res * 10 +c - '0';
- c = getchar();
- }
- res *= f;
- }
- template<class T>
- void out(T x) {
- if(x <0) {x = -x;putchar('-');}
- if(x>= 10) {
- out(x / 10);
- }
- putchar('0' + x % 10);
- }
- const int MOD = 1000000007;
- int p,q,s,m,k,pos[1005],cnt;
- bitset<1005> c[1005],fr[1005],rec[1005],nw;
- int dp[1005][1005],f[1005],pw[1005],g[1005],rf[1005];
- bool used[1005];
- int inc(int a,int b) {
- return a + b>= MOD ? a + b - MOD : a + b;
- }
- int mul(int a,int b) {
- return 1LL * a * b % MOD;
- }
- void update(int &x,int y) {
- x = inc(x,y);
- }
- int fpow(int x,int c) {
- int res = 1,t = x;
- while(c) {
- if(c & 1) res = mul(res,t);
- t = mul(t,t);
- c>>= 1;
- }
- return res;
- }
- void Insert(int t) {
- for(int j = 0 ; j <s ; ++j) {
- if(c[t][j]) {
- if(pos[j]) {
- c[t] ^= c[pos[j]];
- fr[t] ^= fr[pos[j]];
- }
- else {
- pos[j] = t;++cnt;used[t] = 1;break;
- }
- }
- }
- }
- void Calc() {
- for(int i = 1 ; i <= p ; ++i) {
- fr[i][i] = 1;
- Insert(i);
- }
- }
- int Getans() {
- memset(g,0,sizeof(g));
- g[cnt] = 1;
- for(int i = cnt + 1 ; i <= min(s,q) ; ++i) {
- g[i] = mul(g[i - 1],inc(pw[s - cnt],MOD - pw[i - cnt - 1]));
- }
- for(int i = cnt ; i <= min(s,q) ; ++i) {
- g[i] = mul(g[i],fpow(rf[i - cnt],MOD - 2));
- }
- int res = 0;
- for(int i = cnt ; i <= min(s,q) ; ++i) {
- int t = fpow(pw[q - i],p);
- update(res,mul(f[i],mul(g[i],t)));
- }
- return res;
- }
- void Modify(int l) {
- int t = -1,h = 0;
- for(int j = s - 1 ; j>= 0 ; --j) {
- if(fr[pos[j]][l]) {t = j;break;}
- }
- for(int i = 1 ; i <= p ; ++i) {
- if(!used[i]) {
- if(fr[i][l]) {h = i;break;}
- }
- }
- if(h) {
- for(int i = 1 ; i <= p ; ++i) {
- if(i != h && fr[i][l]) fr[i] ^= fr[h];
- }
- c[h] ^= nw ^ rec[l];
- Insert(h);
- }
- else if(t != -1){
- for(int j = t - 1 ; j>= 0 ; --j) {
- if(fr[pos[j]][l]) {
- fr[pos[j]] ^= fr[pos[t]];
- c[pos[j]] ^= c[pos[t]];
- }
- }
- int id = pos[t];
- c[id] ^= nw ^ rec[l];
- used[pos[t]] = 0;--cnt;
- pos[t] = 0;
- Insert(id);
- }
- rec[l] = nw;
- }
- void Solve() {
- read(p);read(q);read(s);read(m);read(k);
- int a;
- for(int i = 1 ; i <= p ; ++i) {
- for(int j = 0 ; j < s ; ++j) {
- read(a);
- c[i][j] = a;rec[i][j] = a;
- }
- }
- pw[0] = 1;
- for(int i = 1 ; i <= 1000 ; ++i) pw[i] = mul(pw[i - 1],2);
- dp[0][0] = 1;
- for(int i = 0 ; i <= q ; ++i) {
- for(int j = 0 ; j <= i ; ++j) {
- update(dp[i + 1][j + 1],dp[i][j]);
- update(dp[i + 1][j],mul(dp[i][j],pw[j]));
- }
- }
- for(int j = 0 ; j <= min(q,s) ; ++j) {
- rf[j] = 1;
- for(int k = 0 ; k < j ; ++k) {
- rf[j] = mul(rf[j],inc(pw[j],MOD - pw[k]));
- }
- f[j] = mul(rf[j],dp[q][j]);
- }
- Calc();
- int la = Getans();
- out(la);enter;
- int wz;
- for(int i = 1 ; i <= m ; ++i) {
- read(wz);wz ^= k * la;
- for(int j = 0 ; j < s; ++j) {
- read(a);nw[j] = a;
- }
- Modify(wz);
- la = Getans();
- out(la);enter;
- }
- }
- int main(){
- #ifdef ivorysi
- freopen("f1.in","r",stdin);
- #endif
- Solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3098911.html