P10681 [COTS 2024] 奇偶矩阵 Tablica
题意
有一个 \(n \times m\) 的 \(01\) 矩阵，问有多少种填 \(01\) 的方式，满足同一行、列恰好有 \(1\) 或 \(2\) 个 \(1\)。
\(n,m \le 3000\)。
思路
首先一个显然的 \(O(nm^2)\) 做法：
设 \(f_{i,s0,s1}\) 表示考虑到第 \(i\) 行，目前有 \(s0\) 列有 \(0\) 个 \(1\)，有 \(s1\) 列有 \(1\) 个 \(1\)，的方案数。
转移分 \(5\) 种，讨论第 \(i+1\) 行填几个 \(1\)，以及在 \(s0\) 还是 \(s1\) 那里选 \(1\)。
就是酱子：
int w = f[i][s0][s1];
if (s0)
_add(f[i + 1][s0 - 1][s1 + 1], mul(s0, w)),
_add(f[i + 1][s0 - 1][s1], mul(w, mul(s0, s1)));
if (s1)
_add(f[i + 1][s0][s1 - 1], mul(s1, w));
if (s0 >= 2)
_add(f[i + 1][s0 - 2][s1 + 2], mul(w, 1ll * s0 * (s0 - 1) / 2 % mod));
if (s1 >= 2)
_add(f[i + 1][s0][s1 - 2], mul(w, 1ll * s1 * (s1 - 1) / 2 % mod));
好像 DP 状态不好再减了。
所以考虑不要一行行转移了，直接组合计数。
学习了 yyyyxh 大佬的题解。
枚举有 \(x_1\) 行恰好有 \(1\) 个 \(1\)，那么有 \(x_2 = n-x_1\) 恰好有 \(2\) 个 \(1\)。
那么所有列加起来 \(1\) 的个数 \(y_1+2y_2 = x_1+2x_2\)，所以可以直接求出 \(y_1,y_2\)。
问题就是有 \(m\) 种球，其中 \(y_1\) 种各有 \(1\) 个，\(y_2\) 种各有 \(2\) 个。有 \(n\) 个桶，其中 \(x_1\) 个容量为 \(1\)，\(x_2\) 个容量为 \(2\)。问有多少种放球方式，满足每个桶都放满，且一个桶里不能放两个同一种球。
桶和球的种类都是有编号的，但是编号不影响计数，所以答案乘上组合数 \(\binom{n}{x_1} \binom{m}{y_1}\) 即可。
一个错误答案是 \((y_1+2y_2)!\)。
有两个难处理的问题：
- 两个同种球是无序的，容量为 \(2\) 的桶里面两个球也是无序的。
- 一个桶不能放两个同种球。
情况 \(1\) 我们就对答案乘上 \(\frac{1}{2^{x_2+y_2}}\)。
情况 \(2\) 考虑容斥。外层只有枚举的 \(O(\min(n,m))\) 复杂度，所以放心容斥。
具体地，就是随便放 \(-\) 钦定一个容量为 \(2\) 的桶放两个一样的球 \(+\) 钦定两个容量为 \(2\) 的桶放两个一样的球……
钦定的方案数就是除去那几个行和列，剩下随便放的方案数。
即
\[\sum_{k=0}^{\min(x_2,y_2)} \binom{x_2}{k} \binom{y_2}{k} k! (-1)^k \frac{(y_1+2y_2-2k)!}{2^{x_2+y_2-2k}} \]\(k!\) 是计算每个钦定的桶对应什么种类的球。
这对吗？实际上是错的，如果有两个同种球被放在一个桶里的情况，直接算排列只是多算了 \(1\) 次，而你以为有 \(3\) 次都是多算的。所以当你钦定这两个同种球必须在一个桶里的时候，需要把多减的加回来。就是说容斥要带系数 \(2^k\)，体现在分母那里变成 \(2^{x_2+y_2-k}\)。
总的式子就是：
\[\sum_{x_1+x_2=n, y_1+y_2=m, x_1+2x_2=y_1+2y_2} \binom{n}{x_1} \binom{m}{y_1} \sum_{k=0}^{\min(x_2,y_2)} \binom{x_2}{k} \binom{y_2}{k} k! (-1)^k \frac{(y_1+2y_2-2k)!}{2^{x_2+y_2-k}} \]\(\binom{x_2}{k} \binom{y_2}{k} k! (-1)^k \frac{(y_1+2y_2-2k)!}{2^{x_2+y_2-k}}\) 算出来是小数，很反直觉。大概是容斥容的。
复杂度 \(O(\min(n,m)^2)\)。
code
好难。
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace hesitate {
constexpr int N=6e3+7,Max=6e3,mod=1e9+7;
int add(int a,int b) { return a+b>=mod ? a+b-mod : a+b; }
void _add(int &a,int b) { a=add(a,b); }
int mul(int a,int b) { return 1ll*a*b%mod; }
void _mul(int &a,int b) { a=mul(a,b); }
int ksm(int a,int b=mod-2) {
int s=1;
while(b) {
if(b&1) _mul(s,a);
_mul(a,a);
b>>=1;
}
return s;
}
int fac[N],ifac[N],mi[N],imi[N];
void init() {
fac[0]=mi[0]=1;
rep(i,1,Max) fac[i]=mul(fac[i-1],i);
rep(i,1,Max) mi[i]=add(mi[i-1],mi[i-1]);
ifac[Max]=ksm(fac[Max]);
per(i,Max-1,0) ifac[i]=mul(ifac[i+1],i+1);
imi[Max]=ksm(mi[Max]);
per(i,(Max)-1,0) imi[i]=add(imi[i+1],imi[i+1]);
}
int c(int n,int m) { return mul(fac[n],mul(ifac[m],ifac[n-m])); }
int n,m;
int ans;
void main() {
init();
sf("%d%d",&n,&m);
rep(x1,0,n) {
int x2=n-x1,y2=x1+(x2<<1)-m,y1=m-y2;
if(y2<0 || y1<0) continue;
int s=0;
rep(k,0,min(x2,y2)) {
int sum= (k&1) ? mod-1 : 1;
_mul(sum,mul(mul(c(x2,k),c(y2,k)),fac[k]));
_mul(sum,mul(fac[y1+(y2<<1)-(k<<1)],imi[x2+y2-k]));
_add(s,sum);
}
_mul(s,mul(c(n,x1),c(m,y1)));
_add(ans,s);
}
pf("%d\n",ans);
}
}
int main() {
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("my.out","w",stdout);
#endif
hesitate :: main();
}