Doveqise

Doveqise

万事皆虚,诸行皆允

CF40E Number Table 题解

posted on 2019-10-07 11:00:29 | under 题解 |

来补模拟赛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 $ 。
$0 \leq k \leq max(n,m)$ ,
$1 \leq a \leq n,1\leq b \leq m, c \in \{1,-1\} ,$
$2 \leq p \leq 10^9+7,$
数据保证不会同一个格子填两次。

解法1:
暴力 $DFS$ 。
得分:30pts

解法2:
特判 $n+m$ 为奇数时答案显然为0。
证明:
我们把每一行和每一列的答案乘起来。
易得,这种行为等价于将每一个格子的数字平方再相乘。
但是每一行和每一列的答案相乘为-1,而后者为1。
$Q.E.D.$
得分:+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;
}