夕张的改造[FJWC2020Day4]

发表于 分类于 ，

链接

jzoj

题意

提督们惊奇地发现，2019 年实装的改造非常少。

经调查，原来是改造厂的厂长于八日克扣了其他舰娘改造的图纸，并且在 2020 年的第一个月利用这些图纸进行了华丽的改造，一共有三种形态，于八日改二，于八日改二特，于八日改二丁，对空、对陆、对潜、开幕雷、五装备格，无所不能。镇守府雪菜八万钢惨遭退役。

舰娘的结构可以看成一棵 $n$ 个点的树，点编号为 $0 \sim n−1$。使用一张图纸可以把树中的某一条边去掉，再加上一条边，使得它依然是一棵树。

现在，于八日想在 2020 年继续拿走别的舰娘的图纸对自己进行改造，她一共拿走了 $k$ 张图纸。她想知道，自己经过接下来的改造之后，总共会有多少种形态。两个形态不同，表示有一条边 $(x,y)$ 在第一棵树中出现，在另一棵树中不出现。

$k\leq n\leq 50$

题解

这题还挺简单的。。。

刚开始在想树形DP，结果毫无思路，那么剩下的就只有矩阵树定理了。

题目实际上要求的是至多有不超过 $k$ 条边不出现在原树中的生成树。

我们知道，矩阵树定理求的是生成树的边权的乘积。

那么对于所有不在原树的边，边权为 $x$，否则为 $1$。求出来的行列式是一个 $n-1$ 次多项式。

然后想到暴力算多项式乘法，时间复杂度 $O(n^5)$。（应该过不了）

哪有人这么蠢的。既然是一个多项式，那么把 $x=1,2\cdots n$ 代进去，算出来后暴力拉格朗日差值就好了。

时间复杂度 $O(n^4)$。

程序

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const ll mod=998244353;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
   y%=(mod-1);ll f=1;for(;y;y>>=1,x=x*x%mod)if(y&1) f=f*x%mod;
   return f;
}
const int N=55;
int n,m;
ll a[N][N];
bool bo[N][N];
inline ll guass(int n)
{
	ll ans=1,tmp;
	ff(i,0,n)
	{
		int j=-1;
		ff(k,i,n) if(a[k][i]) {j=i; break;}
		if(j==-1) return 0;
		if(j!=i)
		{
			ans=mod-ans;
			ff(k,i,n) swap(a[j][k],a[i][k]);
		}
		ff(j,i+1,n)
		{
			tmp=Pow(a[i][i],mod-2)*a[j][i]%mod;
			ff(k,i,n) a[j][k]=Dec(a[j][k],tmp*a[i][k]%mod);
		}
	}
	ff(i,0,n) ans=Mul(ans,a[i][i]);
	return ans;
}
inline ll calc(int x)
{
	ff(i,0,n) ff(j,0,n) a[i][j]=0;
	int v;
	ff(i,0,n)
		ff(j,i+1,n)
		{
			v=bo[i][j]?1:x;
			a[i][j]-=v; a[j][i]-=v;
			a[i][i]+=v; a[j][j]+=v;
		}
	ff(i,0,n) ff(j,0,n) a[i][j]=(a[i][j]+mod)%mod;
	return guass(n-1);
}
ll h[N],f[N],g[N];
int main()
{
	n=read(); m=read();
	int x;
	ff(i,1,n)
	{
		x=read();
		bo[x][i]=bo[i][x]=1;
	}
	fo(i,1,n)
	{
		ll tmp=calc(i),d;
		fo(j,0,n) g[j]=0;
		g[0]=1;
		fo(j,1,n) if(j!=i)
		{
			tmp=Mul(tmp,(i<j)?(mod-Pow(j-i,mod-2)):Pow(i-j,mod-2));
			fo(k,0,n)
			{
				h[k]=Mul(mod-j,g[k]);
				if(k) h[k]=Add(h[k],g[k-1]);
			}
			fo(k,0,n) g[k]=h[k],h[k]=0;
		}
		fo(j,0,n) f[j]=Add(f[j],Mul(g[j],tmp));
	}
	ll sum=0;
	fo(i,0,m) sum=Add(sum,f[i]);
	printf("%lld",sum);
	return 0;
}