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 $。
$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就不能去交惹）
代码如下：
```cpp
#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;
}
```