CF1554E You

考虑到删点操作的实质是指认边的方向。

由于这是一棵树，所以有很好的性质。

我们完全可以以此从树叶开始，往上拓扑进行，按照对某个数的取膜的大小来进行操作。

由此可知，除了 \(1\) 以外,任意 \(2 \leq k\) 都有可能，且只有一种方案。

那么如何判断方案是当下的问题。

考虑到我们的的操作过程，我们发现其实在每个质数的同余系下，有且只有一个答案可能存在。

又由于 \(m = n - 1 = \sum a[i]\)，那么我们把 \(m\) 质数分解，对这些质数的同余系进行讨论就好。

同时总方案数为 \(2 ^ {n - 1}\) ，依照容斥原理，那么 \(k = 1\) 时答案为 \(2 ^ {n - 1} - \sum_{i = 2} f[i]\)

#include<iostream>

#include<cstdio>

#include<queue>

#define ll long long

#define N 100005

#define mod 998244353 

ll T;

ll n;

ll head[N],cnt;

ll in[N],iin[N];

ll a[N],b[N];

ll f[N];

struct P{

	int to,next;

}e[N << 1];

inline void clear(){

	for(int i = 1;i <= n;++i)

	head[i] = in[i] = iin[i] = a[i] = b[i] = 0,f[i] = 0;

	for(int i = 1;i <= cnt;++i)

	e[i].to = e[i].next = 0;

	cnt = 0;

}

inline void add(int x,int y){

	e[++cnt].to = y;

	e[cnt].next = head[x];

	head[x] = cnt;

	in[y] ++ ;

}

inline ll qpow(ll a,ll b){

	ll ans = 1;

	while(b){

		if(b & 1)ans = ans * a % mod;

		a = a * a % mod;

		b >>= 1;

	}

	return ans;

}

std::queue<int>QWQ;

ll vis[N];

inline ll gcd(ll x,ll y){

	return (x == 0) ? y : gcd(y % x,x);

}

inline ll find(ll x){//找出在该同余系下的答案。

	for(int i = 1;i <= n;++i)

	iin[i] = in[i],a[i] = b[i] = 0,vis[i] = 0;

	for(int i = 1;i <= n;++i)

	if(iin[i] == 1)//成为叶子

	QWQ.push(i);

	while(QWQ.size()){

		int u = QWQ.front();

		QWQ.pop();

		vis[u] = 1;

		for(int i = head[u];i;i = e[i].next){

			int v = e[i].to;

			if(vis[v])continue;

			if(a[u] == 0)a[v] = (a[v] + 1) % x,b[v] ++ ;else a[u] = (a[u] + 1) % x,b[u] ++;

			iin[v] -- ;

			if(iin[v] == 1)

			QWQ.push(v);

		}

	}

	ll ans = b[1];

	for(int i = 2;i <= n;++i)

	ans = gcd(ans,b[i]);

	return ans;

}

int main(){

	scanf("%lld",&T);

	while(T -- ){

		scanf("%lld",&n);

		clear();

		for(int i = 1;i <= n - 1;++i){

			ll x,y;

			scanf("%lld%lld",&x,&y);

			add(x,y);

			add(y,x);

		}

		ll m = n - 1;

		for(int i = 2;i * i <= m;++i){

			if(m % i == 0){

				ll si = find(i);

				if(si % i == 0)

				f[si] = 1 ;

				while(m % i == 0 && i != 1)m /= i;

			}

		}

		if(m > 1){

			ll si = find(m);

			if(si % m == 0)

			f[si] = 1 ;

		}

		f[1] = (f[1] + qpow(2,n - 1)) % mod;

		for(int i = 2;i <= n;++i)

		f[1] = (f[1] - f[i] + mod) % mod;

		for(int i = 1;i <= n;++i)

		std::cout<<f[i]<<" ";

		puts("");

	}

}

巴特西

CF1554E You

最新文章

热门文章