杭电多校-Counting Stickmen-(思维+组合数+容斥)

Counting Stickmen

题意：
就是给你一个树，然后让你找出有多少个人形状的方案。由于方案数很大对mod取模。

红色标注的就是的，就是2是头，3是脖子，5是身体，7和8是两个腿,4 6是其中一个手，9 10是另一个手。

思考：
1.比赛刚开始我就看了下这题，但是看到取模后，感觉树上取模的问题都不简单，就没看了。等把简单题过完就看了下这题。然后思考了一下，如果我遍历树的时候，枚举到now点了，那么我可以让now当脖子，now父亲当头，然后从儿子里选取两个子树作为手臂再选一个子树作为身子就可以了。
2.比如now有7个儿子，我把每个儿子当手臂的时候有多少方案数，当身子的时候有多少种方案数分别为sum1[i],sum2[i]。这个好求，就是对于i看看有多少儿子，然后当手方案就是从儿子个数中选一个。身体的话是从儿子个数中选两个。
3.处理出来之后呢？那么就要选手臂了，到底选那两个子树当手臂？这个如果暴力枚举n×n的复杂度不行。所以我就想先枚举选哪个子树当身子，这个就是枚举一遍看看选哪个子树当身子。比如选a当身子，那么要从剩下的子树中选两个当手臂，这该怎么办呢？也就是选的手臂不能是a这个子树了，那么就想到了容斥。我可以先把任选两个当手臂的总方案数求出来(如果暴力枚举两个点这样还是n×n，任选两个其实是选这个点以及他后面的，不能再看前面的了，这样就重复了，既然是看后面的，就维护一个后缀和倒着处理就好了)，然后不能选a子树作为手臂的情况就是 = 总方案数-选a子树作为手臂的方案数。 选a子树作为手臂的方案数 = sum1[a]*(sum1的总和-sum1[a])。所以选择一个身子和选择两个手的总方案数就可以遍历一遍求出来了。头就是当前now点的父亲。
4.当我正想写的时候，发现，没给我说根是谁。这我该怎么遍历呢，我从哪开始跑呢？因为我从不同的点开始跑我枚举的时候就不一样了，儿子就不一样了。所以我就感觉不行，这样做不了了。但是于说，也不用管那么多，答案不会变。确实，这个图形永远都是这样，但是我还是不知道该怎么搜。
5.因为我的思路就是，当我枚举到这个点的时候，我就让他当脖子，下面的儿子子树去当手臂和身子。但是不给我根，我不知道枚举的顺序到底该怎么样。这里卡了一会，然后于说，可以枚举每个点作为脖子，然后手臂和腿会用掉3个子树，那么剩下的子树就可以当成头。说到这里，我就感觉差不多了，就是这样的。这样也不会有重复，因为你的脖子不一样，不同的脖子肯定是不同的方案数。
6.其实我就陷入了那种是树就要按树跑的思维里面去了，就感觉这个顺序要固定住从根开始搜这样答案才是正确的。其实不然，这只是一个图罢了，树就是没有环的图。如果这个题给我说是个图，也许不会陷入那种思维了。
7.记得开IOS，没开当时就超时了罚时了一发。对于到达1e6输入的题目，必须要开IOS或者用scanf了。

代码：

#include
#define int long long
#define pb push_back
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;

const int N = 5e5+10,mod = 998244353;

int T,n,m;
int in[N];
int va[N],cnt;
int sum1[N],sum2[N];
int pre[N];

int fact[N],infact[N];

vector<int > e[N];

int ksm(int a,int b)
{
	int sum = 1;
	while(b)
	{
		if(b&1) sum = sum*a%mod;
		a = a*a%mod;
		b >>= 1;
	}
	return sum;
}

void init(int x)
{
	fact[0] = infact[0] = 1;
	for(int i=1;i<=x;i++) fact[i] = fact[i-1]*i%mod;
	infact[x] = ksm(fact[x],mod-2)%mod;
	for(int i=x-1;i>=1;i--) infact[i] = infact[i+1]*(i+1)%mod;
}

int C(int a,int b)
{
	if(a<b) return 0;
	return fact[a]*infact[b]%mod*infact[a-b]%mod;
}

int get(int now)
{
	cnt = 0;
	for(auto spot:e[now]) va[++cnt] = in[spot]-1; //now相邻的每个子树有多少儿子
	for(int i=1;i<=cnt;i++) 
	{
		sum1[i] = C(va[i],1); //每个子树作为手臂的方案数
		sum2[i] = C(va[i],2); //每个子树作为身子的方案数
	}
	int res = 0,res1 = 0;pre[cnt+1] = 0; //res是任选两个作为子树的总方案数,选的话只选当前的和当前后面的，如果再选前面的就重复了，所以倒着处理维护一个后缀和就好了。res1是每个子树作为手臂的总和。pre就是后缀和
	for(int i=cnt;i>=1;i--)
	{
		res1 = (res1+sum1[i])%mod;
		res = (res+sum1[i]*pre[i+1]%mod)%mod;
		pre[i] = (pre[i+1]+sum1[i])%mod;
	}
	int ans = 0;
	for(int i=1;i<=cnt;i++)
	{
		int sum = sum2[i]*(res-sum1[i]*(res1-sum1[i])%mod)%mod; //i作为身子的方案数*(不能选i作为手臂的方案数)
		sum = sum*(cnt-3)%mod; //用掉两个手臂和一个身子，那么还剩cnt-3个子树，那么就是头的可以选的个数
		ans = (ans+sum)%mod;
	}
	ans = (ans%mod+mod)%mod;
	return ans;
}

signed main()
{
	init(5e5+5);
	scanf("%lld",&T);
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			in[i] = 0;
			e[i].clear();
		}
		for(int i=1;i<n;i++)
		{
			int a,b;
			scanf("%lld%lld",&a,&b);
			e[a].pb(b);
			e[b].pb(a);
			in[a]++,in[b]++; //每个点的度，方便求这个点有多少儿子节点
		}
		int ans = 0;
		for(int i=1;i<=n;i++) ans = (ans+get(i))%mod; //当i作为身子的方案数
		ans = (ans%mod+mod)%mod;
		printf("%lld\n",ans);
	}
	return 0;
}
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

总结：
多多思考，相信自己大体的思路是正确的，当卡住的时候，尝试改变一下卡住的思维。