Wuyanru's blog
0%

[2024 集训队互测 Round 12] goods

发表于 分类于 ，

互测时间： 年 月 日。这是这场的 T3（实际上是第二简单的。

既然数据题解那些都公开了那写个题解应该不算侵权吧（

应该可以在 这里 看题。

出题人题解

下载

题意

现在有 个物品，第 个物品权值为 。

对于一个物品的集合，我们定义集合的权值，为其中所有物品的权值的异或和，空集的权值为 。

当你选择一个集合后，会有两个人挑选这些物品。

每一个人可以选中若干物品，一个物品只能被同一个人选择一次，但是一个物品可以被两个人同时选择。两个人选择的总次数为 。

定义一个集合的期待值，为两个人从其中挑选物品的本质不同方案数。

对于每一个 ，输出所有权值为 的集合，期待值之和，对 取模。

，

，

题解

当我读完这个题的时候，我的思路就已经错了（悲

假设一共选了 个物品，那两个人选择的方案数就是 。

但是很可惜，这个式子并没有什么用（事实上我也只会这个了（

建议先做一下这道题的 前置题。

这道题显然和这个前置题长得很像。

这道前置题中，每多选择一个物品，会给答案造成一个 的贡献。

但是我们从上面的二项式可以知道，在本题中多选择一个物品，对答案的贡献不是常数。

所以我们考虑使用一个多项式 描述这个贡献。

表示没有人选中； 表示有一个人选中，对选中次数造成 的贡献，方案是 ； 表示被两个人选中，对选中次数造成 的贡献。

这样的话，我们进行 的时候，每一项的系数，就还是一个多项式。

这就相当于有一个关于 的二元多项式，我们对 做加法卷积，对 做异或卷积。

最后所得到的 项，前面的系数就是 所有权值为 的集合期待值之和。

大体思路是这个样子，但是显然不能直接做。

我们设 ，。

那么我们想要求的就是 ，更近一步，我们只关心它的 项构成的多项式。

根据前置题的启发，我们发现 这个多项式只有 和 这两个位置上有值。

所以 实际上只有 和 两种取值。

那么我们的 一定可以表示为 的形式。

那我们能不能试图求出这个 呢？

考虑代入 ，那么 就只有 和 两种取值。

由于 具有分配律，即 。

那么 。等号右边的多项式是易得的，所以等号左边的多项式我们可以求出来。

那么我们就知道了 ，这样就可以算出所有的 了。

既然已经算出了所有的 ，我们考虑如何计算答案。 提出后面的负号枚举第一个括号中有个不选提出后面的

后面的一个 不难使用 NTT 算出。

这样我们就得到了 。

再做一个 就可以得到 。

这道题就做完啦！

时间复杂度 。

代码

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=998244353;
const int inv2=(mod+1)/2;
const int G=3;
const int NG=(mod+1)/G;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int wh[2097152];
ll jc[2097153];
ll inv[2097153];
ll f[2097152];
ll g[2097152];
ll p2[2097152];
ll q2[2097152];
int t[1048577];
int n,m,B,L;
template<typename A>
inline void FWT(A *f,int m,int typ)
{
    for(int i=0;i<m;i++) for(int j=0;j<(1<<m);j++) if(j&(1<<i))
    {
        ll num1=f[j^(1<<i)],num2=f[j];
        if(typ) f[j^(1<<i)]=(num1+num2)%mod,f[j]=(num1-num2+mod)%mod;
        else f[j^(1<<i)]=(num1+num2)*inv2%mod,f[j]=(num1-num2+mod)*inv2%mod;
    }
}
inline ll qow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
inline void NTT(ll *f,int L,bool dft)
{
    for(int i=0;i<L;i++) if(i<wh[i]) swap(f[i],f[wh[i]]);
    for(int len=2;len<=L;len<<=1)
    {
        ll step=qow(dft?G:NG,(mod-1)/len);
        for(int l=0,r=len;l<L;l+=len,r+=len)
        {
            int mid=(l+r)>>1;ll now=1;
            for(int i=l,j=mid;j<r;i++,j++)
            {
                ll num=f[j]*now%mod;
                f[j]=(f[i]-num+mod)%mod;
                f[i]=(f[i]+num)%mod;
                now=now*step%mod;
            }
        }
    }
    if(!dft)
    {
        ll num=qow(L,mod-2);
        for(int i=0;i<L;i++) f[i]=f[i]*num%mod;
    }
}
inline ll C(int a,int b)
{
    if(a<b||b<0) return 0;
    return jc[a]*inv[b]%mod*inv[a-b]%mod;
}
inline void init()
{
    L=p2[0]=jc[0]=q2[0]=1;while(L<2*n+2) L<<=1;
    for(int i=1;i<L;i++) p2[i]=p2[i-1]*2%mod,q2[i]=q2[i-1]*inv2%mod;

    for(int i=1;i<=L;i++) jc[i]=jc[i-1]*i%mod;
    inv[L]=qow(jc[L],mod-2);
    for(int i=L;i;i--) inv[i-1]=inv[i]*i%mod;

    for(int i=0;i<L;i++) wh[i]=(wh[i>>1]>>1)+(i&1?L>>1:0);
    for(int i=0;i<=n;i++)
    {
        f[i]=inv[i];
        g[i]=q2[i]*inv[i]%mod*C(n-i,B-n+i)%mod;
    }
    NTT(f,L,1),NTT(g,L,1);
    for(int i=0;i<L;i++) f[i]=f[i]*g[i]%mod;
    NTT(f,L,0);
}
int main()
{
    n=read(),m=read(),B=read();init();
    for(int i=1;i<=n;i++) t[0]++,t[read()]++;
    FWT(t,m,1);for(int i=0;i<(1<<m);i++) t[i]/=2;

    for(int i=0;i<(1<<m);i++)
    {
        g[i]=p2[2*n-B]*f[t[i]]%mod*jc[t[i]]%mod;
        if((n-t[i])&1) g[i]=(mod-g[i])%mod;
    }
    FWT(g,m,0);
    for(int i=0;i<(1<<m);i++)
    {
        if(i) putchar(' ');
        printf("%lld",g[i]);
    }
    return 0;
}

感谢观看！