8.5()-其他
8.5()
CF1574F
题意：
定义 \(a\) 序列在 \(b\) 序列中出现的次数为 \(b\) 序列中与 \(a\) 相同的子区间个数。
有 \(n\) 个值域在 \([1,k]\) 的数列 \(A_1,A_2,\cdots,A_n\)，要求构造一个长为 \(m\) 的值域在 \([1,k]\) 的序列 \(a\)，满足对于所有数列 \(A_i\)，\(A_i\) 在序列 \(a\) 中的出现次数大于等于其任意一个非空子区间在 \(a\) 中的出现次数。
求不同的 \(a\) 的数量，答案 \(\bmod 998244353\)。
数据范围：\(1\le n,m,k\le 3\times 10^5,\sum c_i\le 3\times 10^5\)。
题解：
首先考虑不能有任何子区间出现的次数多于自己，那么就是说，任何序列的任何数不能出现超过一次。
考虑有数字相交的两个序列：
这样是可以的：
\(1,2,3\)
\(3,4,5\)
这样是不行的：
\(1,2,3\)
\(3,2,4\)
因为如果这两个序列其中一个出现，那么\(2\)必然会出现两次，比某个序列出现次数都要多。
我们把序列之间的数字连边，那么就是说连通块内不能有环，否则这个连通块里的数字都作废了。
还有另一种情况也不行，就是分叉：
\(1,2,3\)
\(1,2,4\)
路径分叉也不行。
也就是说只有连通块是一条链的时候才能用来作为答案。
先用并查集求出有哪些长度的链，然后更新答案。
假设长度为\(i\)的链有\(cnt[i]\)条，那么当然可以
设\(f(x)=\sum cnt[i]x^i\)
答案为\([x^m]g(x)=1+f(x)+f(x)^2+f(x)^3+…=[x^m]\frac{1}{1-f(x)}\)
还可以什么分治\(NTT\)，复杂度应该都是\(O(nlog^2n*大常数)\)
其实不用，考虑每种颜色只会出现在一条链里，那么长度不同的链最多有\(\sqrt{k}\)条。
暴力更新就行了\(O(m\sqrt{k})\)
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=2e6+10,mod=998244353,inv2=5e8+4,inf=2e9;
inline void main()
{
int n,m,k;
cin>>n>>m>>k;
vector<int> f(k+1),str(k+1),tag(k+1);
vector<int> cnt(m+1);
for(int i=1;i<=k;++i)
{
f[i]=i;
str[i]=1;
}
function<int(int)> find=[&](int k) -> int
{
return f[k]==k?k:f[k]=find(f[k]);
};
auto merge=[&](int x,int y) -> void
{
x=find(x),y=find(y);
if(x==y) {tag[x]=1;return;}
f[x]=y;
str[y]+=str[x];
tag[y]|=tag[x];
};
vector<int> pre(k+1),nxt(k+1);
for(int i=1;i<=n;++i)
{
int s;cin>>s;
int y=0;
while(s--)
{
int x;cin>>x;
if(y)
{
if((pre[x]&&pre[x]!=y)||(nxt[y]&&nxt[y]!=x)) {merge(x,y);tag[find(x)]=1;}
else if(!nxt[y])
{
pre[x]=y,nxt[y]=x;
merge(x,y);
}
}
y=x;
}
}
for(int i=1;i<=k;++i) if(find(i)==i)
{
int tmp=str[i];
if(tmp>m||tag[i]) continue;
++cnt[tmp];
}
vector<int> g,dp(m+1);
dp[0]=1;
for(int i=1;i<=m;++i)
{
if(cnt[i]) g.emplace_back(i);
for(int t:g)
{
dp[i]=(dp[i]+dp[i-t]*cnt[t]%mod)%mod;
}
}
cout<<dp[m]<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::main();
return 0;
}
/*
*/
CF1654F
题意：
- 给定一个长度为 \(2^n\)，只包含小写字母的字符串 \(s\)。
- 你可以将字符串的下标全部异或一个 \([0,2^n)\) 的整数 \(k\)，即构造一个与 \(s\) 等长的新字符串 \(t\)，使得 \(t_i=s_{i\oplus k}\)。
- 最小化 \(t\) 的字典序，并输出字典序最小的 \(t\)。
- \(n\leq 18\)。
题解：
其实可以理解为，如果异或上一个数字\(x\)，且二进制下\(x\)的第\(k\)位是\(1\)，那么每两个相邻的长度为\(2^k\)的段之间就要交换一下位置
\(k=0\)时类似这样交换：\((a,b,c,d)->(b,a,d,c)\)
\(k=1\)时是这样的：\((a,b,c,d)->(c,d,a,b)\)
设\(f(x,k)\)是所有下标异或上\(x\)之后，字符串的前\(2^k\)个字符
根据上面的规律，那么\(f(x,k)\)的得到方法就是
加号表示字符串拼接。
这样就好像是后缀数组的后缀排序，两个关键字，可以用倍增的方法，时间放的比较宽，可以直接\(sort\)
每次\(sort\)，对所有\(f(x,k-1)+f(x\bigoplus 2^{k-1},k-1)\)排名，然后再拼接得到新的\(f(x,k)\)的排名。
最后操作结束后，其实所有\(x\)都是排好序的，想求字典序排第几的排序都可以。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=3e5+10,mod=998244353,inv2=5e8+4,inf=2e9;
inline void main()
{
int n,m;cin>>n;
m=(1<<n);
string s;cin>>s;
vector<int> sa(m),rk(m),tmp(m);
for(int i=0;i<m;++i) sa[i]=i,rk[i]=s[i]-'a';
sort(sa.begin(),sa.end());
int k=0;
auto cmp=[&](int x,int y) -> bool
{
return rk[x]==rk[y]?rk[x^k]<rk[y^k]:rk[x]<rk[y];
};
for(k=1;k<m;k<<=1)
{
sort(sa.begin(),sa.end(),cmp);
for(int i=0,num=0;i<m;++i)
{
if(i==0||cmp(sa[i-1],sa[i])) tmp[sa[i]]=++num;
else tmp[sa[i]]=num;
}
for(int i=0;i<m;++i) rk[i]=tmp[i];
}
int ans=sa[0];
for(int i=0;i<m;++i) cout<<s[i^ans];
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::main();
return 0;
}
/*
*/
CF1716E
题意：
给定一个长度为\(2^n\)的序列\(a\)，\(q\)次询问，每次给定一个数字\(k\)，要求交换所有\(a_i\)和\(a_{i+2^k}\)，单次交换中，已经被交换过的数字不会被再次交换，问每次交换后的序列的最大子段和。
\(1\leq n\leq 18,0\leq k<n,q\leq 2*10^5\)
题解：
这个东西很像线段树结构，而且最大子段和也很能通过线段树来维护。
单次询问对应的操作就是把线段树对应层的所有节点的左右儿子翻转，很合理。
观察询问，其实给出的是一个操作集合，这个集合我们可以用一个二进制数来表示，范围在\(0\sim 2^n-1\)，两次操作之后等于没操作，所以每次询问给出的数字是可以异或的。
最后是如何计算一个操作集合对应的答案：
询问一次查一次肯定不行，因为对应深度的节点可能有很多，可以提前预处理出来。
\(dp[p][s]\)表示，在编号为\(p\)的节点，对应的操作集合为\(s\)的方案数
其实一个建树就可以预处理出来，因为一共\(n\)层，每一层的状态数量一共是\(O(2^n)\)个，所以总状态数是\(O(n*2^n)\)的，完全可以预处理出来。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=3e5+10,mod=998244353,inv2=5e8+4,inf=2e9;
struct node
{
int sum,pre,suf,ans;
void update(node &t1,node &t2)
{
sum=t1.sum+t2.sum;
pre=max(t1.pre,t1.sum+t2.pre);
suf=max(t2.suf,t2.sum+t1.suf);
ans=max(t1.suf+t2.pre,max(t1.ans,t2.ans));
}
};
vector<node> dp[N<<2];
void build(int l,int r,int p,int k)
{
dp[p].resize(r-l+1);
if(l==r)
{
int x;cin>>x;
dp[p][0]=(node){x,max(0ll,x),max(0ll,x),max(0ll,x)};
return;
}
build(l,mid,ls(p),k-1);
build(mid+1,r,rs(p),k-1);
for(int i=0;i<r-l+1;++i)
{
if((i>>k)&1)
{
dp[p][i].update(dp[rs(p)][i^(1<<k)],dp[ls(p)][i^(1<<k)]);
}
else
{
dp[p][i].update(dp[ls(p)][i],dp[rs(p)][i]);
}
}
}
inline void main()
{
int n,m;cin>>n;
m=(1<<n);
build(1,m,1,n-1);
int q,tmp=0;cin>>q;
while(q--)
{
int x;cin>>x;
tmp^=(1<<x);
cout<<dp[1][tmp].ans<<'\n';
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::main();
return 0;
}
/*
*/
CF1574F
题意：
定义 \(a\) 序列在 \(b\) 序列中出现的次数为 \(b\) 序列中与 \(a\) 相同的子区间个数。
有 \(n\) 个值域在 \([1,k]\) 的数列 \(A_1,A_2,\cdots,A_n\)，要求构造一个长为 \(m\) 的值域在 \([1,k]\) 的序列 \(a\)，满足对于所有数列 \(A_i\)，\(A_i\) 在序列 \(a\) 中的出现次数大于等于其任意一个非空子区间在 \(a\) 中的出现次数。
求不同的 \(a\) 的数量，答案 \(\bmod 998244353\)。
数据范围：\(1\le n,m,k\le 3\times 10^5,\sum c_i\le 3\times 10^5\)。
题解：
首先考虑不能有任何子区间出现的次数多于自己，那么就是说，任何序列的任何数不能出现超过一次。
考虑有数字相交的两个序列：
这样是可以的：
\(1,2,3\)
\(3,4,5\)
这样是不行的：
\(1,2,3\)
\(3,2,4\)
因为如果这两个序列其中一个出现，那么\(2\)必然会出现两次，比某个序列出现次数都要多。
我们把序列之间的数字连边，那么就是说连通块内不能有环，否则这个连通块里的数字都作废了。
还有另一种情况也不行，就是分叉：
\(1,2,3\)
\(1,2,4\)
路径分叉也不行。
也就是说只有连通块是一条链的时候才能用来作为答案。
先用并查集求出有哪些长度的链，然后更新答案。
假设长度为\(i\)的链有\(cnt[i]\)条，那么当然可以
设\(f(x)=\sum cnt[i]x^i\)
答案为\([x^m]g(x)=1+f(x)+f(x)^2+f(x)^3+…=[x^m]\frac{1}{1-f(x)}\)
还可以什么分治\(NTT\)，复杂度应该都是\(O(nlog^2n*大常数)\)
其实不用，考虑每种颜色只会出现在一条链里，那么长度不同的链最多有\(\sqrt{k}\)条。
暴力更新就行了\(O(m\sqrt{k})\)
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=2e6+10,mod=998244353,inv2=5e8+4,inf=2e9;
inline void main()
{
int n,m,k;
cin>>n>>m>>k;
vector<int> f(k+1),str(k+1),tag(k+1);
vector<int> cnt(m+1);
for(int i=1;i<=k;++i)
{
f[i]=i;
str[i]=1;
}
function<int(int)> find=[&](int k) -> int
{
return f[k]==k?k:f[k]=find(f[k]);
};
auto merge=[&](int x,int y) -> void
{
x=find(x),y=find(y);
if(x==y) {tag[x]=1;return;}
f[x]=y;
str[y]+=str[x];
tag[y]|=tag[x];
};
vector<int> pre(k+1),nxt(k+1);
for(int i=1;i<=n;++i)
{
int s;cin>>s;
int y=0;
while(s--)
{
int x;cin>>x;
if(y)
{
if((pre[x]&&pre[x]!=y)||(nxt[y]&&nxt[y]!=x)) {merge(x,y);tag[find(x)]=1;}
else if(!nxt[y])
{
pre[x]=y,nxt[y]=x;
merge(x,y);
}
}
y=x;
}
}
for(int i=1;i<=k;++i) if(find(i)==i)
{
int tmp=str[i];
if(tmp>m||tag[i]) continue;
++cnt[tmp];
}
vector<int> g,dp(m+1);
dp[0]=1;
for(int i=1;i<=m;++i)
{
if(cnt[i]) g.emplace_back(i);
for(int t:g)
{
dp[i]=(dp[i]+dp[i-t]*cnt[t]%mod)%mod;
}
}
cout<<dp[m]<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::main();
return 0;
}
/*
*/
CF1654F
题意：
- 给定一个长度为 \(2^n\)，只包含小写字母的字符串 \(s\)。
- 你可以将字符串的下标全部异或一个 \([0,2^n)\) 的整数 \(k\)，即构造一个与 \(s\) 等长的新字符串 \(t\)，使得 \(t_i=s_{i\oplus k}\)。
- 最小化 \(t\) 的字典序，并输出字典序最小的 \(t\)。
- \(n\leq 18\)。
题解：
其实可以理解为，如果异或上一个数字\(x\)，且二进制下\(x\)的第\(k\)位是\(1\)，那么每两个相邻的长度为\(2^k\)的段之间就要交换一下位置
\(k=0\)时类似这样交换：\((a,b,c,d)->(b,a,d,c)\)
\(k=1\)时是这样的：\((a,b,c,d)->(c,d,a,b)\)
设\(f(x,k)\)是所有下标异或上\(x\)之后，字符串的前\(2^k\)个字符
根据上面的规律，那么\(f(x,k)\)的得到方法就是
加号表示字符串拼接。
这样就好像是后缀数组的后缀排序，两个关键字，可以用倍增的方法，时间放的比较宽，可以直接\(sort\)
每次\(sort\)，对所有\(f(x,k-1)+f(x\bigoplus 2^{k-1},k-1)\)排名，然后再拼接得到新的\(f(x,k)\)的排名。
最后操作结束后，其实所有\(x\)都是排好序的，想求字典序排第几的排序都可以。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=3e5+10,mod=998244353,inv2=5e8+4,inf=2e9;
inline void main()
{
int n,m;cin>>n;
m=(1<<n);
string s;cin>>s;
vector<int> sa(m),rk(m),tmp(m);
for(int i=0;i<m;++i) sa[i]=i,rk[i]=s[i]-'a';
sort(sa.begin(),sa.end());
int k=0;
auto cmp=[&](int x,int y) -> bool
{
return rk[x]==rk[y]?rk[x^k]<rk[y^k]:rk[x]<rk[y];
};
for(k=1;k<m;k<<=1)
{
sort(sa.begin(),sa.end(),cmp);
for(int i=0,num=0;i<m;++i)
{
if(i==0||cmp(sa[i-1],sa[i])) tmp[sa[i]]=++num;
else tmp[sa[i]]=num;
}
for(int i=0;i<m;++i) rk[i]=tmp[i];
}
int ans=sa[0];
for(int i=0;i<m;++i) cout<<s[i^ans];
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::main();
return 0;
}
/*
*/
CF1716E
题意：
给定一个长度为\(2^n\)的序列\(a\)，\(q\)次询问，每次给定一个数字\(k\)，要求交换所有\(a_i\)和\(a_{i+2^k}\)，单次交换中，已经被交换过的数字不会被再次交换，问每次交换后的序列的最大子段和。
\(1\leq n\leq 18,0\leq k<n,q\leq 2*10^5\)
题解：
这个东西很像线段树结构，而且最大子段和也很能通过线段树来维护。
单次询问对应的操作就是把线段树对应层的所有节点的左右儿子翻转，很合理。
观察询问，其实给出的是一个操作集合，这个集合我们可以用一个二进制数来表示，范围在\(0\sim 2^n-1\)，两次操作之后等于没操作，所以每次询问给出的数字是可以异或的。
最后是如何计算一个操作集合对应的答案：
询问一次查一次肯定不行，因为对应深度的节点可能有很多，可以提前预处理出来。
\(dp[p][s]\)表示，在编号为\(p\)的节点，对应的操作集合为\(s\)的方案数
其实一个建树就可以预处理出来，因为一共\(n\)层，每一层的状态数量一共是\(O(2^n)\)个，所以总状态数是\(O(n*2^n)\)的，完全可以预处理出来。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=3e5+10,mod=998244353,inv2=5e8+4,inf=2e9;
struct node
{
int sum,pre,suf,ans;
void update(node &t1,node &t2)
{
sum=t1.sum+t2.sum;
pre=max(t1.pre,t1.sum+t2.pre);
suf=max(t2.suf,t2.sum+t1.suf);
ans=max(t1.suf+t2.pre,max(t1.ans,t2.ans));
}
};
vector<node> dp[N<<2];
void build(int l,int r,int p,int k)
{
dp[p].resize(r-l+1);
if(l==r)
{
int x;cin>>x;
dp[p][0]=(node){x,max(0ll,x),max(0ll,x),max(0ll,x)};
return;
}
build(l,mid,ls(p),k-1);
build(mid+1,r,rs(p),k-1);
for(int i=0;i<r-l+1;++i)
{
if((i>>k)&1)
{
dp[p][i].update(dp[rs(p)][i^(1<<k)],dp[ls(p)][i^(1<<k)]);
}
else
{
dp[p][i].update(dp[ls(p)][i],dp[rs(p)][i]);
}
}
}
inline void main()
{
int n,m;cin>>n;
m=(1<<n);
build(1,m,1,n-1);
int q,tmp=0;cin>>q;
while(q--)
{
int x;cin>>x;
tmp^=(1<<x);
cout<<dp[1][tmp].ans<<'\n';
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::main();
return 0;
}
/*
*/