2022 年牛客多校第九场补题记录

A Car Show

题意：给定长度为 $n$ 的序列 { a i } \{a_i\} {ai​}，其中 $a_i\in [1,m]$，求有多少个连续子区间包含 $[1,m]$ 中每个数。$n,m\le 1\times 10^5$。

解法：使用双指针即可。时间复杂度 $\mathcal{O}(n)$。

#include 
using namespace std;
const int N = 100000;
int cnt[N + 5], a[N + 5];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    long long ans = 0;
    for (int i = 1; i <= n;i++)
        scanf("%d", &a[i]);
    int now = 0;
    for (int l = 1, r = 1; l <= n;l++)
    {
        while (r <= n && now < m)
        {
            if(!cnt[a[r]])
                now++;
            cnt[a[r]]++;
            r++;
        }
        if (now == m)
            ans += n - r + 2;
        cnt[a[l]]--;
        if (!cnt[a[l]])
            now--;
    }
    printf("%lld", 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

B Two Frogs

题意：有一长度为 $n$ 的数轴和 $2$ 个青蛙，初始均在 $1$ 号点，在第 $i$ 号点两个青蛙都以等概率跳到 $[i+1,i+a_i]$ 号点，问两青蛙以相同次数跳跃抵达 $n$ 号点的概率。$n\le 8\times 10^3$。

解法：计算出单个青蛙的答案即可。设 $f_{i,j}$ 为在 $i$ 号点，还需要跳跃 $j$ 次抵达 $n$ 号点的概率，则答案为 $\sum _{i=1}^n{f}_{1,i}^2$。其转移非常显然：$f_{i,j}=\frac{1}{a_i}\sum _{k=1}^{a_i}{f}_{i+k,j-1}$。使用后缀和优化即可，整体复杂度 $\mathcal{O}(n^2)$。

#include 
using namespace std;
const int N = 8000;
const long long mod = 998244353;
long long power(long long a, long long x)
{
    long long ans = 1;
    while(x)
    {
        if (x & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return ans;
}
int a[N + 5], f[N + 5][N + 5], suf[N + 5][N + 5];
long long inv[N + 5];
int main()
{
    int n;
    scanf("%d", &n);
    inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for (int i = 1; i <= n;i++)
        scanf("%d", &a[i]);
    f[n][0] = suf[n][0] = 1;
    for (int i = n - 1; i >= 1; i--)
    {
        suf[i][0] = suf[i + 1][0];
        for (int j = 1; j <= n; j++)
            f[i][j] = 1ll * (suf[i + 1][j - 1] - suf[i + a[i] + 1][j - 1] + mod) % mod * inv[a[i]] % mod,
            suf[i][j] = (suf[i + 1][j] + f[i][j]) % mod;
    }
    long long ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = (ans + 1ll * f[1][i] * f[1][i] % mod) % mod;
    printf("%lld", 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

C Global Positioning System

题意：给定 $n$ 个点 $m$ 条边的图，图上每条边有一向量。现在这些边上的向量恰好有一个错误的，原始的图上任意环上向量和为 $\vec{0}$，找出有多少个可能错误的边。$n,m\le 1\times 10^5$。

解法：首先找到任意一个生成森林，考虑非树边的加入会对答案造成什么影响：

1. 当前边 $(u,v)$ 的加入不会造成冲突。那么对于链 $u\to \mathrm{lca}(u,v)$ 与 $v\to \mathrm{lca}(u,v)$ 均不能出现错误。
2. 当前边 $(u,v)$ 的加入导致了错误。则有以下两种子情况：树边错误与 $(u,v)$ 错误。在树上对 $u\to \mathrm{lca}(u,v)$ 与 $v\to \mathrm{lca}(u,v)$ 链打标记，记录错误次数。同时 $(u,v)$ 边也打上标记，表示可能错误。

最后统计答案的时候，找到所有错误的边的交集，对于树边必然是这些答案中的一个（注意要去掉不允许出错的正确环）。若只有一条非树边的加入导致了错误，则当前错误非树边也可能是错误的。

#include
#define IL inline
#define LL long long
using namespace std;
const int N=5e5+3;
struct poi{
	LL x,y,z;
	poi operator+(const poi &a) const{
	return (poi){x+a.x,y+a.y,z+a.z};}
	poi operator-(const poi &a) const{
	return (poi){x-a.x,y-a.y,z-a.z};}
	poi operator*(const int k) const{
	return (poi){x*k,y*k,z*k};}
	IL int chk(){return !x&&!y&&!z;}
}dis[N];
struct hh{
	int to,nxt,id;poi w;
}e[N<<1];
struct line{
	int x,y,id;poi w;
}l[N],re[N];
int n,m,num,cnt,fir[N],fa[N][22],vis[N],f[N],dep[N],val[N],id[N],bo[N],ban[N];
vector<line>er;vector<int>ans;
IL int in(){
  char c;int f=1;
  while((c=getchar())<'0'||c>'9')
    if(c=='-') f=-1;
  int x=c-'0';
  while((c=getchar())>='0'&&c<='9')
    x=x*10+c-'0';
  return x*f;
}
IL void add(int x,int y,int pos,poi w){
	e[++num]=(hh){y,fir[x],pos,w},fir[x]=num;
	e[++num]=(hh){x,fir[y],pos,w*-1},fir[y]=num;
}
int find(int x){return x^f[x]?f[x]=find(f[x]):x;}
void dfs1(int u,int f){
	vis[u]=1,dep[u]=dep[f]+1,fa[u][0]=f;
	for(int i=0;fa[u][i];++i)
	  fa[u][i+1]=fa[fa[u][i]][i];
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
	  if(v^f) dis[v]=dis[u]+e[i].w,dfs1(v,u);
}
IL int Lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;~i;--i)
	  if(dep[fa[x][i]]>=dep[y])
	    x=fa[x][i];
	if(x==y) return x;
	for(int i=19;~i;--i)
	  if(fa[x][i]^fa[y][i])
	    x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
void chk(line l,int pos){
	int x=l.x,y=l.y;
	poi sum=l.w+(dis[y]*-1)+dis[x];
	if(!sum.chk()){
		int lca=Lca(x,y);
		++val[x],++val[y],val[lca]-=2;
		er.push_back(l);
	}
	else bo[pos]=1;
}
IL void print(){
	sort(ans.begin(),ans.end());
	int nn=0;
	for(int i=0;i<ans.size();++i)
	  if(!ban[ans[i]]) ++nn;
	printf("%d\n",nn);
	for(int i=0;i<ans.size();++i)
	  if(!ban[ans[i]]) printf("%d ",ans[i]);
	putchar('\n');
}
void dfs2(int u,int f){
	vis[u]=1;
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
	  if(v^f) id[v]=e[i].id,dfs2(v,u),val[u]+=val[v];
	if(!val[u]&&id[u]) ans.push_back(id[u]); 
}
void work1(){
	for(int i=1;i<=cnt;++i){
		int x=re[i].x,y=re[i].y,lca=Lca(x,y);
		++val[x],++val[y],val[lca]-=2;
	}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;++i)
	  if(!vis[i]) dfs2(i,0); 
	print();
}
void dfs3(int u,int f){
	vis[u]=1;
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
	  if(v^f) id[v]=e[i].id,dfs3(v,u),val[u]+=val[v];
	if(val[u]==er.size()) ans.push_back(id[u]);
}
void dfs4(int u,int f){
	vis[u]=1;
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
	  if(v^f) id[v]=e[i].id,dfs4(v,u),val[u]+=val[v];
	if(val[u]) ban[id[u]]=1;
}
void work2(){
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;++i)
	  if(!vis[i]) dfs3(i,0);
	if(er.size()==1) ans.push_back(er[0].id);
	memset(val,0,sizeof(val));
	for(int i=1;i<=cnt;++i)
	  if(bo[i]){
	  	int x=re[i].x,y=re[i].y,lca=Lca(x,y);
	  	++val[x],++val[y],val[lca]-=2;
	  }
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;++i)
	  if(!vis[i]) dfs4(i,0);
	print();
}
void solve(){
	int u,v,x,y,z;
	n=in(),m=in();
	for(int i=1;i<=n;++i) f[i]=i;
	for(int i=1;i<=m;++i)
	  u=in(),v=in(),x=in(),y=in(),z=in(),
	  l[i]=(line){u,v,i,(poi){x,y,z}};
	for(int i=1;i<=m;++i){
		int x=l[i].x,y=l[i].y;
		if(find(x)^find(y)) f[find(x)]=find(y),add(x,y,l[i].id,l[i].w);
		else re[++cnt]=l[i];
	}
	for(int i=1;i<=n;++i)
	  if(!vis[i]) dfs1(i,0);
	for(int i=1;i<=cnt;++i) chk(re[i],i);
	if(!er.size()) work1();
	else work2();
}
int main()
{
	int T=1;
	while(T--) solve();
  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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

E Longest Increasing Subsequence

题意：构造一个长度不超过 $100$ 的排列，使得其最长上升子序列个数恰好为 $m$ 个。$m\le 1\times 10^9$。

解法：为了保证 LIS 的个数，一个基础的构造是 $2,1,4,3,6,5\cdots ,2n,2n-1$，这样可以使得 LIS 的个数为 $2^n$。同时此时的 LIS 序列长度为 $n$。最后添加一个最大值，作为全部 LIS 的终止。接下来考虑利用二进制拆分，如何填补更小的 $2^i$。

一个可行的操作是，从大到小的考虑 $2^i$，从后往前的往初始序列中插入。在第 $2i+1$ 个数字的前面插入一个比 $2n$ 大的数字，记为 $x$，这样就可以让该数字可以在前面有 $2^i$ 种选择，同时若选择了新加入的数字，则后面只能选最大值。但是选择到了这里 LIS 的长度不够，所以需要在 $x$ 的往后增补一些数字。注意到对于 $2^j$ 的考虑，一定是在 $2^i,i>j$ 之后考虑的。因而 $2^j$ 这里的 LIS 长度增补可以利用后面增补的数字，只需要增补到 $n$ 的长度即可。因而若 $2^i$ 这里已经加了 $x$ 个数字，$2^j$ 这里只需要额外增补 $n-j-x$ 个数字即可。

例如，考虑 $(100101{)}_2$，那么首先构造 $2,1,4,3,6,5,8,7,10,9,12,11$。首先插入一个最大的：$2,1,4,3,6,5,8,7,10,9,12,11,100$，考虑 $2^2$，因而在 $6$ 前面插入一个比最大值小的数字，例如 $99$。但是这样取到 $99$ LIS 长度不足，因而还需要增补四个数字（为了全部整数因而要将 $99$ 适当下调为 $96$）：$2,1,4,3,(\underline{96},97,98,99),6,5,8,7,10,9,12,11,100$。最后的 $2^0$ 需要在序列的开头增补一个数字，同时为了满足 LIS 的长度， 因而需要开头加入两个数字：$(\underline{94},95),2,1,4,3,(\underline{96},97,98,99),6,5,8,7,10,9,12,11,100$。最后再离散化一下就可以得到最终的排列。

这样的排列长度为：$2\times 30+30=90$，满足条件，因为总的添加数字个数仅为 LIS 的长度。

#include 
using namespace std;
int main()
{
	int t, m;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &m);
		int len = 30;
		while (!(m >> len & 1))
			len--;
		vector<int> add(len, 0);
		int cnt = 0;
		for (int i = len - 1; i >= 0;i--)
			if (m >> i & 1)
			{
				add[i] = len - i - cnt;
				cnt += add[i];
			}
		printf("%d\n", 2 * len + cnt + 1);
		int base = 2 * len;
		for (int i = 0; i < len;i++)
		{
			while (add[i] && add[i]--)
				printf("%d ", ++base);
			printf("%d %d ", 2 * i + 2, 2 * i + 1);
		}
		printf("%d\n", 2 * len + cnt + 1);
	}
	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

F Matrix and GCD

题意：给定 $n\times m$ 的矩阵，其中 $[1,nm]$ 的数字均只出现一次，问所有的连续子矩阵的 $\gcd $ 之和。$n,m\le 1\times 10^3$。

解法：考虑 $\mathcal{O}(n\log n)$ 的倍数枚举，统计有 $f_i$ 个连续子矩形其中全部的数字均是 $i$ 的倍数，再进行容斥，答案为 $\sum _{i=1}^{nm}\mu (i)f_i$。

因而问题转化为，$n\times m$ 的矩形中，有 $k$ 个特殊格点，问有几个矩形是完全由特殊格点组成的。首先先 $\mathcal{O}(k\log k)$ 的进行排序，然后 $\mathcal{O}(k)$ 的从下往上统计每个点垂直往下有多少个连续的特殊格点，然后横向枚举每个格点，用单调栈在线性时间内计算出以当前格点为左上角有多少个矩形，一次计算一整个横向连续段。因而对于一个连通块只需要 $\mathcal{O}(k)$ 的时间，因而总的时间复杂度为 $\mathcal{O}(nm{\log }^{2}nm)$。

#include 
#define fp(i, a, b) for (int i = a, i##_ = (b) + 1; i < i##_; ++i)
#define fd(i, a, b) for (int i = a, i##_ = (b) - 1; i > i##_; --i)

using namespace std;
const int N = 1e3 + 5, M = 1e6 + 5;
using ll = int64_t;
int n, m, a[N][N], vis[N][N], H[N][N];
pair<int, int> pos[M];
ll calc(int *h, int k) {//计算矩形个数
    stack<int> s;
    vector<int> l(k), r(k);
    fd(i, k - 1, 0) {
        while (!s.empty() && h[i] <= h[s.top()]) l[s.top()] = i, s.pop();
        s.push(i);
    }
    while (!s.empty()) l[s.top()] = -1, s.pop();
    fp(i, 0, k - 1) {
        while (!s.empty() && h[i] < h[s.top()]) r[s.top()] = i, s.pop();
        s.push(i);
    }
    while (!s.empty()) r[s.top()] = k, s.pop();
    ll res = 0;
    fp(i, 0, k - 1) res += (ll)h[i] * (i - l[i]) * (r[i] - i);
    return res;
}
void Solve() {
    scanf("%d%d", &n, &m);
    fp(i, 1, n) fp(j, 1, m)
        scanf("%d", a[i] + j), pos[a[i][j]] = {i, j};
    int k = n * m;
    vector<ll> cnt(k + 1);
    fp(d, 1, k) {
        vector<pair<int, int>> a;
        for (int t = d; t <= k; t += d) {
            auto [x, y] = pos[t];
            vis[x][y] = 1, a.push_back({x, y});
        }
        sort(a.begin(), a.end());
        for (int i = a.size() - 1; ~i; --i) {
            auto [x, y] = a[i];
            H[x][y] = vis[x + 1][y] ? H[x + 1][y] + 1 : 1;
        }
        for (int i = 0, j; i < a.size(); i = j + 1) {
            for (j = i; j + 1 < a.size() && a[j + 1].first == a[i].first && a[j + 1].second == a[j].second + 1; ++j);
            cnt[d] += calc(H[a[i].first] + a[i].second, j - i + 1);
        }
        for (auto [x, y] : a) vis[x][y] = 0;
    }
    ll ans = 0;
    fd(d, k, 1) {
        for (int t = 2 * d; t <= k; t += d)
            cnt[d] -= cnt[t];
        ans += cnt[d] * d;
    }
    printf("%lld\n", ans);
}
int main() {
    int t = 1;
    while (t--) Solve();
    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

G Magic Spells

题意：给定 $k$ 个串 { S i } \{S_i\} {Si​}，问在每个串中都出现的本质不同回文子串个数。$\sum |S_i|\le 3\times 10^5$，$k\le 5$。

解法：$k$ 较小，因而可以考虑对每个串都建立一个 PAM，然后同时对 $k$ 个 PAM 进行遍历，只向每个 PAM 都能扩展出来的字符出边走。整体时间复杂度 $\mathcal{O}(k|S_i|)$。

#include 
using namespace std;
const int N = 300000;
class PAM
{
    
public:
	struct node
	{
		int ch[26];
		int fail;
		int len;
        int cnt;
        node ()
		{
			memset(ch, 0, sizeof(ch));
			fail = len = cnt = 0;
		}
	} NIL;
	vector<node> t;
	int tot, len, last;
	string s;
    int getfail(int x, int place)
    {
		while (s[place - t[x].len - 1] != s[place])
			x = t[x].fail;
		return x;
	}
	PAM()
    {
        s = " ";
        tot = 1;
        t.push_back(NIL);
        t.push_back(NIL);
        t[0].len = 0;
		t[0].fail = 1;
		t[1].len = -1;
        last = 0;
    }
    int insert(int ch, int ind)
	{
        s += ch;
        int p = getfail(last, ind);
        if (!t[p].ch[ch])
        {
            int q = ++tot;
            t.push_back(NIL);
            t[q].len = t[p].len + 2;
            t[q].fail = t[getfail(t[p].fail, ind)].ch[ch];
            t[p].ch[ch] = q;
            t[q].cnt = t[t[q].fail].cnt + 1;
        }
		last = t[p].ch[ch];
        return t[last].cnt;
    }
} t[5];
string s[5];
long long cnt;
int k;
void dfs(vector<int> p)
{
    if(t[0].t[p[0]].len >= 1)
        cnt++;
    for (int i = 0; i < 26;i++)
    {
        auto temp = p;
        bool flag = 1;
        for (int j = 0; j < k;j++)
            if (!t[j].t[p[j]].ch[i])
            {
                flag = 0;
                break;
            }
        if(flag)
        {
            for (int j = 0; j < k;j++)
                temp[j] = t[j].t[p[j]].ch[i];
            dfs(temp);
        }
    }
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> k;
    for (int i = 0; i < k;i++)
    {
        cin >> s[i];
        int ind = 0;
        for (auto j : s[i])
            t[i].insert(j - 97, ++ind);
    }
    vector<int> pos1(k, 1), pos0(k, 0);
    dfs(pos1);
    dfs(pos0);
    cout << cnt;
    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
100
101

I The Great Wall II

题意：给定长度为 $n$ 的序列 { a i } \{a_i\} {ai​}，将其划分为连续的 $k$ 段，每一段的花费为这一段的最大值，问 $k\in [1,n]$ 的最小花费。$n\le 8\times 10^3$。

解法：考虑 $f_{k,i}$ 表示前 $i$ 个数字分了 $k$ 段的最小花费，那么朴素转移为 f k , i ← min ⁡ k − 1 ≤ j ≤ i − 1 { f k − 1 , j + max ⁡ j + 1 ≤ l ≤ i a l } \displaystyle f_{k,i} \leftarrow \min_{k-1\leq j \leq i-1} \{f_{k-1,j}+\max_{j+1 \leq l \leq i}a_l\} fk,i​←k−1≤j≤i−1min​{fk−1,j​+j+1≤l≤imax​al​}。考虑分层转移，即固定 $k$，只对 $i$ 进行转移，则可以利用单调栈和线段树，维护 $f_{k-1,j}+\underset{j+1\le l\le i}{\max }{a}_l$ 实现 $\mathcal{O}(n^2\log n)$。但是这样很显然还是过不去。

考虑优化掉线段树的 $\log n$。由于单调栈中会有弹栈操作，因而可以在弹栈的时候维护出待弹栈部分的 $f_{k-1,j}$ 的最小值。对于更前面的最小值，可以在维护单调栈的增减栈操作的时候，同步维护出栈的前缀 $f$ 和 $f+\max$ 的最小值。这样就可以实现 $\mathcal{O}(n^2)$。

#include 
using namespace std;
const int N = 8000, inf = 0x3f3f3f3f;
int a[N + 5], pre[N + 5], f[N + 5][N + 5];
int main()
{
    memset(f, 0x3f, sizeof(f));
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n;i++)
    {
        scanf("%d", &a[i]);
        f[i][1] = pre[i] = max(pre[i - 1], a[i]);
    }
    for (int k = 2; k <= n; ++k)
    {
        vector<int> st, minf, minall;
        st.push_back(inf);
        minf.push_back(0);
        minall.push_back(inf);
        for (int i = 1; i <= n; i++)
        {
            int now = f[i - 1][k - 1];
            while (!st.empty() && st.back() <= a[i])
            {
                now = min(now, minf.back());
                minf.pop_back();
                minall.pop_back();
                st.pop_back();
            }
            f[i][k] = min(now + a[i], minall.back());
            st.push_back(a[i]);
            minf.push_back(now);
            minall.push_back(min(now + a[i], minall.back()));
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d\n", f[n][i]);
    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

K NIO’s OAuth2 Server

题意：有 $k$ 个元素和 $n$ 个由这 $k$ 个元素构成的集合 { S n } \{S_n\} {Sn​}，问由这 $k$ 个元素生成的全部 $2^k-1$ 个非空集合中有多少个 $T$ 集合满足 $T\subseteq \bigcup _{k=1}^i{S}_k$，即由 $i$ 个集合能覆盖 $T$ 集合，对于 $i\in [1,k]$ 计算答案。$k\le 20$，$n\le 1\times 10^5$。

解法：首先利用状压将显然所用集合个数不会超过 $k$ 个，因而可以枚举进行 $i$ 次集合并操作，能得到的集合个数。

这样问题转化为，对这 $n$ 个集合进行 $i$ 次任意并操作，能得到哪些集合。那么利用集合幂级数，使用 $f(x)=\sum _{i=0}^{2^k-1}{f}_i{x}^i$，其中 $f_i$ 为合成集合 $i$ 的方案，进行 $i$ 次 FWTor 即可。最后统计答案的时候，只需要统计系数（方案数）是否为 $0$，若 $f_i$ 不为 $0$ 则表示可以合成，同时对于后面的计算需要强制令 $f_i=1$ 否则最后的方案数可能过大导致溢出。

#include 
using namespace std;
const int N = 20;
using Poly = vector<long long>;
void FWTor(Poly &a, bool rev)
{
    int n = a.size();
    for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1)
        for (int j = 0; j < n; j += l)
            for (int i = 0; i < m; i++)
                if (!rev)
                    a[i + j + m] += a[i + j];
                else
                    a[i + j + m] -= a[i + j];
}
Poly operator |(Poly a, Poly b)
{
    int n = a.size();
    FWTor(a, 0), FWTor(b, 0);
    for (int i = 0; i < n; i++)
        a[i] *= b[i];
    FWTor(a, 1);
    return a;
}
int ans[1 << N], cnt[N + 1];
int main()
{
    int n, k, x, z;
    scanf("%d%d", &n, &k);
    Poly base(1 << k, 0), f(1 << k, 0);
    f[0] = 1;
    while(n--)
    {
        int y = 0;
        scanf("%d", &x);
        while(x--)
        {
            scanf("%d", &z);
            y |= 1 << (z - 1);
        }
        base[y] = 1;
    }
    for (int i = 0; i < k; i++)
        for (int j = (1 << k) - 1; j >= 0; j--)
            if (!(j & (1 << i)))
                base[j] += base[j ^ (1 << i)];
    for (int i = 0; i < 1 << k;i++)
        if(base[i])
        {
            base[i] = ans[i] = 1;
            if (i)
                cnt[1]++;
        }
    for (int j = 1; j <= k; j++)
    {
        f = f | base;
        for (int i = 1; i < 1 << k; i++)
            if (f[i] && !ans[i])
            {
                ans[i] = j;
                cnt[j]++;
            }
        for (auto &i : f)
            if (i)
                i = 1;
    }
    for (int i = 1; i <= k;i++)
        printf("%d ", cnt[i]);
    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