【bzoj5481】矩阵

Source

bzoj5481

Hint

请先思考后再展开

如果两行在同一位置都是1,连一条边

Solution

请先思考后再展开

这是若干个环,然后我们考虑图的形状计数,最后把n个列分配到边上
$ans=\sum_{n=1}^N n!g_n$
然后考虑最后一行所在的行
$g_n=\si,{i=2}^n g{n-i} \times T_i \times C_{n-1}^{i-1}$
这里 $Ti=\frac{i!}{2i}$ 表示一个大小为i的环的形状数
然后把组合数化开,发现可以前缀和优化转移,故线性

oj垫底……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void main()
{
fac[0]=fac[1]=inv[1]=facinv[0]=facinv[1]=1;
int N=qread(),ans=0;g[0]=1;f[0]=f[1]=1;
for(int n=2;n<=N;n++)
{
fac[n]=(ll)fac[n-1]*n%MOD;
if(n>1) inv[n]=ll(MOD-MOD/n)*inv[MOD%n]%MOD;
facinv[n]=(ll)facinv[n-1]*inv[n]%MOD;
g[n]=(ll)f[n-2]*fac[n-1]%MOD*inv[2]%MOD;
f[n]=(f[n-1]+(ll)g[n]*facinv[n]%MOD)%MOD;
add(ans,(ll)g[n]*fac[n]%MOD);
}
write(ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/a44d.html
转载请注明出处,谢谢!