（2023 省选模拟 Round #4）
之前感冒了一阵子，错过了两场省选模拟，不过我不打算补（乐
成绩：0+42+0
（就是说 T1 写挂了）
A
题目大意
小 \(\omega\) 最近学习了分治 \(\text{FFT}\)，她想计算一类特殊的分治 \(\text{FFT}\) 的最小代价。分治的过程大致如下：
solve(l, r):
if r - l == 1:
process(l)
return
在开区间 (l, r) 中选取一个整数 mid
solve(l, mid)
fft(r - l)
solve(mid, r)
return
其中 process 函数执行时代价为 \(1\)。只有函数执行时计入代价。
其中 fft(n) 函数的代价计算方式如下：
- 设 \(p\) 为最小的满足 \(2^p\geq n\) 的整数，则代价为 \(p\cdot 2^p\)。
小 \(\omega\) 希望知道在合适地选取 mid 的值的情况下调用 solve(0, n) 的最小代价（对 \(998244353\) 取模）。
小 \(\omega\) 在此基础上还要对 \(n\) 进行修改，具体方法是对 \(n\) 加上或减去 \(2^b\)，你需要在每一次修改后输出你的答案。
\(n\) 特别大，输入的时候输入 \(k\) 段连续 \(1\) 的左右端点。对于所有数据，保证 \(0\le k,m\leq 1.5\times 10^5\)，\(0\le b_i, l_i, r_i\leq 10^9\)，保证 \(n\) 时刻为正。
题解
首先 dp 是容易的
注意到 solve(l,r) 的代价只与 \(r-l\) 有关
我们记 \(f_i\) 表示 solve(0,i) 的代价
那么根据题面里的代码，很容易给出状态转移方程
\[f_i=\min_{0<j<i} \{ f_j+f_{i-j}+p\cdot2^p \} \]其中 \(j\) 就是代码中选取的 \(mid\) ，\(p=\lceil log_2{i}\rceil\)
这么直接做 \(O(n^2)\)
我们写个暴力程序找找规律，会发现每次转移的位置 \(j=2^{p-1}\)
这样我们就可以推式子了
\[\begin{gather*} f_{2^p}=2f_{2^{p-1}}+p\cdot2^p\\ g_p=2g_{p-1}+p\cdot2^p\\ g_p=2(2(\cdots(g_0\cdots+(p-1)\cdot2^{p-1})+p\cdot2^p\\ g_p=2^p+(1+\dots+p)\cdot2^p\\ g_p=2^p+\frac{p(p+1)}{2}2^{p} \end{gather*} \]\[\begin{align*} f_n&=f_{2^t}+f_{n-2^t}+(t+1)\cdot2^{t+1} (n\ne2^p)\\ &=(1+2(t+1)+\frac{t(t+1)}{2})2^t+f_{n-2^t}\\ &=\sum_{(n>>t)\&1=1}\left((1+2(t+1)+\frac{t(t+1)}{2})2^t\right)-(l_1+1)2^{l_1+1}\\ &=\sum_{(n>>t)\&1=1}\left((t^2+5t+6)2^{t-1}\right)-(l_1+1)2^{l_1+1}\\ \end{align*} \]现在我们只需要求连续一段区间的和
使用错项相减或待定系数法等技巧可以求出
\[\sum_{t=L}^{R}\left((t^2+5t+6)2^{t-1}\right)=2^R(R^2+3R+4)-2^{L-1}((L-1)^2+2(L-1)+4) \]使用 set 可以维护连续的全 \(1\) 区间，细节有点多不过还好
时间复杂度 \(O((k+m)\log P)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1.5e5+5, P = 998244353;
int k,m;
int qpow(int a, int b) { int res=1; for(; b; b>>=1,a=(ll)a*a%P) if(b&1) res=(ll)a*res%P; return res; }
int work(int L, int R) { auto f=[&](const int &x) { if(x==-1) return 1ll; return (ll)qpow(2,x)*((ll)x*(x+3)%P+4)%P; }; return (f(R)-f(L-1)+P)%P; }
struct Misaka { int l,r; friend bool operator< (const Misaka &a, const Misaka &b) { return a.l<b.l; } };
set<Misaka> st;
int main()
{
scanf("%d%d",&k,&m);
int ans=0;
for(int i=1,l,r; i<=k; i++)
{
scanf("%d%d",&l,&r); st.insert({l,r});
// for(int j=l; j<=r; j++) (ans+=(ll)qpow(2,j-1)*(j+2)%P*(j+3)%P)%=P;
(ans+=work(l,r))%=P;
}
// printf("%d\n",ans);
for(int i=1,op,b; i<=m; i++)
{
scanf("%d%d",&op,&b);
// printf("b=%d\n",b);
if(op==0)
{
auto it=st.lower_bound((Misaka){b+1,b+1});
if(it==st.begin() or (*prev(it)).r<b)
{
(ans+=work(b,b))%=P; st.insert({b,b});
}
else
{
// puts("!!2!!");
auto t=*prev(it); Misaka t2={t.r+1,t.r+1};
ans=(ans-work(b,t.r)+P)%P; (ans+=work(t.r+1,t.r+1))%=P; t.r=b-1;
st.erase(prev(it)); if(t.l<=t.r) st.insert(t); st.insert(t2);
}
}
else
{
auto it=st.lower_bound((Misaka){b+1,b+1});
if(it==st.begin() or (*prev(it)).r<b)
{
auto t=*it; (ans+=work(b,t.l-1))%=P; ans=(ans-work(t.l,t.l)+P)%P;
// printf("[%d,%d]\n",t.l,t.r);
st.erase(it); st.insert({b,t.l-1}); t.l++;
// puts("!!");
if(t.l<=t.r) st.insert(t);
}
else
{
auto t=*prev(it); ans=(ans-work(b,b)+P)%P; st.erase(prev(it));
if(t.l<=b-1) st.insert({t.l,b-1});
if(b+1<=t.r) st.insert({b+1,t.r});
}
}
auto it=st.lower_bound((Misaka){b,b});
if(it!=st.end())
{
auto u=*it;
if(it!=st.begin() and u.l==(*prev(it)).r+1)
{
u.l=(*prev(it)).l;
st.erase(prev(it));
}
if(it!=prev(st.end()) and u.r==(*next(it)).l-1)
{
u.r=(*next(it)).r;
st.erase(next(it));
}
st.erase(it); st.insert(u);
}
int t=(*st.begin()).l; int lv=(ll)(t+1)*qpow(2,t+1)%P;
printf("%d\n",(ans-lv+P)%P);
}
return 0;
}
B
题目大意
小 \(\omega\) 是一个喜欢随机的人，所以他又开始随机了。
他有一个长度为 \(n\) 的排列，他想将它排序。于是他写了一个冒泡排序。其中冒泡一次的伪代码如下：
for j = 2 to n do
if a[j] < a[j - 1] then
swap(a[j], a[j - 1])
这当然是对的了，于是小 \(\omega\) 愉快的使用了它。
但是，他发现出现了问题！第 \(2\) 行的比较可能会返回错误的结果！
具体的来说，它有 \(233 / 12345679\) 的概率会返回错误结果，否则它将会返回正确的结果。
小 \(\omega\) 发现这样排序就会错误，于是，他只好做了 \(m\) 遍冒泡，希望提高正确率。
现在，钱菜鸡想知道冒泡 \(m\) 次后第 \(i\) 个数的期望大小，你能帮帮他吗。
\(n\leq 15, m \leq 500\)
题解
暴力很简单
每个排列可以看做一个点，每做一次交换，有两条出边，于是可以在上面 dp
\(f_{i,j}\) 表示交换 \(j\) 次后，是排列 \(i\) 的概率
转移是容易的
时间复杂度 \(O(n!mn)\) ，\(42\) 分
正解只需要做一个优化
冒泡 \(m\) 次后 \(E(a_i)=P(a_i\geq1)+P(a_i\geq2)+\dots+P(a_i\geq n)\)
然后对于 \(P(a_i\geq k)\)，可以把 \(\geq k\) 变成 \(1\) 反之 \(0\)，然后 \(dp\)
因为状态数是 \(\binom{n}{k}\) ，所以时间复杂度是 \(\sum \binom{n}{k}=2^n\)，可以通过
事实上这些状态互不重复，可以一起 dp
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 20, M = 33000, P = 12345678;
int a[N],pos[N],n,m,f[M][2],ans[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) scanf("%d",&a[i]),pos[a[i]]=i;
for(int i=n,cur=0; i; i--) { cur|=(1<<(pos[i]-1)); f[cur][0]=1; }
int t=0;
for(int i=1; i<=m; i++) for(int j=1; j<n; j++)
{
int swp=(1<<(j-1))|(1<<j);
for(int u=0; u<(1<<n); u++) if(f[u][t])
{
int t1=(u>>(j-1))&1; int t2=(u>>j)&1;
int v=(t1==t2)?u:(u^swp); int p1=(t1<t2)?233:(1-233+P);
(f[u][t^1]+=(ll)(1-p1+P)*f[u][t]%P)%=P;
(f[v][t^1]+=(ll)p1*f[u][t]%P)%=P;
}
for(int u=0; u<(1<<n); u++) f[u][t]=0; t^=1;
}
for(int u=0; u<(1<<n); u++) for(int i=0; i<n; i++) if((u>>i)&1) (ans[i+1]+=f[u][t])%=P;
for(int i=1; i<=n; i++) printf("%d ",ans[i]);
return 0;
}