CF40E Number Table

原题

Solution

这是个计数题。

我直接正难则反

我们观察题面，发现一个很重要的条件 (k< max{n,m}) ，我们这里设 (n>m) ，那么也就是如果填入的每个数都不同行，也会有一行是空出来什么都没有的。

我艸，妙啊

继续想，这一行是空的，别的行需要满足乘积为 (-1) 。

列是不需要考虑的，因为别的列可以通过这个空着的列满足乘积为 (-1) 。而这空着的这一行也因为别的都是 (-1) ，它自己也得是 (-1) 。

此时每行乘起来为 ((-1)^n) ，每列为 ((-1)^m) ，如果 (n,m) 奇偶性不一样，直接判无解。

就这？

因为要满足每一行乘积为 (-1) ，所以将每一行分开考虑：

1. 这一行还没填满，那么除了某一个位置，剩下的位置随便填，最后剩的位置用来使这一行乘积为 (-1) ，则答案为 (2^{m-cnt-1}) ，其中 (cnt) 为这一行填着的位置数。
2. 这一行是填满的，如果乘积为 (1) ，判无解。否则跳过。

这个时间复杂度是 (O(n)) 的。

Code

#include<bits/stdc++.h>

using namespace std;
const int N=1005;
int n,m,k,p,pow2[N],cnt[N],mul[N],ans=1;
bool is_change;

int main(){
    scanf("%d%d%d",&n,&m,&k);
    if(n<m) swap(n,m),is_change=true;
    for(int i=1;i<=n;i++) mul[i]=1;
    for(int i=1,x,y,v;i<=k;i++){
        scanf("%d%d%d",&x,&y,&v);
        if(is_change) swap(x,y);
        cnt[x]++,mul[x]*=v;
    }
    scanf("%d",&p);
    if((n&1)!=(m&1)){
        puts("0");
        return 0;
    }
    pow2[0]=1;
    for(int i=1;i<=n;i++)
        pow2[i]=(pow2[i-1]*2)%p;
    for(int i=1;i<n;i++)
        if(!cnt[i]){
            swap(cnt[i],cnt[n]);
            swap(mul[i],mul[n]);
            break;
        }
    for(int i=1;i<n&&ans;i++){
        if(cnt[i]==m){
            if(mul[i]==1) ans=0;
        }
        else ans=ans*1ll*pow2[m-cnt[i]-1]%p;
    }
    printf("%d
",ans);
    return 0;
}