列表

详情


NC200174. Ranks

描述

A finite field F_2 consists of two elements: 0 and 1. Addition and multiplication on F_2 are those on integers modulo two, as defined below.
A set of vectors over F_2 with the same dimension is said to be linearly independent when, for , is equivalent to , where 0 is the zero vector, the vector with all its elements being zero.
The rank of a matrix is the maximum cardinality of its linearly independent sets of column vectors. For example, the rank of the matrix is two; the column vectorsand (the first and the third columns) are linearly independent while the set of all three column vectors is not linearly independent. Note that the rank is zero for the zero matrix.
Given the above definition of the rank of matrices, the following may be an intriguing question. How does a modification of an entry in a matrix change the rank of the matrix? To investigate this question, let us suppose that we are given a matrix A over F_2. For any indices i and j, let be a matrix equivalent to A except that the (i,j) entry is flipped.

In this problem, we are interested in the rank of the matrix . Let us denote the rank of A by r, and that of by . Your task is to determine, for all (i,j) entries, the relation of ranks before and after flipping the entry out of the following possibilities: (i) , (ii) , or (iii) .

输入描述

The input consists of a single test case of the following format.
n m

. . .
n and m are the numbers of rows and columns in the matrix A, respectively . In the next n lines, the entries of A are listed without spaces in between. is the entry in the i-th row and j-th column, which is either 0 or 1.


输出描述

Output n lines, each consisting of m characters. The character in the i-th line at the j-th position must be either - (minus), 0 (zero), or + (plus). They correspond to the possibilities (i), (ii), and (iii) in the problem statement respectively.

示例1

输入:

2 3 
001 
101

输出:

-0-
-00

示例2

输入:

5 4
1111
1000
1000
1000
1000

输出:

0000
0+++
0+++
0+++
0+++

示例3

输入:

10 10
1000001001
0000010100
0000100010
0001000001
0010000010
0100000100
1000001000
0000010000
0000100000
0001000001

输出:

000-00000-
0-00000-00
00-00000-0
+00000+000
00-0000000
0-00000000
000-00000-
0-000-0-00
00-0-000-0
+00000+000

示例4

输入:

1 1 
0

输出:

+

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 328ms, 内存消耗: 6492K, 提交时间: 2020-10-04 15:27:08

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef double db;
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define low(x) ((x)&-(x))
#define all(x) x.begin(),x.end()
#define mp make_pair
#define X first
#define Y second
#ifdef _DEBUG
const int N=1e3+10;
#else
const int N=1e6+10;
#endif
const ll mod=1e9+7;
template<typename T> inline T gcd(T a, T b) {
    return !b?a:gcd(b, a%b);
}
template<typename T> inline T q_pow(T a, T x) {
    T ans=1, tmp=a;while (x) {
        if (x&1)(ans*=tmp)%=mod;(tmp*=tmp)%=mod;x>>=1;
    }return ans;
}
template<typename T> inline void re(T &N) {
    int f=1;char c;while ((c=getchar())< '0'||c> '9')if (c=='-')f=-1;N=c-'0';while ((c=getchar())>='0'&&c<='9')N=N*10+c-'0';N*=f;
}
int m, n, t=1, st, en;
struct Xor {
    vector<bitset<1001>>v;
    vector<int>p;
    void init(int n) {
        v.resize(n+1);p.assign(n+1, 0);
    }
    void insert(bitset<1001> x, int up)
    {
        int pos=0;
        for (int i=up;i<=m;i++)if (x[i])
        {
            if (p[i])x^=v[i];
            else if (!pos)pos=i;
        }
        if (pos)
        {
            v[pos]=x;p[pos]=1;
            for (int i=pos-1;i>=1;i--)
                if (v[i][pos])v[i]^=x;
        }
    }
    void filter(bitset<1001> &x)
    {
        for (int i=1;i<=m;i++)
            if (x[i]&&p[i])x^=v[i];
    }
    inline int judge(bitset<1001> &x, int pos)
    {
        if (p[pos])x^=v[pos];x[pos].flip();
        int ans=x.count();
        if (p[pos])x^=v[pos];x[pos].flip();
        return ans;
    }
};
bitset<1001>a[1010];
char s[1010][1010];
struct SegT {
    Xor d[20];
    vector<bitset<1001> >e[4010];
    void update(int p, int l, int r, int L, int R, bitset<1001> &k)
    {
        if (L<=l&&r<=R)
        {
            e[p].push_back(k);
            return;
        }
        int mid=(l+r)>>1;
        if (L<=mid)update(ls(p), l, mid, L, R, k);
        if (mid< R)update(rs(p), mid+1, r, L, R, k);
    }
    void query(int p, int l, int r, int dep)
    {
        d[dep]=d[dep-1];
        for (auto &it:e[p])
            d[dep].insert(it, 1);
        if (l==r)
        {
            d[dep].filter(a[l]);
            int ty=a[l].count();
            for (int i=1;i<=m;i++)
            {
                int now=d[dep].judge(a[l], i);
                if (ty)putchar(now?'0':'-');
                else putchar(now?'+':'0');
            }
            puts("");
            return;
        }
        int mid=(l+r)>>1;
        query(ls(p), l, mid, dep+1);
        query(rs(p), mid+1, r, dep+1);
    }
}tr;
int main()
{
    // freopen("data.txt","r",stdin);
    // freopen("out1.txt","w",stdout);
    re(n);re(m);
    for (int i=1;i<=n;i++)scanf("%s", s[i]+1);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            a[i][j]=s[i][j]-'0';
    for (int i=1;i<=n;i++)
    {
        if (i> 1)tr.update(1, 1, n, 1, i-1, a[i]);
        if (i< n)tr.update(1, 1, n, i+1, n, a[i]);
    }
    for (int i=0;i< 20;i++)
        tr.d[i].init(m);
    tr.query(1, 1, n, 1);
}

C++11(clang++ 3.9) 解法, 执行用时: 188ms, 内存消耗: 5112K, 提交时间: 2020-10-04 12:17:17

#include<bits/stdc++.h>
using namespace std;const int N=1007;typedef bitset<N> bit;bit zero,A[N];int n,m,i,j,k;char s[N],ans[N][N];struct LB{bit a[N];void ins(bit x){int i,j;for(i=m;i>=1;--i)if(x[i])if(a[i][i])x^=a[i];else {a[i]=x;break;}if(!i)return;for(j=1;j<i;++j)if(a[i][j])a[i]^=a[j];for(j=i+1;j<=m;++j)if(a[j][i])a[j]^=a[i];}bit query(bit x){for(int i=m;i>=1;--i)if(x[i])x^=a[i];return x;}}S;void fuck(int l,int r,LB S){if(l==r){bit tmp=S.query(A[l]),tmp2;int x=(tmp==zero)-1,y,i;for(i=1;i<=m;++i){tmp2=S.a[i];tmp2.flip(i);y=x+(tmp!=tmp2);ans[l][i]=y?(y>0?'+':'-'):'0';}return;}int mid=l+r>>1;LB tmp=S;for(int i=l;i<=mid;++i)tmp.ins(A[i]);fuck(mid+1,r,tmp);tmp=S;for(int i=mid+1;i<=r;++i)tmp.ins(A[i]);fuck(l,mid,tmp);}int main(){for(scanf("%d%d",&n,&m),i=1;i<=n;++i)for(scanf("%s",s+1),j=1;j<=m;++j)A[i][j]=s[j]-'0';fuck(1,n,S);for(i=1;i<=n;++i)puts(ans[i]+1);}

上一题