CF40E Number Table 题解

Doveqise · 2019-10-07 11:00:29 · 题解

来补模拟赛T3
这道题为什么是蓝的（
把模拟赛数据范围贴上来，方便分段解决

对于30%的数据，1 \leq n * m \leq 21 。
对于70%的数据，1 \leq n , m \leq 1000 。
其中有10%的数据，1 \leq n,m \leq 1000,k=0。
对于100%的数据，1 \leq n , m \leq 1000000 。

数据保证不会同一个格子填两次。

解法1：
暴力DFS。
得分：30pts

解法2：
特判n+m为奇数时答案显然为0。
证明：
我们把每一行和每一列的答案乘起来。
易得，这种行为等价于将每一个格子的数字平方再相乘。
但是每一行和每一列的答案相乘为-1，而后者为1。

得分：+10pts

解法3：
注意到k \lt max(n,m)，则必有一行或一列是完全空的。
不妨设空的为一行，显然其他行填完后，这行有且只有一种填法。
则问题转化为在一维上已经若干了多少个位置，有多少种合法填数情况。
假设某行一共s个位置，已经填好t个位置，可以想到使用线性方法填这一行，然后用乘法原理求出答案。
得分：70pts

解法4：
优化在一维上求解的方法。
借用解法3的概念，
若初始乘积为1，则k=0；
若初始乘积为0，则k=1；
不难发现一维上的方案数可写成 C^{s-t}_{k} + C^{s-t}_{k+2} +C^{s-t}_{k+4} + C^{s-t}_{k+6} + ……
不难发现答案为2^{s-t-1}。
得分：100pts

（记得JZ的OJ里面有一道这个题的加强版，n和m的范围扩大到了10^9，k为10^6，可惜自己的账号到期了QwQ就不能去交惹）

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
typedef long long ll;
ll T[maxn], N[maxn];
ll n, m, k, mod;
ll qpow(ll x, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b % 2)
            res = (res * x) % mod;
        x = (x * x) % mod;
        b >>= 1;
    }
    return res % mod;
}
signed main()
{
    scanf("%lld%lld%lld", &n, &m, &k);
    int swp = 0;
    if (n < m)
        swap(n, m), swp = 1;
    if ((n + m) % 2)
    {
        puts("0");
        return 0;
    }
    for (int i = 1; i <= n; i++)
        N[i] = 1;
    for (int i = 1, x, y, z; i <= k; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        if (swp)
            swap(x, y);
        T[x]++;
        N[x] *= z;
    }
    scanf("%lld", &mod);
    ll det = 0;
    for (int i = 1; i <= n; i++)
    {
        if (T[i] == m && N[i] == 1)
        {
            puts("0");
            return 0;
        }
        det += min(T[i], m - 1);
    }
    printf("%lld\n", qpow(2, 1ll * (n - 1) * (m - 1) - det));
    return 0;
}