CF1707D Partial Virtual Trees()

首先真子集这一限制比较麻烦,我们可以尝试把这个限制给去除掉。
具体地,令 \(G(i)\) 表示答案, \(F(i)\) 为用 \(i\) 步使得 \(U={1}\)且不要求真子集这一限制的方案数。
考虑 \(F(i)\), 枚举哪几步满足真子集,可知 \(F(i) = \Sigma_{j=1}^{i}\binom{i}{j}G(j)\)
显然可以二项式反演,可知 \(G(i)=\Sigma_{j=1}^i (-1) ^{i – j} \binom {i}{j} F(j)\)。(其实就是子集反演)。
定义 \(f_{i,j}\) 表示 \(i\) 子树直到第 \(j\) 个时刻还有未被点亮的点的方案数。
考虑转移,分 \(i\) 在第 \(k\) 时刻仍点亮和未点亮两种情况。对于前者,不难发现只要每个子树内合法, \(i\) 子树内必然合法,所以

设 \(s_i\) 为 \(f_i\) 的前缀和。
对于第二种情况,枚举 \(i\) 在 \(p\) 时刻至 \(p + 1\) 时刻间熄灭,则 \(p+1\) 时刻到 \(k\) 时刻有且仅有 \(i\) 的一个儿子子树被点亮,因此有转移式

改变求和顺序,预处理前缀后缀从而预处理 \(g_{u,k} = \sum_{p=0}^{k} \prod_{v \in son(i) v \not= u} s_{v,p}\)

根节点暴力统计一下答案就行了。
Tips:
如果子集限制严格,可以考虑子集反演,处理更加简洁便于计算的子集。

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
   x = 0; char ch = getchar(); bool flg = 0;
   for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
   for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
   if (flg) x = -x;
   read(Ar...);	
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

#define int LL
const int N = 2010;
int n, fac[N], ifac[N], mod;
vector<int> e[N];
inline int Qpow(int a, int b) {
   LL res = 1;
   for (; b; b >>= 1) {
   	if (b & 1) (res *= a) %= mod;
   	(a *= a) %= mod;
   }
   return res;
}

int f[N][N], s[N][N], pre[N][N], suf[N][N], sum[N];
int ans[N];
inline int C(int n, int m) {
   if (n < 0 || m < 0) return 0;
   return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

inline void dfs(int u, int fa) {
   // cerr << u << 
   vector<int> son;
   for (auto v : e[u]) {
   	if (v == fa) continue ;
   	dfs(v, u), son.push_back(v);
   }
   if (son.empty()) {
   	U(i, 1, n - 1) f[u][i] = 1, s[u][i] = i;
   	return ;
   }
   int tot = son.size();
   U(j, 0, tot - 1)
   	U(i, 1, n - 1) pre[i][j + 1] = suf[i][j + 1] = s[son[j]][i];
   U(i, 1, n - 1) {
   	pre[i][0] = suf[i][tot + 1]=1;
   	U(j, 0, tot - 1)
   		pre[i][j + 1] = pre[i][j + 1] * pre[i][j] % mod;
   	D(j, tot - 1, 0)
   		suf[i][j + 1] = suf[i][j + 1] * suf[i][j + 2] % mod;
   	f[u][i] = pre[i][tot];
   }
   if(u == 1)
   	return;
   U(i, 1, n - 1) {
   	for(int j = 0, v = son[0]; j < tot; v = son[++j])
   		update(f[u][i], f[v][i] * sum[v] % mod),
   		update(sum[v], pre[i][j] * suf[i][j + 2] % mod);
   	s[u][i] = (s[u][i - 1] + f[u][i]) % mod;
   }
}

signed main(){
   //FO("");
   read(n, mod);
   U(i, 2, n) {
   	int u, v;
   	read(u, v);
   	e[u].push_back(v);
   	e[v].push_back(u);
   }

   fac[0] = 1;
   U(i, 1, n) fac[i] = fac[i - 1] * i % mod;
   ifac[n] = Qpow(fac[n], mod - 2);
   D(i, n - 1, 0) ifac[i] = ifac[i + 1] * (i + 1) % mod;
   dfs(1, 0);
   U(i, 1, n - 1) {
   	ans[i] = f[1][i];
   	U(j, 0, i - 1) 
   		update(ans[i], mod - C(i, j) * ans[j] % mod);
   	writesp(ans[i]);
   }
   return 0;
}
————————

首先真子集这一限制比较麻烦,我们可以尝试把这个限制给去除掉。
具体地,令 \(G(i)\) 表示答案, \(F(i)\) 为用 \(i\) 步使得 \(U={1}\)且不要求真子集这一限制的方案数。
考虑 \(F(i)\), 枚举哪几步满足真子集,可知 \(F(i) = \Sigma_{j=1}^{i}\binom{i}{j}G(j)\)
显然可以二项式反演,可知 \(G(i)=\Sigma_{j=1}^i (-1) ^{i – j} \binom {i}{j} F(j)\)。(其实就是子集反演)。
定义 \(f_{i,j}\) 表示 \(i\) 子树直到第 \(j\) 个时刻还有未被点亮的点的方案数。
考虑转移,分 \(i\) 在第 \(k\) 时刻仍点亮和未点亮两种情况。对于前者,不难发现只要每个子树内合法, \(i\) 子树内必然合法,所以

设 \(s_i\) 为 \(f_i\) 的前缀和。
对于第二种情况,枚举 \(i\) 在 \(p\) 时刻至 \(p + 1\) 时刻间熄灭,则 \(p+1\) 时刻到 \(k\) 时刻有且仅有 \(i\) 的一个儿子子树被点亮,因此有转移式

改变求和顺序,预处理前缀后缀从而预处理 \(g_{u,k} = \sum_{p=0}^{k} \prod_{v \in son(i) v \not= u} s_{v,p}\)

根节点暴力统计一下答案就行了。
Tips:
如果子集限制严格,可以考虑子集反演,处理更加简洁便于计算的子集。

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
   x = 0; char ch = getchar(); bool flg = 0;
   for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
   for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
   if (flg) x = -x;
   read(Ar...);	
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

#define int LL
const int N = 2010;
int n, fac[N], ifac[N], mod;
vector<int> e[N];
inline int Qpow(int a, int b) {
   LL res = 1;
   for (; b; b >>= 1) {
   	if (b & 1) (res *= a) %= mod;
   	(a *= a) %= mod;
   }
   return res;
}

int f[N][N], s[N][N], pre[N][N], suf[N][N], sum[N];
int ans[N];
inline int C(int n, int m) {
   if (n < 0 || m < 0) return 0;
   return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

inline void dfs(int u, int fa) {
   // cerr << u << 
   vector<int> son;
   for (auto v : e[u]) {
   	if (v == fa) continue ;
   	dfs(v, u), son.push_back(v);
   }
   if (son.empty()) {
   	U(i, 1, n - 1) f[u][i] = 1, s[u][i] = i;
   	return ;
   }
   int tot = son.size();
   U(j, 0, tot - 1)
   	U(i, 1, n - 1) pre[i][j + 1] = suf[i][j + 1] = s[son[j]][i];
   U(i, 1, n - 1) {
   	pre[i][0] = suf[i][tot + 1]=1;
   	U(j, 0, tot - 1)
   		pre[i][j + 1] = pre[i][j + 1] * pre[i][j] % mod;
   	D(j, tot - 1, 0)
   		suf[i][j + 1] = suf[i][j + 1] * suf[i][j + 2] % mod;
   	f[u][i] = pre[i][tot];
   }
   if(u == 1)
   	return;
   U(i, 1, n - 1) {
   	for(int j = 0, v = son[0]; j < tot; v = son[++j])
   		update(f[u][i], f[v][i] * sum[v] % mod),
   		update(sum[v], pre[i][j] * suf[i][j + 2] % mod);
   	s[u][i] = (s[u][i - 1] + f[u][i]) % mod;
   }
}

signed main(){
   //FO("");
   read(n, mod);
   U(i, 2, n) {
   	int u, v;
   	read(u, v);
   	e[u].push_back(v);
   	e[v].push_back(u);
   }

   fac[0] = 1;
   U(i, 1, n) fac[i] = fac[i - 1] * i % mod;
   ifac[n] = Qpow(fac[n], mod - 2);
   D(i, n - 1, 0) ifac[i] = ifac[i + 1] * (i + 1) % mod;
   dfs(1, 0);
   U(i, 1, n - 1) {
   	ans[i] = f[1][i];
   	U(j, 0, i - 1) 
   		update(ans[i], mod - C(i, j) * ans[j] % mod);
   	writesp(ans[i]);
   }
   return 0;
}