https://atcoder.jp/contests/abc273/tasks
G - Row Column Sums 2
求个数mod 998244353
nxn的矩阵, 元素非负整数
行i 和为ri
列i 和为ci
范围
n 5000
ri,ci [0,1,2]
3s
1024mb
我的思路
这 ri, ci很有说法,
显然 sum r == sum c
说明每行/列只有4种情况 全0,1个1,2个1,1个2
而全零的行列可以直接删掉
如果是一个2的情况, 那么显然对应到另一个2的
因此变成
一些 行列为2的成对 直接填2, 剩余的 只有 1个1 和2个1
行 (a个1,b个2)
列 (c个1,d个2)
选出 t个填2的行列
sum binom(b,t) * binom(d,t) * t!(其中行定,列匹配) * f(a,b-t,c,d-t)
因为上面枚举了t
希望能在小于O(N)的时间 算出 f(a,b,c,d) = 行(a个1,b个2) 列(c个1,d个2) 全部拆成1和1+1的方案
注意到a,c 不变 考虑最小的b,d 比如f(a,b,c,0)的情况, 比较好算, = c!/(c-a)! * binom(2b,2) * binom(2b-2,2) * binom(2b-4,2) …
然后考虑 每次b和d增1
1 2 3 4
| 1 1 1 1 1 1 2 a j b 2 i x
|
如果这增的两个选了, 那么4种情况
对应原来一种情况, 是原来一个(1,1) 指向的
1 2 3 4 5 6 7
| 1 2 1 j 2 i x ```
对应原来一种情况, 是原来一个(1,2) 或(2,1) 指向的
|
1 2
2 1 j
2 i x
1 2 3 4 5 6 7 8
| 对应原来一种情况, 是原来一个(2,2) 指向的
```` 2 2 1 2 1 j 2 i x
|
对应 [b-2][d-2]
的情况 前面还插入了两个
f[b][d] = f[b-1][d-1] * (a+2*(b-1)) + f[b-2][d-2] * (d-1)*(b-1)
然后考虑说 新增的没有共点 ???????????????????????????????????
上面 看起来是二维, 然而实际上b和d的差为定值, 所以是个一维的
diff=d-b >= 0
f[b] = f[b-1] * (a+2*b) + f[b-2] * (b+diff-1)*(b-1)
但是不共点的情况 咋讨论啊, 感觉好多啊, 不会了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| 1 1 11
1 11 11
1 1 1 11
1 1 11 11
11 1 11
1 1 1 11
11 1 1 11
|
难道 对 这种2x2 的形态进行计数, f[i][状态=6]
?