2023.2.21~22日寄
\(~~~~\) 事物缠身（指演讲/baojin 所以咕一天一起来写
一言
\(~~~~\) 生命是有光的，在我熄灭以前，能够照亮你一点，就是我所有能做的了，我爱你，你要记得我——程霜
模拟赛
状压DP&集合幂级数
「CF1034E」Little C Loves 3 III
题意
\(~~~~\) 求长为 \(2^{n}\) ，值域 \([0,3]\) 的两个数列做集合卷积（下标不交的或卷积）后 \(\bmod 4\) 的结果。
\(~~~~\) \(1\leq n\leq 21\).
题解
\(~~~~\) 很神仙的题。
\(~~~~\) 考虑集合卷积需要 \(2^n n^2\) 的原因：我们需要一位来记录 \(\operatorname{popcount}\)，所以会多带一个 \(n\)。
\(~~~~\) 那么这题非常小的值域可以怎么利用呢？
\(~~~~\) 我们直接把每个数 \(a_i\) 变成 \(4^{\operatorname{popcount (i)}}\) ，然后直接把两个集合做或卷积，得到的 \(c_i'\) 是最后答案 \(c_i\) 的 \(4^{\operatorname{popcount(i)}}\) 倍。
\(~~~~\) 原因如下：我们做集合卷积用 \(\operatorname{popcount}\) 来限制就是因为满足条件的数会有：\(\operatorname{popcount(i)}+\operatorname{popcount(j)}=\operatorname{popcount(i~\text{or}~j)}\)，而不满足条件的则会是大于。那么加上过后就会发现若不满足条件那么最后这一项加数就会多出 \(4\) 的因子，直接寄。
\(~~~~\) 实现的时候开 long long 就好了。
代码
查看代码
#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
ll arr[2097155],brr[2097155],PC[2097155];
ll Pow[25];
int n,N;
void FWT(ll *S,int op)
{
for(int i=1;i<N;i<<=1)
for(int j=0;j<N;j+=i<<1)
for(int k=0;k<i;k++) S[i+j+k]+=S[j+k]*op;
}
char S[2097155];
int main() {
read(n); N=1<<n;
for(int i=1;i<N;i++) PC[i]=PC[i>>1]+(i&1);
Pow[0]=1;
for(int j=1;j<=21;j++) Pow[j]=Pow[j-1]*4;
scanf("%s",S);
for(int i=0;i<N;i++) arr[i]=(S[i]-'0')*Pow[PC[i]];
scanf("%s",S);
for(int i=0;i<N;i++) brr[i]=(S[i]-'0')*Pow[PC[i]];
FWT(arr,1); FWT(brr,1);
for(int i=0;i<N;i++) arr[i]=arr[i]*brr[i];
FWT(arr,-1);
for(int i=0;i<N;i++) printf("%lld",(arr[i]/Pow[PC[i]])&3);
return 0;
}
/*
瑶草一何碧，春入武陵溪。溪上桃花无数，花上有黄鹂。我欲穿花寻路，直入白云深处，浩气展虹霓。只恐花深里，红露湿人衣。
坐玉石，欹玉枕。拂金徽。谪仙何处，无人伴我白螺杯。我为灵芝仙草，不为朱唇丹脸，长啸亦何为。醉舞下山去，明月逐人归。
*/
「CF914G」 Sum the Fibonacci
题意
\(~~~~\) 给出长为 \(n\) 的数列 \(a\)，求有多少五元组 \((a,b,c,d,e)\) 满足：
- \(1\leq a,b,c,d,e\leq n\)；
- \((s_a~\text{or}~s_b)~\text{and}~s_c~\text{and}~(s_d~\text{xor}~s_e)=2^k~~k\in \mathbb{Z}\)；
- \(s_a \text{and} s_b=0\)
\(1\leq n\leq 10^6,0\leq s_i<2^{17}\).
题解
\(~~~~\) 第二个式子，第一部分看做集合卷积 \(2^{17}\times 17^2\) 做，第二部分直接用桶，第三部分直接异或卷积，三个部分统一和卷积，卷完过后统计每个 \(2^i\) 单个的方案即可。
代码
查看代码
#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
const ll MOD=1e9+7,Inv2=(MOD+1)>>1;
inline ll Add(ll a,ll b){return (a+b)%MOD;}
inline ll Dec(ll a,ll b){return (a-b+MOD)%MOD;}
inline ll Mul(ll a,ll b){return a*b%MOD;}
inline ll qpow(ll a,ll b)
{
ll ret=1;
while(b)
{
if(b&1) ret=Mul(ret,a);
b>>=1;a=Mul(a,a);
}
return ret;
}
ll N,Lg;
ll arr[1000005],fib[200005];
ll cnt[200005];
void FWTAND(ll *S,ll op)
{
if(op==-1) op=MOD-1;
for(ll i=1;i<N;i<<=1)
for(ll j=0;j<N;j+=i<<1)
for(ll k=0;k<i;k++) S[j+k]=Add(S[j+k],Mul(S[i+j+k],op));
}
void FWTOR(ll *S,ll op)
{
if(op==-1) op=MOD-1;
for(ll i=1;i<N;i<<=1)
for(ll j=0;j<N;j+=i<<1)
for(ll k=0;k<i;k++) S[i+j+k]=Add(S[i+j+k],Mul(S[j+k],op));
}
void FWTXOR(ll *S,ll op)
{
if(op==-1) op=Inv2;
for(ll i=1;i<N;i<<=1)
{
for(ll j=0;j<N;j+=i<<1)
{
for(ll k=0;k<i;k++)
{
ll x=S[j+k],y=S[i+j+k];
S[j+k]=Mul(Add(x,y),op); S[i+j+k]=Mul(Dec(x,y),op);
}
}
}
}
ll a[20][200005],b[20][200005],PC[200005];
ll A[200005],B[200005],C[200005];
int main() {
// freopen("1.in","r",stdin);
fib[0]=0; fib[1]=1; PC[1]=1; ll Maxn=0;
for(ll i=2;i<200000;i++) fib[i]=Add(fib[i-1],fib[i-2]),PC[i]=PC[i>>1]+(i&1);
ll n;read(n);
for(ll i=1;i<=n;i++)
read(arr[i]),cnt[arr[i]]++,Maxn=max(Maxn,arr[i]);
for(N=1,Lg=0;N<=Maxn;N<<=1,Lg++);
for(ll i=0;i<N;i++) a[PC[i]][i]=C[i]=cnt[i];
for(ll i=0;i<=Lg;i++) FWTOR(a[i],1);
for(ll i=0;i<=Lg;i++) for(ll j=0;j<=i;j++) for(ll k=0;k<N;k++) b[i][k]=Add(b[i][k],Mul(a[j][k],a[i-j][k]));
for(ll i=0;i<=Lg;i++) FWTOR(b[i],-1);
for(ll i=0;i<N;i++) A[i]=Mul(b[PC[i]][i],fib[i]);
FWTXOR(C,1);
for(ll i=0;i<N;i++) C[i]=Mul(C[i],C[i]);
FWTXOR(C,-1);
for(ll i=0;i<N;i++) C[i]=Mul(C[i],fib[i]);
for(ll i=0;i<N;i++) B[i]=Mul(cnt[i],fib[i]);
FWTAND(A,1); FWTAND(B,1); FWTAND(C,1);
for(ll i=0;i<N;i++) A[i]=Mul(A[i],Mul(B[i],C[i]));
FWTAND(A,-1);
ll Ans=0;
for(ll i=0;i<=Lg;i++)
Ans=Add(Ans,A[1<<i]);
printf("%lld",Ans);
return 0;
}
/*
瑶草一何碧，春入武陵溪。溪上桃花无数，花上有黄鹂。我欲穿花寻路，直入白云深处，浩气展虹霓。只恐花深里，红露湿人衣。
坐玉石，欹玉枕。拂金徽。谪仙何处，无人伴我白螺杯。我为灵芝仙草，不为朱唇丹脸，长啸亦何为。醉舞下山去，明月逐人归。
集合卷积 FWT 二合一板子
*/
「CF1326F2」 Wise Men (Hard Version)
题意
\(~~~~\) 给出一个 \(n\) 个人的认识情况的邻接表，对 \(2^{n-1}\) 种二进制串求有多少排列可以生成这个串。排列 \(p\) 生成的串的 \(s_i\) 为邻接表中 \(E_{p_i}{p_{i+1}}\) 的值。
\(~~~~\) \(1\leq n\leq 18\).
题解
\(~~~~\) 考虑容斥：对一个串的定义改为：\(1\) 表示 \(E_{p_i}{p_{i+1}}\) 值为 \(1\)，否则没有限制。
\(~~~~\) 那么这样的话一个串就可以被划分成若干个连续的 \(1\) 段，并且我们不需要关心这些串的首尾连接情况，这样就是若干独立的问题，最后合并即可。
\(~~~~\) 对 \(18\) 进行整数拆分，方案数为 \(450\) 左右，那我们对每种方案都进行计算，具体来说需要定义 \(g_{i,j}\) 表示 \(i\) 个数，用 \(j\) 里面的元素的方案数。那么我们直接在搜拆分的时候顺手把这个 \(g\) 做或卷积求出来即可。
代码
查看代码
#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
ll n,N;
char S[20];
bool Edge[20][20];
ll dp[20][262145],g[20][262145],PC[262145],Tmp[20][262145],f[262145],Sta[262145];
void FWT(ll*SS){for(int i=1;i<N;i<<=1)for(int j=0;j<N;j++)if(j&i) SS[j]+=SS[j^i];}
void IFWT(ll*SS){for(int i=1;i<N;i<<=1) for(int j=0;j<N;j++) if(j&i) SS[j^i]-=SS[j];}
vector <ll> now;
map<vector<ll>,ll>M;
void dfs(ll t,ll Lst,ll res)
{
if(!res)
{
ll Sum=0;
for(ll i=0;i<N;i++) Sum+=Tmp[t][i]*Sta[i];
M[now]=Sum;
return;
}
for(ll i=Lst;i<=res;i++)
{
for(ll j=0;j<N;j++) Tmp[t+1][j]=Tmp[t][j]*g[i][j];
now.push_back(i);
dfs(t+1,i,res-i);
now.pop_back();
}
}
ll Solve(ll x)
{
vector<ll>Now;ll cnt=1;
for(ll i=0;i<n;i++)
{
if(!((x>>i)&1)) Now.push_back(cnt),cnt=0;
cnt++;
}
Now.push_back(cnt); sort(Now.begin(),Now.end());
return M[Now];
}
int main() {
read(n); N=1<<n;
for(ll i=0;i<n;i++)
{
scanf("%s",S); dp[i][1<<i]=1;
for(ll j=0;j<n;j++) Edge[i][j]=S[j]-'0';
}
Sta[0]=(n&1)?-1:1;
for(ll i=1;i<N;i++) PC[i]=PC[i>>1]+(i&1),Tmp[0][i]=1,Sta[i]=((i&1)?-1:1)*Sta[i>>1];
for(ll i=1;i<N;i++)
for(ll j=0;j<n;j++)
for(ll k=0;k<n;k++)
if((!((i>>k)&1))&&Edge[j][k]) dp[k][i|(1<<k)]+=dp[j][i];
for(ll i=0;i<n;i++)
for(ll j=1;j<N;j++) g[PC[j]][j]+=dp[i][j];
for(ll i=1;i<n;i++) FWT(g[i]);
dfs(0,1,n); n--; N>>=1;
for(ll i=0;i<N;i++) f[i]=Solve(i);
IFWT(f);
for(ll i=0;i<N;i++) printf("%lld ",f[i]);
return 0;
}
/*
瑶草一何碧，春入武陵溪。溪上桃花无数，花上有黄鹂。我欲穿花寻路，直入白云深处，浩气展虹霓。只恐花深里，红露湿人衣。
坐玉石，欹玉枕。拂金徽。谪仙何处，无人伴我白螺杯。我为灵芝仙草，不为朱唇丹脸，长啸亦何为。醉舞下山去，明月逐人归。
*/
「GYM102798E」 So Many Possibilities...
题意
\(~~~~\) \(m\) 刀，\(n\) 个怪，每个怪有血量 \(a_i\)，每刀可以随机砍一个怪一滴血，求期望杀怪数。
\(~~~~\) \(1\leq n\leq 15,1\leq m\leq 100\).
题解
\(~~~~\) 注意到死了的怪其实可以对应确定他们挨了多少刀，所以刀数应该去对应活着的怪的情况。
\(~~~~\) 记 \(Sum_{S}\) 表示 \(S\) 集合内的怪的总血量
\(~~~~\) 定义 \(f_{i,S}\) 表示用了 \(i\) 刀，杀成 \(S\) 内的情况的概率（\(1\) 为死 \(0\) 为生）
\(~~~~\) 枚举怪进行转移，如果我们一刀没杀死一只怪，那概率就是 \(\frac{1}{n-|S|}\)，这里我们暂时先不关心怪之间不同。若杀死了，那就是 \(\dfrac{\binom{i-Sum_{S}}{arr_{j}-1}}{n-|S|}\) 也就是要给前面的一些刀匹配到这个怪。当然在转移前需要确认：刀数够杀死了的怪且剩下的不会因为鸽巢杀死该活着的怪。
\(~~~~\) 然后我们来确认留给活着的怪的刀分配方案问题，定义 \(g_{i,S}\) 表示用了 \(i\) 刀给 \(S\) 中活着的且都没砍死的方案数。这可以对每个怪爆搜死不死然后单个 \(m^2\) 转移。
\(~~~~\) 最后的答案就是 \(\sum_{S} f_{m,S}\times g_{m-Sum_S,S}\times |S|\).
代码
查看代码
#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
int n,m,U;
double C[105][105];
int arr[20],Sum[32770],lg[32770],PC[32770];
/*1死 0生*/
/*f:砍i刀砍出S里面生死的概率 g:砍i刀S中存活的，都没砍死的概率*/
double f[105][32770];
double g[105][105],G[105][32770];
inline int lowbit(int x){return x&(-x);}
void dfs(int t,int S,int now)
{
if(t==n)
{
for(int i=0;i<=m;i++) G[i][S]=g[now][i];
return;
}
/*没把 t 打死*/
for(int i=0;i<=m;i++)
for(int j=0;j<arr[t+1]&&j<=i;j++) g[now+1][i]+=g[now][i-j]*C[i][j];
dfs(t+1,S,now+1);
/*把 t 打死*/
for(int i=0;i<=m;i++) g[now+1][i]=0;
dfs(t+1,S|(1<<t),now);
}
bool check(int x,int S){return x>=Sum[S]&&Sum[U^S]-PC[U^S]>=x-Sum[S];}
int main() {
read(n);read(m);lg[1]=1;
for(int i=1;i<=n;i++) read(arr[i]),lg[1<<i]=i+1;
for(int i=0;i<=100;i++)
{
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j];
}
for(int i=1;i<(1<<n);i++) PC[i]=PC[i>>1]+(i&1),Sum[i]=Sum[i^lowbit(i)]+arr[lg[lowbit(i)]];
g[0][0]=1; dfs(0,0,0);
U=(1<<n)-1;
double Ans=0; f[0][0]=1;
for(int S=0;S<(1<<n);S++)
{
int Num=n-PC[S];
for(int i=0;i<m;i++)
{
if(check(i,S))
{
for(int j=0;j<n;j++)
if((!((S>>j)&1))&&check(i+1,S^(1<<j))) f[i+1][S^(1<<j)]+=f[i][S]*C[i-Sum[S]][arr[j+1]-1]/Num;
if(check(i+1,S)) f[i+1][S]+=f[i][S]/Num;
}
else f[i][S]=0;
}
if(m>=Sum[S])
Ans+=f[m][S]*G[m-Sum[S]][S]*(n-Num);//cerr<<f[m][S]<<" "<<G[m-Sum[S]][S]<<" "<<n-Num<<endl;
}
printf("%.8f",Ans);
return 0;
}
/*
瑶草一何碧，春入武陵溪。溪上桃花无数，花上有黄鹂。我欲穿花寻路，直入白云深处，浩气展虹霓。只恐花深里，红露湿人衣。
坐玉石，欹玉枕。拂金徽。谪仙何处，无人伴我白螺杯。我为灵芝仙草，不为朱唇丹脸，长啸亦何为。醉舞下山去，明月逐人归。
*/