由于博主水平有限，目前只有 \(A,B,D\) 题题解。
A.最酷的排列
题目描述
\(T\) 组数据，给定长为 \(n\) 的序列 \(a\) 和下标集合 \(S\) ，你可以对序列进行任意次操作，每次选择一个区间并将其中元素升序排序。
求 \(\sum\limits_{i\in S}a_i\) 的最小可能值。
数据范围
- \(1\le n,\sum n\le 2\cdot 10^5,1\le a_i\le 10^9\)。
时间限制 \(\texttt{1s}\) ，空间限制 \(\texttt{1024MB}\)。
分析
注意到对一个区间排序等价于进行若干次冒泡，因此只需选择长为 \(2\) 的区间。
根据 \(\texttt{Subtask3}\) 的提示，从后往前扫描，最终某个位置的数不可能比已经扫描过的位置更小，即 \(a'_i\ge \min\limits_{i\le j\le n}a_j\)。
小根堆维护已经扫描且尚未使用过的数，每次碰到集合 \(S\) 中的下标，弹出其中的最小值，这是答案的下界。
再来证明上述方法得到的答案可以取到，对于 \(S\) 中的两个相邻下标 \(i,j\) ，如果在 \(i\) 处弹出的数（记为 \(b_i\)）比 \(j\) 处（记为 \(b_j\)）大，每次交换两个数可以让 \(a'_i=b_j,a'_j=b_i\) ，即完成 \(S\) 内部的冒泡。
时间复杂度 \(\mathcal O(\sum n\log n)\)。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n,t;
long long res;
int a[maxn];
char s[maxn];
int main()
{
for(scanf("%d",&t);t--;)
{
scanf("%d",&n),res=0;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%s",s+1);
priority_queue<int,vector<int>,greater<int>> q;
for(int i=n;i>=1;i--)
{
q.push(a[i]);
if(s[i]=='1') res+=q.top(),q.pop();
}
printf("%lld\n",res);
}
return 0;
}
B.里外一致
题目描述
给定长为 \(n\) 的序列 \(a\) ， \(q\) 次询问，每次给定 \(l,r\) ，求有多少 \(U=\{l,\cdots,r\}\) 的子集 \(S\) 满足 \(|\{a_i|i\in S\}|=|\{a_i|i\in U/S\}|\) ，对 \(2^{64}\) 取模。
数据范围
\(1\le n\le 3\cdot 10^5,1\le q\le 10^5,1\le a_i\le n\)。
时间限制 \(\texttt{2s}\) ，空间限制 \(\texttt{1024MB}\) 。
分析
先考虑 \(q=1\) 怎么做，假设不同数字在序列 \(a\) 中的出现次数分别为 \(cnt_1,\cdots,cnt_m\)。
\(f_{i,j}\) 表示考虑前 \(i\) 个 \(cnt\) ，\(|\{a_i|i\in S\}|-|\{a_i|i\in U/S\}|=j\) 的方案数。
容易写出转移方程：
\[f_{i,j}=f_{i-1,j-1}+f_{i-1,j}\cdot (2^{cnt_i}-2)+f_{i-1,j+1} \]用生成函数的视角理解，答案为：
\[[x^0]\prod_{i=1}^m(x+2^{cnt_i}-2+\frac 1x) \]本题非常 \(\texttt{tricky}\) 的一点是，由于答案对 \(2^{64}\) 取模，所以如果与\(2^{cnt_i}\)有关的项取太多对答案没有任何影响。
将 \(x-2+\frac 1x\) 和 \(2^{cnt_i}\) 拆开来看，注意到：
\[V_k=[x^0](x-2+\frac 1x)^k=[x^0](\sqrt x-\sqrt\frac 1x)^{2k}=(-1)^k\binom{2k}k \]\(g_{i,j}\) 表示考虑前 \(i\) 个 \(cnt\) ，有 \(j\) 项没选 \(2^{cnt_i}\) 的系数之和，那么答案为 \(\sum g_{m,j}V_{m-j}\) 。
转移方程 \(g_{i,j}=g_{i-1,j}+2^{cnt_i}\cdot g_{i-1,j-1}\) ，注意到第二维上限为 \(63\) ，否则对答案没有贡献。
预处理 \(V_k\) 即可获得一个 \(\mathcal O(64nq)\) 的做法，link。具体的，预处理阶乘中 \(2\) 的幂次，奇数部分的逆元可以用欧拉定理求出。
注意到 \(g\) 的转移本质上是背包，而背包问题可以支持撤回，用莫队维护 \(cnt\) 和 \(g\) 数组，可以做到 \(\mathcal O(64n\sqrt q)\)。
由于 \(q\) 很小，并且 \(cnt\ge 64\) 时没有贡献，我们希望将所有相同的 \(cnt\) 放在一起转移，这样可以把 \(64\) 的常数从 \(n\sqrt q\) 上拿下来。
记 \(cnt_i=x\) 出现了 \(c_x\) 次，将 \(g\) 的定义修改为考虑所有 \(cnt\le i\) 的情况，转移方程为 \(g_{i,k}\gets\binom{c_x}{k-j}\cdot 2^{i\cdot (k-j)}\cdot g_{i-1,j}\) 。
时间复杂度 \(\mathcal O(n\sqrt q+64\cdot 273\cdot q)\) ，由于卡不满，可以通过。
这里 \(273=\sum_{i=1}^{63}\lfloor\frac{63}i\rfloor\)，而且过的比较惊险，
如果被叉了或者能证明出更优复杂度可以叫我。注意非常重要的一点，下面代码中第 \(62\) 行 \(x\) 一定要倒序枚举，这样可以大幅减少转移次数。
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int B=1000,maxn=6e5+5;
int l,n,q,r;
int a[maxn],c[65],pw[maxn],bel[maxn],cnt[maxn];
ull fac[maxn],inv[maxn];
ull g[64],v[maxn],res[maxn];
struct node
{
int l,r,id;
bool operator<(const node &a)
{
return bel[l]!=bel[a.l]?l<a.l:r<a.r;
}
}f[maxn];
ull qpow(ull a,ull k)
{
ull res=1;
for(;k;a=a*a,k>>=1) if(k&1) res=res*a;
return res;
}
ull get_c(int n,int m)
{
int x=pw[n]-pw[m]-pw[n-m];
return x<64?(fac[n]*inv[m]*inv[n-m])<<x:0;
}
void init(int n)
{
fac[0]=1;
for(int i=1,j=0;i<=n;i++)
{
for(j=i,pw[i]=pw[i-1];!(j&1);j>>=1,pw[i]++) ;
fac[i]=fac[i-1]*j;
}
inv[n]=qpow(fac[n],(1ll<<63)-1);
for(int i=n,j=0;i>=1;i--)
{
for(j=i;!(j&1);j>>=1) ;
inv[i-1]=inv[i]*j;
}
for(int i=0;i<=(n>>1);i++) v[i]=(i&1?-1:1)*get_c(i<<1,i);
}
void add(int x,int v)
{
c[min(cnt[x],64)]--,cnt[x]+=v,c[min(cnt[x],64)]++;
}
int main()
{
scanf("%d%d",&n,&q),init(n<<1);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),bel[i]=(i-1)/B+1;
for(int i=1;i<=q;i++) scanf("%d%d",&f[i].l,&f[i].r),f[i].id=i;
sort(f+1,f+q+1);
for(int i=1,l=1,r=0;i<=q;i++)
{
while(l>f[i].l) add(a[--l],1);
while(r<f[i].r) add(a[++r],1);
while(l<f[i].l) add(a[l++],-1);
while(r>f[i].r) add(a[r--],-1);
int m=c[64];
for(int j=0;j<64;j++) g[j]=!j;
for(int x=63;x>=1;x--)
{
m+=c[x];
for(int j=63;j>=0;j--)
if(g[j]) for(int k=min({c[x],63-j,63/x});k>=1;k--)
g[j+k]+=(get_c(c[x],k)*g[j])<<(k*x);
}
for(int j=0;j<=min(m,63);j++) res[f[i].id]+=g[j]*v[m-j];
}
for(int i=1;i<=q;i++) printf("%llu\n",res[i]);
return 0;
}
D.兵棋
题目描述
对于长为 \(n\) 的 \(01\) 串 \(s\) ，定义一次操作为，删除所有满足 \(i\ge 2,s_i\neq s_{i-1}\) 的位置，并将剩余位置拼接起来。
给定长为 \(n\) 的由 \(0,1,?\) 组成的字符串 \(s\)，对于所有将 \(?\) 替换成 \(0\) 或 \(1\) 得到的字符串，求其经过 \(k\) 次操作后序列长度之和，对 \(998244353\) 取模。
数据范围
\(1\le n\le 10^5,1\le k\le 200\)。
时间限制 \(\texttt{2s}\) ，空间限制 \(\texttt{1024MB}\) 。
分析
对于一个已知的 \(01\) 串 \(s\) ，我们需要比模拟更快的方法求出其经过 \(k\) 次操作后的长度。
先考虑 \(k=1\) 的情况，容易发现这是将除第一段以外的每个连续段长度减一，但是可能会引起连续段合并。
这启发我们用 +1/-1 来代替 0/1 ，具体地，有以下结论：
记上一个未被删除的字符为 \(x\) ，将 \(x\) 赋值为 \(-1\) ， \(1-x\) 赋值为 \(+1\) ，如果权值到达 \(-1\)，那么下一个未被删除的字符为 \(x\)；如果权值到达 \(k+1\) ，那么下一个未被删除的字符为 \(1-x\) ，最后将权值清零。
接下来可以动态规划。
记 \(f_{i,x,j}\) 为考虑前 \(i\) 个字符，上一个未被删除的字符为 \(x\) ，当前权值为 \(j\) 的序列个数与长度之和，用二元组存储。
对于普通转移，我们只需要让序列个数和权值之和分别相加即可；对于涉及到新字符的转移，原先的每个序列都会产生 \(1\) 的贡献，将前者的序列个数加到后者的长度之和中即可。
时间复杂度 \(\mathcal O(nk)\)。
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int maxn=1e5+5,mod=998244353;
int k,n,res;
char s[maxn];
pii f[2][2][205];
void add(int &a,int b)
{
if((a+=b)>=mod) a-=mod;
}
void tran(pii &a,pii &b,bool op)
{
add(b.fi,a.fi),add(b.se,a.se);
if(op) add(b.se,a.fi);
}
int main()
{
scanf("%d%d%s",&n,&k,s+1);
if(s[1]!='1') f[1][0][0]=mp(1,1);
if(s[1]!='0') f[1][1][0]=mp(1,1);
for(int i=2;i<=n;i++)
{
memset(f[i&1],0,sizeof(f[i&1]));
for(int x=0;x<=1;x++)
for(int j=0;j<=k;j++)
{
pii &v=f[i-1&1][x][j];
if(!v.fi&&!v.se) continue;
if(s[i]-'0'!=(x^1)) j>0?tran(v,f[i&1][x][j-1],0):tran(v,f[i&1][x][0],1);
if(s[i]-'0'!=x) j<k?tran(v,f[i&1][x][j+1],0):tran(v,f[i&1][x^1][0],1);
}
}
for(int x=0;x<=1;x++) for(int j=0;j<=k;j++) add(res,f[n&1][x][j].se);
printf("%d\n",res);
return 0;
}