Wannafly Winter Camp 2020 Day 5J Xor on Figures

有一个\(2^k\cdot 2^k\) 的全零矩阵 \(M\)，给出 \(2^k\cdot 2^k\) 的 \(01\) 矩阵 \(F\)，现在可以将 \(F\) 的左上角置于 \(M\) 的任一位置（超出部分就循环，\(2^k\) 的下一个就是 \(1\)），然后相应位置相异或。现在可以执行任意次以上操作：将 \(F\)放于某个位置，执行对应的异或操作。问最后不同的 \(M\)有多少个。

Solution

很显然我们可以 \(F\) 放在每一个位置的异或结果都算出来，放在一起，变成一个集合，那么最终的答案就是这个集合内的元素相互异或，有多少种不同的结果。

把它压成一个串，这样每个结果就是一个向量。把它们视作一个向量组，那么在异或的意义下，设它的秩是 \(r\)，则答案显然是 \(2^r\)

求线性基，搬运一个板子，把 int 换成 bitset 即可

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 1e9+7;

int n;

char s[35][35];

int a[35][35],b[35][35];

struct linear_base {

    bitset <1024> a[1024];

    void insert(bitset<1024> k) {

        for(int j=1023; j>=0; --j)

            if((k>>j)[0])

                if(a[j]==0) {a[j]=k;break;}

                else k^=a[j];

    }

    int count() {

        int ans=0;

        for(int i=0;i<1024;i++) if(a[i]!=0) ++ans;

        return ans;

    }

} lb;

signed main() {

    scanf("%d",&n);

    for(int i=1;i<=(1<<n);i++) {

        scanf("%s",s[i]+1);

    }

    for(int i=1;i<=(1<<n);i++) {

        for(int j=1;j<=(1<<n);j++) {

            a[i][j]=s[i][j]-'0';

        }

    }

    for(int i=1;i<=(1<<n);i++) {

        for(int j=1;j<=(1<<n);j++) {

            bitset<1024>x;

            for(int k=1;k<=(1<<n);k++) {

                for(int l=1;l<=(1<<n);l++) {

                    b[k][l]=a[(k+i-2)%(1<<n)+1][(l+j-2)%(1<<n)+1];

                    x[k*(1<<n)-k+l-1]=b[k][l];

                }

            }

            lb.insert(x);

        }

    }

    int t=lb.count();

    int ans=1;

    for(int i=1;i<=t;i++) ans*=2,ans%=mod;

    cout<<ans;

}

巴特西

Wannafly Winter Camp 2020 Day 5J Xor on Figures - 线性基,bitset

Solution

最新文章

热门文章