当前位置：首页 > news >正文

2026 NOI 做题记录（二）

news 2025/9/14 23:25:16

Contest Link

$\text{By DaiRuiChen007}$

A. [ARC194E] Swap 0^X and 1^Y (3)

Problem Link

删掉所有的串 $0^x$ 以及 $1^y$，每次操作不会跨过里面的连续段，因此剩下的串必定相同。

取出每个连续段，任意两个 $0$ 连续段在原串中中间 $1$ 个数相等，反之亦然。

不难证明充分性。

时间复杂度 $\mathcal O(n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
struct seg { int c,d; };
int n,p[2]; string s,t;
array <int,2> a[MAXN],b[MAXN];
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>p[0]>>p[1]>>s>>t;vector <seg> fs,ft;for(int i=0,j=-1;i<n;++i) {if(i==n-1||s[i]!=s[i+1]) fs.push_back({s[i]-'0',i-j}),j=i;}for(int i=0,j=-1;i<n;++i) {if(i==n-1||t[i]!=t[i+1]) ft.push_back({t[i]-'0',i-j}),j=i;}vector <int> gs,gt;for(int i=0;i<(int)fs.size();++i) {a[i][fs[i].c]+=fs[i].d,a[i+1]=a[i];if(fs[i].d%p[fs[i].c]) gs.push_back(i);}for(int i=0;i<(int)ft.size();++i) {b[i][ft[i].c]+=ft[i].d,b[i+1]=b[i];if(ft[i].d%p[ft[i].c]) gt.push_back(i);}if(gs.size()!=gt.size()||a[fs.size()]!=b[ft.size()]) return cout<<"No\n",0;for(int i=0;i<(int)gs.size();++i) {int h=fs[gs[i]].c;if(h!=ft[gt[i]].c||fs[gs[i]].d%p[h]!=ft[gt[i]].d%p[h]) return cout<<"No\n",0;if(a[gs[i]][h^1]!=b[gt[i]][h^1]) return cout<<"No\n",0;}cout<<"Yes\n";return 0;
}

B. [ARC195E] Random Tree Distance (2)

Problem Link

树上距离拆成 $d_u+d_v-2d_{\mathrm{LCA}(u,v)}$，深度容易计算，只要算每个 $x$ 为 $\mathrm{LCA}$ 的概率。

枚举 $u\to x,v\to x$ 的路径，其他点父亲任意，路径上的点父亲唯一，因此概率就是 $\dfrac{1}{p_up_v}(\prod_{u<i<v}1+\frac1{i})(\prod_{x<i<u}1+\frac{2}{p_i})$，不难维护。

时间复杂度 $\mathcal O(n)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+5,MOD=998244353;
int n,m;
ll inv[MAXN],a[MAXN],d[MAXN],fac=1,p[MAXN],q[MAXN],f[MAXN];
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m,inv[1]=1;for(int i=2;i<=n;++i) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD,fac=fac*(i-1)%MOD;for(int i=2,s=0;i<=n;++i) cin>>a[i],d[i]=(s*inv[i-1]+a[i])%MOD,s=(s+d[i])%MOD;p[1]=q[1]=1;for(int i=2;i<=n;++i) {p[i]=p[i-1]*(1+inv[i-1])%MOD,q[i]=q[i-1]*(1+MOD-inv[i])%MOD;f[i]=(f[i-1]*(1+2*inv[i-1])+d[i])%MOD;}for(int u,v;m--;) {cin>>u>>v;ll s=d[u]+d[v],z=p[v-1]*q[u]%MOD*inv[v-1]%MOD;if(u>1) s=(s-2*z*d[u])%MOD,z=z*inv[u-1]%MOD,s=(s-2*z*f[u-1])%MOD;cout<<(s+MOD)*fac%MOD<<"\n";}return 0;
}

C. [AGC071C] Orientable as Desired (5)

Problem Link

首先尝试构造一些序列：所有点填 $0$，那么可以解决非二分图。

否则考虑进一步构造：其中一个点任意填，其他点填 $0$，那么删掉该点后的每个连通块到该点的边都同向。

因此对每个 $u$ 求出在其在每个点双中的度数，然后背包判断是否有不能表出的数，如果有就能解决。

注意到求最小不能表出元素是经典问题，可以 $\mathcal O(n\log n)$ 解决。

可以证明该条件充分：从圆方树上从上往下逐个考虑，用儿子的方点来调整度数即可。

时间复杂度 $\mathcal O(m\log m)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
vector <int> G[MAXN],E[MAXN],D[MAXN];
int stk[MAXN],tp,low[MAXN],dfn[MAXN],dcnt,vcnt,bl[MAXN],d[MAXN];
bool cl[MAXN],ok,ins[MAXN];
void tarjan(int u) {low[u]=dfn[u]=++dcnt,stk[++tp]=u,ins[u]=true;for(int v:G[u]) {if(!dfn[v]) {cl[v]=cl[u]^1,tarjan(v),low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]) {for(++vcnt;ins[v];ins[stk[tp--]]=false) bl[stk[tp]]=vcnt;}} else low[u]=min(low[u],dfn[v]),ok&=cl[u]^cl[v];}
}
int n,m;
void solve() {cin>>n>>m,dcnt=vcnt=tp=0,ok=1;for(int i=1;i<=n;++i) G[i].clear(),E[i].clear(),D[i].clear(),stk[i]=d[i]=bl[i]=low[i]=dfn[i]=ins[i]=cl[i]=0;for(int i=1,u,v;i<=m;++i) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);tarjan(1);if(!ok) return cout<<"Yes\n",void();for(int u=1;u<=n;++u) for(int v:G[u]) if(dfn[u]>dfn[v]) E[bl[u]].push_back(u),E[bl[u]].push_back(v);for(int i=1;i<=vcnt;++i) {for(int x:E[i]) ++d[x];for(int x:E[i]) if(d[x]) D[x].push_back(d[x]),d[x]=0;}for(int i=1;i<=n;++i) {int h=1;sort(D[i].begin(),D[i].end());for(int z:D[i]) {if(z>h) return cout<<"Yes\n",void();else h+=z;}}cout<<"No\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}

*D. [AGC072A] Rhythm Game (7)

Problem Link

首先走来回看成在 $[t_i-x_i,t_i-x_i+D)$ 范围内向该按钮移动，用 $2x_i$ 完成。

如果所有 $t_i-x_i$ 都 $\le 0$，那么问题可以看成最小化最大前缀和，用 Exchange Argument 能得到最优策略为按 $t_i+x_i$ 升序依次访问。

考虑原问题，按 $t_i+x_i$ 排序后，如果我们顺序访问 $1\sim i$ 直接访问 $j$，则结束时间 $\ge t_j+x_j$，则对于任意 $k\in (i,j)$ 都有 $t_j+x_j\ge t_k+x_k>t_k$，所以这些点没有了 $t_k$ 限制，接下来肯定按 $i+1\sim j-1$ 依次访问。

$f_i$ 表示处理 $[1,i]$ 的最小代价，然后转移到 $f_j$，中间加入 $j,i+1\sim j-1$，写出式子容易做到 $\mathcal O(1)$ 计算代价。

时间复杂度 $\mathcal O(n^2)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5005;
const ll inf=1e18;
struct info { ll t,x; } a[MAXN];
int n;
ll m,f[MAXN];
void solve() {cin>>n>>m;for(int i=1;i<=n;++i) cin>>a[i].t>>a[i].x;sort(a+1,a+n+1,[&](auto u,auto v){ return u.x+u.t<v.x+v.t; });f[0]=0;for(int i=1;i<=n;++i) {f[i]=inf; ll lim=inf,su=0;for(int j=i-1;~j;--j) {ll z=max(f[j],a[i].t-a[i].x)+2*a[i].x;if(z<=a[i].t+a[i].x+m&&z<=lim) f[i]=min(f[i],z+su);su+=2*a[j].x,lim=min(lim-2*a[j].x,a[j].t-a[j].x+m);}}cout<<(f[n]>=inf?"No\n":"Yes\n");
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}

E. [ARC197E] Four Square Tiles (2)

Problem Link

简单题，首先从上到下从左到右把矩形标号 $1,2,3,4$，必须要满足 $x_1+k\le x_2,x_3+k\le x_4,y_1+k\le y_3,y_2+k\le y_4$。

此时可以保证 $(1,2),(3,4),(1,3),(2,4)$ 无交，容斥掉 $(1,4)$ 或 $(2,3)$ 相交，两种对称，考虑第一种，此时要求 $x_1\le x_4<x_1+k\le x_2,x_3+k\le x_4$ 且 $y_1\le y_4<y_1+k\le y_3,y_2+k\le y_4$，行列方案独立，枚举 $x_1,x_4$ 列出式子后优化成 $\mathcal O(1)$ 即可。

时间复杂度 $\mathcal O(1)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=998244353,inv=291154603;
ll S(ll x) { return x*(x+1)/2%MOD; }
ll f(ll n) { return inv*(n-1)%MOD*n%MOD*(n+1)%MOD*(n+2)%MOD; }
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) {ll n,m,k;cin>>k>>n>>m,n-=2*k-1,m-=2*k-1;if(min(n,m)<0) cout<<"0\n";else cout<<(S(n)*S(n)%MOD*S(m)%MOD*S(m)%MOD+(MOD-f(n))*f(m)*2)%MOD<<"\n";}return 0;
}

F. [ARC200D] |A + A| (4.5)

Problem Link

首先观察到选择 $[0,x]$ 可以表示出 $2x+1$ 个数，选 $[0,x]\setminus{1}$ 可以表示出 $2x$ 个数（$x\ge 3$）。

那么只要考虑 $k\in\{2,4\}$ 的情况，可以分讨证明此时必定有 $2\mid m$ 或 $4\mid m$，对应构造就是 $\{0,\frac m2\}$ 和 $\{0,\frac m4,\frac m2\}$。

时间复杂度 $\mathcal O(m)$。

代码：

#include<bits/stdc++.h>
using namespace std;
void solve() {int m,k,n;cin>>m>>k;if(k==m) {cout<<"Yes\n"<<m<<"\n";for(int i=0;i<m;++i) cout<<i<<" \n"[i==m-1];return ;}if(k%2) {n=k/2,cout<<"Yes\n"<<n+1<<"\n";for(int i=0;i<=n;++i) cout<<i<<" \n"[i==n];return ;}if(k>4) {n=k/2,cout<<"Yes\n"<<n<<"\n";for(int i=0;i<=n;++i) if(i^1) cout<<i<<" \n"[i==n];return ;}if(k==2) {if(m&1) cout<<"No\n";else cout<<"Yes\n2\n0 "<<m/2<<"\n";return ;}if(m%4) cout<<"No\n";else cout<<"Yes\n3\n0 "<<m/4<<" "<<m/2<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}

G. [AGC069B] Pair Guessing (6.5)

Problem Link

每次询问得到 $0$ 就删掉一行一列，直到得到 $1$，不妨假设此时就是第一次询问。

然后剩 $n-1$ 次询问，每次可以排除一个行上和列上的点。

前 $n-2$ 次得到 $1$ 只要额外询问一次，最后一次询问时要求两个点至少有一个 $0$。

因此我们要确定一种询问行列的顺序，使得在每个时刻停下时范围内至少有一个 $0$。

停止时 $n=1$ 不需要该限制，如果停止时 $n=2$，且初始 $n\ge 3$ 也不需要该限制。

建立二分图，$a_{i,j}=0$ 连接 $L_i,R_j$，那么要求就是把左右点集分成 $n$ 对，每对有一条边向编号更大的对连接。

那么每对只要保留一条边，考虑怎样的边集合法，显然边集中无环，而每条边能加入一个新的对。

因此只要存在森林边数 $\ge n-2$ 即可，直接并查集。

时间复杂度 $\mathcal O(n^2)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=505;
int n,p[MAXN],dsu[MAXN*2],siz[MAXN*2];
bool a[MAXN][MAXN];
int find(int x) { return dsu[x]^x?dsu[x]=find(dsu[x]):x; }
void solve() {cin>>n;for(int i=1;i<=2*n;++i) dsu[i]=i,siz[i]=0;for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) {char c; cin>>c; if(c=='0') dsu[find(i)]=find(j+n);}for(int i=1;i<=2*n;++i) ++siz[find(i)];int ct=1;for(int i=1;i<=2*n;++i) if(siz[i]) ct+=siz[i]-1;cout<<(ct>=n-(n>2)?"Yes\n":"No\n");
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}

H. [AGC070C] No Streak

Problem Link

看成 $\pm1,0$ 序列，考虑反射容斥去掉前缀和 $\ge 0$ 的代价，计算 $(0,0)\to (n,a-b)$ 的代价容易做到 $\mathcal O(n)$。

对 $x=-1$ 对称变成统计到 $(n,-2-b+a)$ 的方案数，但是如果对称前的下一步是 $+1$，则对称后出现两个 $-1$，考虑删掉其中一个，那么这部分等价于统计到 $(n-1,-1-b+a)$ 的方案数。

否则对称前下一步是 $0$，则删掉这个 $0$，统计到 $(n-1,-2-b+a)$ 的方案数，但 $0$ 后面一步是 $+1$ 的路径又没统计，把这个对称后的 $-1$ 删掉统计到 $(n-2,-1-b+a)$ 的方案数。

可以证明这样计数不重不漏。

时间复杂度 $\mathcal O(n)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e7+5,MOD=1e9+7;
ll fac[MAXN],ifac[MAXN];
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
ll C(int x,int y) { return y<0||y>x?0:fac[x]*ifac[y]%MOD*ifac[x-y]%MOD; }
ll ask(int x,int y,int z) {if(x<0||y<0) return 0;if(!x||!y) return C(z+1,x+y);ll s=0;for(int i=1;i<=x;++i) for(int j:{i-1,i,i+1}) if(1<=j&&j<=y)  {s=(s+(i==j?2:1)*C(x-1,i-1)*C(y-1,j-1)%MOD*C(z+i+j,x+y))%MOD;}return s;
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n,a,b,c;cin>>n>>a>>b,c=n-a-b;for(int i=fac[0]=1;i<=n;++i) fac[i]=fac[i-1]*i%MOD;ifac[n]=ksm(fac[n]);for(int i=n;i;--i) ifac[i-1]=ifac[i]*i%MOD;ll s=ask(a,b,c)-ask(b-1,a,c)-ask(b-1,a+1,c-1)-ask(b-1,a,c-1);cout<<(s%MOD+MOD)%MOD<<"\n";return 0;
}

I. [ARC191E] Unfair Game (3)

Problem Link

注意到每个袋子中的游戏独立，且只会让持有者多操作一次或者无影响，具体属于哪种情况可以直接打表找规律解决。

然后变成先手领先的袋子数量多于后手领先的袋子数量，简单组合数处理。

时间复杂度 $\mathcal O(n)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5,MOD=998244353;
ll fac[MAXN],ifac[MAXN],f[MAXN];
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
ll C(int x,int y) { return y<0||y>x?0:fac[x]*ifac[y]%MOD*ifac[x-y]%MOD; }
bool F(int x,int y,int a,int b) {if(x%2==0&&y%2==0) return (a+b)&1;if(x%2==1&&y%2==1) return b&1;if(x%2==1) return a<2&&(b&1);else return a||(b&1);
}
int n,x,y,cx=0,cy=0;
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>x>>y;for(int i=fac[0]=1;i<=n;++i) fac[i]=fac[i-1]*i%MOD;ifac[n]=ksm(fac[n]);for(int i=n;i;--i) ifac[i-1]=ifac[i]*i%MOD;int c[4]={0,0,0,0};for(int i=1,a,b;i<=n;++i) {cin>>a>>b;int l=F(x,y,a,b),r=F(y,x,a,b);++c[l*2+r];}for(int i=c[3];~i;--i) f[i]=(f[i+1]+C(c[3],i))%MOD;ll s=0;for(int i=0;i<=c[1]+c[2];++i) {int q=c[3]+c[1]-i;q=min(q<0?0:q/2+1,c[3]+1);s=(s+C(c[1]+c[2],i)*f[q])%MOD;}cout<<s*ksm(2,c[0])%MOD<<"\n";return 0;
}

J. [ARC192E] Snuke's Kyoto Trip (2)

Problem Link

分讨一下非法路径要么起点非法，要么经过删除区域的左或下边界。

那么我们要计算某个 $n\times m$ 矩形内路径总数以及从 $(0,0)$ 出发的路径数，组合数前缀和推式子即可。

时间复杂度 $\mathcal O(\max(n,m))$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2.1e6+5,MOD=998244353;
ll fac[MAXN],ifac[MAXN];
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
ll C(int x,int y) { return y<0||y>x?0:fac[x]*ifac[y]%MOD*ifac[x-y]%MOD; }
ll F(int n,int m) { return n<0||m<0?0:C(n+m+2,n+1)-1; }
ll G(int n,int m) { return n<0||m<0?0:(C(n+m+4,m+2)+MOD-1ll*(m+2)*(n+2)%MOD-1)%MOD; }
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);for(int i=fac[0]=1;i<MAXN;++i) fac[i]=fac[i-1]*i%MOD;ifac[MAXN-1]=ksm(fac[MAXN-1]);for(int i=MAXN-1;i;--i) ifac[i-1]=ifac[i]*i%MOD;int n,m,lx,rx,ly,ry;cin>>n>>m>>lx>>rx>>ly>>ry;ll s=G(n,m);for(int i=ly;i<=ry;++i) s=(s-F(lx-1,i)*F(n-lx,m-i))%MOD;for(int i=lx;i<=rx;++i) s=(s-F(i,ly-1)*F(n-i,m-ly))%MOD;s=(s-G(n-lx,m-ly)+G(n-lx,m-ry-1)+G(n-rx-1,m-ly)-G(n-rx-1,m-ry-1))%MOD;cout<<(s+MOD)%MOD<<"\n";return 0;
}

K. [AGC071B] Maximum Bracket Subsequence (5.5)

Problem Link

考虑 $S=()^{k/2}$，那么枚举子序列自动机匹配的 $S$，此时可以在每个字符前面插入人一个不等于该字符的元素，末尾可以任意放。

对于一般情况仍然考虑插入，手玩每个位置插入后是否可以调整：把每个极小的合法括号序列划分成段，首先 $)$ 只能插入在每个段的开头，$($ 只能插在每个段开头第一个 $)$ 前面，并且找到首个 $))$ 子串，这个子串后面不能插入形成 $()$ 子序列。

枚举 $)($ 分界线然后插板计算即可。

时间复杂度 $\mathcal O(k)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e7+5,MOD=998244353;
ll fac[MAXN],ifac[MAXN],pw[MAXN];
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
ll C(int x,int y) { return y<0||y>x?0:fac[x]*ifac[y]%MOD*ifac[x-y]%MOD; }
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);for(int i=fac[0]=pw[0]=1;i<MAXN;++i) fac[i]=fac[i-1]*i%MOD,pw[i]=pw[i-1]*2%MOD;ifac[MAXN-1]=ksm(fac[MAXN-1]);for(int i=MAXN-1;i;--i) ifac[i-1]=ifac[i]*i%MOD;int n,m,k=0,d=0,o=0,c=0; string S;cin>>n>>m>>S;for(auto h:S) {if(h=='(') d+=!(k++),o=0;else {if(o&&!c) c=d;--k,o=1;}}ll s=0;if(!c) {for(int i=0;i<=n-m;++i) s=(s+pw[n-m-i]*C(i+m-1,m-1))%MOD;return cout<<s<<"\n",0;}int x=d-c+1;for(int i=0;i<=x;++i) {s=(s+C(x,i)*(i+1)%MOD*C(n-m+c*2-1,i+c*2-1))%MOD;s=(s+C(x,i)*i%MOD*C(n-m+c*2-1,i+c*2))%MOD;}cout<<s<<"\n";return 0;
}

L. [ARC196C] Strongly Connected (3)

Problem Link

强连通相当于每条边 $(i,i+1)$ 都被至少一条回边覆盖。

容斥未被覆盖的回边，$f_i$ 表示 $[1,i]$ 中首条这样的回边为 $(i,i+1)$ 的方案。

设 $(1,i)$ 中起终点数量为 $s_i,t_i$，转移为 $f_j=-\sum_{i<j}f_i\dfrac{(s_j-t_i)!}{(s_j-t_j)!}$，分治 NTT 优化。

时间复杂度 $\mathcal O(n\log^2n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353,N=1<<19,G=3;
int fac[N],ifac[N];
namespace P {
int rev[N],inv[N],w[N<<1];
int ksm(int a,int b=MOD-2) {int ret=1;for(;b;a=1ll*a*a%MOD,b=b>>1) if(b&1) ret=1ll*ret*a%MOD;return ret;
}
void poly_init() {inv[1]=1;for(int i=2;i<N;++i) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;fac[0]=ifac[0]=1;for(int i=1;i<N;++i) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*inv[i]%MOD;for(int k=1;k<=N;k<<=1) {int x=ksm(G,(MOD-1)/k); w[k]=1;for(int i=1;i<k;++i) w[i+k]=1ll*x*w[i+k-1]%MOD;}
}
int plen(int x) { int y=1; for(;y<x;y<<=1); return y;  }
void ntt(int *f,bool idft,int n) {for(int i=0;i<n;++i) {rev[i]=(rev[i>>1]>>1);if(i&1) rev[i]|=n>>1;}for(int i=0;i<n;++i) if(rev[i]<i) swap(f[i],f[rev[i]]);for(int k=2,x,y;k<=n;k<<=1) {for(int i=0;i<n;i+=k) {for(int j=i;j<i+k/2;++j) {x=f[j],y=1ll*f[j+k/2]*w[k+j-i]%MOD;f[j]=(x+y>=MOD)?x+y-MOD:x+y,f[j+k/2]=(x>=y)?x-y:x+MOD-y;}}}if(idft) {reverse(f+1,f+n);for(int i=0,x=ksm(n);i<n;++i) f[i]=1ll*f[i]*x%MOD;}
}
int poly_mul(const int *f,const int *g,int *h,int n,int m) {static int a[N],b[N];for(int i=0;i<n;++i) a[i]=f[i];for(int i=0;i<m;++i) b[i]=g[i];int len=plen(n+m-1);ntt(a,0,len),ntt(b,0,len);for(int i=0;i<len;++i) h[i]=1ll*a[i]*b[i]%MOD;ntt(h,1,len);memset(a,0,sizeof(int)*len);memset(b,0,sizeof(int)*len);return len;
}
}
int n,m,s[N],t[N],f[N],a[N],b[N],c[N];
void cdq(int l,int r) {if(l==r) return f[l]=1ll*f[l]*ifac[s[l]-t[l]]%MOD,void();int mid=(l+r)>>1;cdq(l,mid);int u=max(0,s[l]-t[r]),v=t[l];for(int i=u;i<=s[r]-t[l];++i) a[i-u]=fac[i];for(int i=l;i<=mid;++i) b[t[i]-v]=(b[t[i]-v]+MOD-f[i])%MOD;int o=P::poly_mul(a,b,c,s[r]-t[l]-u+1,t[mid]-v+1);for(int i=mid+1;i<=r;++i) f[i]=(f[i]+c[s[i]-u-v])%MOD;memset(a,0,o<<2),memset(b,0,o<<2),memset(c,0,o<<2);cdq(mid+1,r);
}
signed main() {P::poly_init();cin>>n;for(int i=1,x=0,y=0;i<=n*2;++i) {char o; cin>>o,(o=='W'?++x:++y);if(x>=y) s[++m]=x,t[m]=y;}f[0]=MOD-1,cdq(0,m),cout<<f[m]<<"\n";return 0;
}

M. [ARC196D] Roadway (3)

Problem Link

考虑前缀和序列，那么 $u\to v$ 相当于 $s_u=s_v$ 且 $s_{u+1,v-1}$ 全部大于或小于 $s_u$。

合法当且仅当拓扑序列无环，不难证明当且仅当如下条件均被满足时合法：

$u<v$ 的所有区间 $[u,v)$ 要么包含要么相离。
$u>v$ 的所有区间 $[v,u)$ 要么包含要么相离。
没有区间 $\min(u,v)$ 相同，没有区间 $\max(u,v)$ 相同。

注意到每个 $l$ 能合法的最大 $r$ 递增，双指针预处理出来即可。

时间复杂度 $\mathcal O(m\log m+q)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+5,N=1<<19,inf=1e9;
struct Heap {priority_queue <int> qi,qo;void ins(int x) { qi.push(x); }void ers(int x) { qo.push(x); }int top() {while(qo.size()&&qi.top()==qo.top()) qi.pop(),qo.pop();return qi.size()?qi.top():-inf;}
};
int n,m,q,L[MAXN],R[MAXN],p[MAXN],o[MAXN];
struct Segt {Heap f[MAXN]; int tr[N*2];Segt() { fill(tr,tr+N*2,-inf); }void upd(int x,int v,bool h) {h?f[x].ins(v):f[x].ers(v),tr[x+N]=f[x].top();for(x+=N;x>1;x>>=1) tr[x>>1]=max(tr[x],tr[x^1]);}int qry(int l,int r) {int s=-inf;for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) {if(~l&1) s=max(s,tr[l^1]);if(r&1) s=max(s,tr[r^1]);}return s;}
}	TL[2],TR[2];
int cl[MAXN],cr[MAXN];
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m>>q;for(int i=1;i<=m;++i) {cin>>L[i]>>R[i];if(L[i]>R[i]) swap(L[i],R[i]),o[i]=1;}for(int i=1,j=1;i<=m;++i) {for(;j<=m&&TR[o[j]].qry(L[j]+1,R[j]-1)<=R[j]&&-TL[o[j]].qry(L[j]+1,R[j]-1)>=L[j]&&!cl[L[j]]&&!cr[R[j]];++j)  {TR[o[j]].upd(L[j],R[j],1),TL[o[j]].upd(R[j],-L[j],1),++cl[L[j]],++cr[R[j]];}p[i]=j,TR[o[i]].upd(L[i],R[i],0),TL[o[i]].upd(R[i],-L[i],0),--cl[L[i]],--cr[R[i]];}for(int l,r;q--;) cin>>l>>r,cout<<(r<p[l]?"Yes\n":"No\n");return 0;
}

*N. [AGC072B] AGC Language (8)

Problem Link

假设没有第一步操作，首先考虑一个 $\pm 1$ 序列的操作次数，注意到一次操作只能给前缀和的某一项 $+2$，因此答案就是 $\sum_i \lceil\frac 12\max(0,-s_i)\rceil$，构造很平凡，每次选一个 $s_i\le 0$ 且 $c_i=+1$ 的位置即可。

然后加上第一步操作，设区间为 $[l,r]$，则 $[l,r]$ 内部的 $s_i$ 贡献变成 $\sum_{l\le i\le r} \lceil\frac 12\max(0,s_i-s_l-s_r)\rceil$。

显然 $s_l,s_r$ 非负，否则可以移动到左侧或右侧第一个非负值上，把 $s$ 序列按 $s_i=0$ 的位置分段，则 $s_l,s_r$ 在同一个 $s_i>0$ 的段内任意取值都不影响减小的代价，显然取段内最大值最优。

进一步如果 $l'<l,s_{l'}\ge s_l$ 则 $l'$ 严格优于 $l$，所以取出所有可能的 $l$ 的前缀最大值，以及所有可能的 $r$ 的后缀最大值。

注意到每个 $l$ 所在段长 $\ge 2s_l$，因此 $l,r$ 的个数分别都是 $\mathcal O(\sqrt n)$ 级别。

考虑如何 $\mathcal O(1)$ 计算答案，即维护 $\sum_{l\le i\le r} \lceil\frac 12\max(0,s_i-s_l-s_r)\rceil$，注意到我们的选出的 $s_l,s_r$ 一定是 $s$ 的前缀和后缀最大值，因此 $i\not\in[l,r]$ 的贡献一定为 $0$，所以只要维护 $f_x=\sum_{i=1}^n\lceil\frac 12\max(0,s_i-x)\rceil$。

然后是重复 $k$ 次的答案，显然可能的 $l$ 和 $r$ 不变，只要求最小的 $a_l+b_r+kf_{s_l+s_r}$，维护凸壳即可。

时间复杂度 $\mathcal O(n)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e6+5;
const ll inf=1e18;
int n,m,a[MAXN],s[MAXN],t[MAXN],ms,mt,ct[MAXN];
ll sl[MAXN],sr[MAXN],d[MAXN],f[MAXN],z[MAXN];
struct seg { ll k,b; int l,r; } b[MAXN];
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m,n*=2;vector <int> p{0};for(int i=1;i<=n;++i) {char c; cin>>c,a[i]=a[i-1]+(c=='A'?1:-1);if(!a[i]) p.push_back(i);}s[0]=0,t[0]=n;for(int i=1,x=0;i<(int)p.size();++i) {int h=max_element(a+p[i-1],a+p[i])-a;if(a[h]>x) x=a[h],s[++ms]=h;}for(int i=p.size()-1,x=0;i;--i) {int h=max_element(a+p[i-1],a+p[i])-a;if(a[h]>x) x=a[h],t[++mt]=h;}for(int i=0;i<=n;++i) sl[i]=(i?sl[i-1]:0)+(max(0,-a[i])+1)/2;for(int i=n;i>=0;--i) sr[i]=sr[i+1]+(max(0,-a[i])+1)/2;for(int i=0;i<=n;++i) if(a[i]>=0) ++ct[a[i]];for(int i=n,w[2]={0,0};i>=0;--i) d[i]=d[i+1]+w[(i&1)^1],w[i&1]+=ct[i];for(int i=0;i<=n+1;++i) z[i]=inf;for(int i=0;i<=ms;++i) for(int j=0;j<=mt;++j) {z[min(n+1,a[s[i]]+a[t[j]])]=min(z[min(n+1,a[s[i]]+a[t[j]])],sl[s[i]]+sr[t[j]]);}int h=0;for(int i=0;i<=n+1;++i) if(z[i]<inf) {while(h&&d[i]*b[h].l+z[i]<=b[h].k*b[h].l+b[h].b) --h;if(!h) b[++h]={d[i],z[i],1,m};else if(d[i]<b[h].k) {b[h].r=min((ll)b[h].r,(z[i]-b[h].b-1)/(b[h].k-d[i]));if(b[h].r<m) b[h+1]={d[i],z[i],b[h].r+1,m},++h;}}for(int i=1;i<=h;++i) for(int j=b[i].l;j<=b[i].r;++j) f[j]=b[i].k*j+b[i].b;for(int i=1;i<=m;++i) cout<<f[i]<<"\n";return 0;
}

O. [AGC072C] Human Exercise (4.5)

Problem Link

简单打表发现路径对称，且对于所有 $i+j\le n$ 的 $(i,j)$，第 $k$ 条经过 $(i,j)$ 的路径向下当且仅当 $k-1\bmod (i+j)<i$。

那么不难递推出前 $m-1$ 条路径经过每个格子的次数，然后就能求出第 $m$ 条路径。

时间复杂度 $\mathcal O(n)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=105;
ll f[MAXN][MAXN];
signed main() {int n;cin>>n>>f[1][1]; --f[1][1];	for(int x=1;x<=n;++x) for(int y=1;x+y<=n;++y) {ll c=f[x][y];f[x+1][y]+=c/(x+y)*x+min(c%(x+y),(ll)x);f[x][y+1]+=c/(x+y)*y+max(c%(x+y)-x,0ll);}string s;for(int i=1,x=1,y=1;i<n;++i) {if(f[x+1][y]<=f[x][y+1]) s+='D',++x;else s+='R',++y;}for(int i=n-2;~i;--i) s+='D'^'R'^s[i];cout<<s<<"\n";return 0;
}

P. [ABC406G] Travelling Salesman Problem (4.5)

Problem Link

设 $f_{i,x}$ 表示匹配 $i$ 个人，当前在 $x$ 的最小代价。

维护 dp 数组需要支持的操作是 $f'_x\gets \min_y f_y+C|x-y|$ 以及 $f_x\gets f_x+D|x-a_i|$。

很显然 $f_x$ 是凸函数，维护斜率变化的位置，第一个操作就是删掉开头结尾的若干个拐点直到斜率 $\in[-C,C]$，第二个操作就是单点修改，容易用 std::map 维护。

构造方案很简单，找到维护 $f_{i-1}\to f_i$ 时最小最大的拐点 $[l_i,r_i]$，那么 $x_{i-1}=\min(r_i,\max(x_i,l_i))$。

时间复杂度：$\mathcal O(n\log n)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
int n,c,d,a[MAXN],l[MAXN],r[MAXN],b[MAXN];
map <int,ll> f;
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>c>>d;for(int i=1;i<=n;++i) cin>>a[i];f[0]+=2*c,f[a[1]]+=2*d;for(int i=2;i<=n;++i) {ll z=d; auto it=f.begin();for(;z>=it->second;++it) z-=it->second;it->second-=z,f.erase(f.begin(),it);z=d,it=--f.end();for(;z>=it->second;--it) z-=it->second;it->second-=z,f.erase(++it,f.end());l[i]=f.begin()->first,r[i]=f.rbegin()->first;f[a[i]]+=2*d;}ll z=c+d; auto it=f.begin();for(;z>=it->second;++it) z-=it->second;b[n]=it->first;for(int i=n;i>1;--i) b[i-1]=max(l[i],min(b[i],r[i]));ll w=0;for(int i=1;i<=n;++i) w=w+1ll*c*abs(b[i-1]-b[i])+1ll*d*abs(a[i]-b[i]);cout<<w<<"\n";for(int i=1;i<=n;++i) cout<<b[i]<<" \n"[i==n];return 0;
}

Q. [ARC198E] Monotone OR (5)

Problem Link

$f_s$ 表示走到 $s$ 的方案数，$g_s=f_{s+1}$，用类似 CDQ 分治的方法转移 $[p,p+2^{k-1})\to [p+2^{k-1},p+2^k)$，每次做 $f$ 和 $a$ 的 OR 卷积。

考虑如何优化 FWT 和 IFWT 的过程，$\mathrm{FWT}(a)$ 预处理，$\mathrm{FWT}(f)$ 可以动态维护，IFWT 只要减掉子集的所有 $g$ 即可。

那么动态维护 $f,g$ 的子集和即可。

时间复杂度 $\mathcal O(n2^n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
void add(int &x,const int &y) { x=(x+y>=MOD)?x+y-MOD:x+y; }
int a[1<<24],f[1<<24],g[1<<24],s[1<<24],t[1<<24];
void cdq(int p,int k) {if(!k) {f[p]=p?g[p-1]:1;g[p]=(1ll*a[p]*(s[p]+f[p])+MOD-t[p])%MOD;s[p]=f[p],t[p]=g[p]; return ;}int d=1<<(k-1);cdq(p,k-1);for(int i=p;i<p+d;++i) add(s[i+d],s[i]),add(t[i+d],t[i]);cdq(p+d,k-1);for(int i=p;i<p+d;++i) add(s[i+d],s[i]),add(t[i+d],t[i]);
}
signed main() {int n,m;cin>>n>>m;for(int i=1,x;i<=m;++i) cin>>x,++a[x];for(int k=1;k<(1<<n);k<<=1) for(int i=0;i<(1<<n);++i) if(i&k) a[i]+=a[i^k];cdq(0,n),cout<<g[(1<<n)-1]<<"\n";return 0;
}

R. [ARC200E] popcount<=2 (3)

Problem Link

首先可以假设 $a_1=0$，只有以下几种情况：

所有数 $\in\{0,2^i\mid i\in[0,m)\}$。
枚举 $i$，所有数 $\in\{0,2^i+2^j\mid i\ne j\}$
枚举 $(i,j)$，所有数 $\in\{0,2^i,2^j,2^i+2^j\}$。
枚举 $(i,j,k)$，所有数 $\in\{0,2^i+2^j,2^j+2^k,2^k+2^i\}$。

简单去重计算。

时间复杂度 $\mathcal O(\log n+\log m)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=998244353;
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
signed main() {int _; cin>>_;for(ll n,m;_--;) {cin>>n>>m,--n;ll s=ksm(m+1,n)+m*(ksm(m+1,n)-ksm(2,n))%MOD-m*(m-1)/2%MOD*(ksm(2,n)-1)%MOD;s+=m*(m-1)/2%MOD*(ksm(4,n)-ksm(3,n)*3+ksm(2,n)*3-1)%MOD;s+=m*(m-1)%MOD*(m-2)%MOD*ksm(6)%MOD*(ksm(4,n)-ksm(3,n)*3+ksm(2,n)*3-1)%MOD;cout<<(s%MOD+MOD)*ksm(2,m)%MOD<<"\n";}return 0;
}

S. [ARC202D] King (4)

Problem Link

首先可以把行列的移动拆开，但是每一步不能原地不动，求出走 $0\sim n$ 步的方案后二项式容斥即可。

然后计算 $+1,-1,0$ 序列用 $[0,n]$ 步 $s\to t$ 的方案数，值域 $[1,m]$，首先可以只考虑 $\pm 1$ 序列，算上 $0$ 只要乘一个组合数，可以 NTT 处理。

如果直接双向反射容斥可以做到 $\mathcal O(\frac {n^2}m)$，暴力 dp 做到 $\mathcal O(nm)$，根号平衡做到 $\mathcal O(n\sqrt n)$。

时间复杂度 $\mathcal O(n\sqrt n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1<<20,MOD=998244353,G=3;
int fac[N],ifac[N];
namespace P {
int rev[N],inv[N],w[N<<1];
int ksm(int a,int b=MOD-2) {int ret=1;for(;b;a=1ll*a*a%MOD,b=b>>1) if(b&1) ret=1ll*ret*a%MOD;return ret;
}
void poly_init() {inv[1]=1;for(int i=2;i<N;++i) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;fac[0]=ifac[0]=1;for(int i=1;i<N;++i) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*inv[i]%MOD;for(int k=1;k<=N;k<<=1) {int x=ksm(G,(MOD-1)/k); w[k]=1;for(int i=1;i<k;++i) w[i+k]=1ll*x*w[i+k-1]%MOD;}
}
int plen(int x) { int y=1; for(;y<x;y<<=1); return y;  }
void ntt(int *f,bool idft,int n) {for(int i=0;i<n;++i) {rev[i]=(rev[i>>1]>>1);if(i&1) rev[i]|=n>>1;}for(int i=0;i<n;++i) if(rev[i]<i) swap(f[i],f[rev[i]]);for(int k=2,x,y;k<=n;k<<=1) {for(int i=0;i<n;i+=k) {for(int j=i;j<i+k/2;++j) {x=f[j],y=1ll*f[j+k/2]*w[k+j-i]%MOD;f[j]=(x+y>=MOD)?x+y-MOD:x+y,f[j+k/2]=(x>=y)?x-y:x+MOD-y;}}}if(idft) {reverse(f+1,f+n);for(int i=0,x=ksm(n);i<n;++i) f[i]=1ll*f[i]*x%MOD;}
}
int poly_mul(const int *f,const int *g,int *h,int n,int m) {static int a[N],b[N];for(int i=0;i<n;++i) a[i]=f[i];for(int i=0;i<m;++i) b[i]=g[i];int len=plen(n+m-1);ntt(a,0,len),ntt(b,0,len);for(int i=0;i<len;++i) h[i]=1ll*a[i]*b[i]%MOD;ntt(h,1,len);memset(a,0,sizeof(int)*len);memset(b,0,sizeof(int)*len);return len;
}
}
int f[N],g[N],dp[2][N];
int C(int x,int y) { return y<0||y>x?0:1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD; }
int qry(int m,int n,int s,int t) {if((n+t-s)&1) return 0;long long z=C(n,(n+t-s)/2);for(int o=1,q=t;;o^=1) {o?q=-q:q=2*m+2-q;if(q<s-n||q>s+n) break;z+=(o?-1:1)*C(n,(n+q-s)/2);}for(int o=1,q=t;s-n<=q&&q<=s+n;o^=1) {o?q=2*m+2-q:q=-q;if(q<s-n||q>s+n) break;z+=(o?-1:1)*C(n,(n+q-s)/2);}return (z%MOD+MOD)%MOD;
}
void sol(int n,int m,int s,int t) {if(m>800) {for(int i=0;i<=n;++i) f[i]=1ll*qry(m,i,s,t)*ifac[i]%MOD;P::poly_mul(f,ifac,f,n+1,n+1);for(int i=0;i<=n;++i) f[i]=1ll*f[i]*fac[i]%MOD;return ;}memset(dp,0,sizeof(dp)),dp[0][s]=1,f[0]=(s==t);for(int i=1;i<=n;++i) {int *l=dp[i&1],*r=dp[(i&1)^1];for(int j=1;j<=m;++j) l[j]=(0ll+r[j]+r[j-1]+r[j+1])%MOD;f[i]=l[t];}
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);P::poly_init();int h,w,n,a,b,c,d;cin>>h>>w>>n>>a>>b>>c>>d;sol(n,w,b,d),swap(f,g),sol(n,h,a,c);int s=0;for(int i=0;i<=n;++i) s=(s+((n-i)&1?-1ll:1ll)*f[i]*g[i]%MOD*C(n,i))%MOD;cout<<(s+MOD)%MOD<<"\n";return 0;
}

T. [ARC204C] Maximize Sum of Mex (4.5)

Problem Link

简单贪心，首先尽可能间隔地安排 $0$，然后再填入 $1,2$，此时每个位置的代价为 $3-x$ 或者 $2(3-x)$，贪心匹配即可。

首先肯定填大小为偶数的环，然后填大小为奇数的环，此时优先放 $\lfloor\frac{\mathrm{siz}}2\rfloor$ 个 $0$ 最优，否则在每个奇数环上多放一个点，注意优先放长度 $\ge 3$ 的环再放长度 $=1$ 的环。

如果填不满大小为偶数的环，背包判断能否完美覆盖若干个环，如果填不满大小为奇数的环，那么从大到小填，二分一下。

时间复杂度 $\mathcal O\left(\dfrac{n^2}\omega+q\log n\right)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5;
int p[MAXN],n,_,c0,c1,c2,q0,q1,s0,su[MAXN];
bool vis[MAXN];
bitset <MAXN> bg,o;
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;++i) cin>>p[i];vector <int> a0,a1;for(int i=1;i<=n;++i) if(!vis[i]) {int c=0;for(int u=i;!vis[u];u=p[u],++c) vis[u]=true;if(c>1) (c&1?a1:a0).push_back(c);else ++q0;}q1=a1.size(),s0=0,bg[0]=1;for(int x:a0) o=bg,o<<=x/2,bg|=o,s0+=x/2;sort(a1.begin(),a1.end());for(int i=0;i<q1;++i) su[i+1]=su[i]+(a1[q1-1-i]-1)/2;for(cin>>_;_--;) {cin>>c0>>c1>>c2;int z=0;if(c0<=(n-q0-q1)/2) {int g2=c0,g1=0,k;if(c0<=s0) {if(!bg[c0]) --g2,g1=2;} else g1=(lower_bound(su,su+q1+1,c0-s0)-su)*2,g2-=g1/2;k=min(c1,g2),z+=4*k,c1-=k,g2-=k;k=min(c1,g1),z+=2*k,c1-=k,g1-=k;k=min(c2,g2),z+=2*k,c2-=k,g2-=k;k=min(c2,g1),z+=k,c2-=k,g1-=k;} else {c0-=(n-q0-q1)/2;int g2=(n-q0-q1)/2,g1=0,x=min(q1,c0),k;z+=x,g1=2*(q1-x),g2-=g1/2,c0-=x;k=min(q0,c0),z+=k,c2+=c0-k;k=min(c1,g2),z+=4*k,c1-=k,g2-=k;k=min(c1,g1),z+=2*k,c1-=k,g1-=k;k=min(c2,g2),z+=2*k,c2-=k,g2-=k;k=min(c2,g1),z+=k,c2-=k,g1-=k;}cout<<z<<"\n";}return 0;
}

U. [ABC381G] Fibonacci Product (6.5)

Problem Link

设 $P=998244353$

首先用比内公式表示类斐波那契数列，然后简单变形成求 $\prod_{i=0}^n(1+pz^i)$。

首先可以发现 $z^{(P-1)/2}=1$，因此只要考虑 $n=\mathcal O(P)$ 的情况。

数列连乘类似快速阶乘算法分块，维护 $f_B(x)=\prod_{i=0}^{B-1}(1+pz^ix)$，那么计算 $f(z^0),f(zB),f(z^{2B}),\dots $ 即可。

首先维护 $f(c^0),f(c^1)\sim ,f(c^m)$ 可以用 BlueStein 算法，即将 $c^{ij}$ 表示成 $c^{\binom {i+j}2-\binom i2-\binom j2}$，然后做一次卷积。

维护 $f_B(x)$ 可以分治注意到 $f_{2k}(x)=f_k(x)f_k(xz^k)$，因此只要一次卷积就能合并。

由于 $\sqrt 5$ 在 $\bmod P$ 意义下不存在，因此扩域一下再处理，容易证明该过程不影响 NTT。

时间复杂度 $\mathcal O(\sqrt P\log\sqrt P)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1<<18,MOD=998244353,G=3,i2=(MOD+1)/2;
int ksm(int a,int b=MOD-2) { int s=1; for(;b;a=1ll*a*a%MOD,b=b>>1) if(b&1) s=1ll*s*a%MOD; return s; }
struct val {int x,y;static constexpr int add(const int &x,const int &y) { return (x+y>=MOD)?x+y-MOD:x+y; }val(int X=0,int Y=0): x(X),y(Y) {}inline friend val operator +(const val &u,const val &v) {return val(add(u.x,v.x),add(u.y,v.y));}inline friend val operator -(const val &u,const val &v) {return val(add(u.x,MOD-v.x),add(u.y,MOD-v.y));}inline friend val operator *(const val &u,const val &v) {return val((1ll*u.x*v.x+5ll*u.y*v.y)%MOD,(1ll*u.x*v.y+1ll*u.y*v.x)%MOD);}inline val inv() const {int z=ksm((1ll*x*x+5ll*(MOD-y)*y)%MOD);return val(1ll*x*z%MOD,1ll*(MOD-y)*z%MOD);}inline friend val operator /(const val &u,const val &v) {return u*v.inv();}
};
namespace P {
int fac[N],ifac[N],rev[N],inv[N],w[N<<1];
void poly_init() {inv[1]=1;for(int i=2;i<N;++i) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;fac[0]=ifac[0]=1;for(int i=1;i<N;++i) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*inv[i]%MOD;for(int k=1;k<=N;k<<=1) {int x=ksm(G,(MOD-1)/k); w[k]=1;for(int i=1;i<k;++i) w[i+k]=1ll*x*w[i+k-1]%MOD;}
}
int plen(int x) { int y=1; for(;y<x;y<<=1); return y;  }
void ntt(val *f,bool idft,int n) {for(int i=0;i<n;++i) {rev[i]=(rev[i>>1]>>1);if(i&1) rev[i]|=n>>1;}for(int i=0;i<n;++i) if(rev[i]<i) swap(f[i],f[rev[i]]);for(int k=2;k<=n;k<<=1) {for(int i=0;i<n;i+=k) {for(int j=i;j<i+k/2;++j) {val x=f[j],y=f[j+k/2]*w[k+j-i];f[j]=x+y,f[j+k/2]=x-y;}}}if(idft) {reverse(f+1,f+n);for(int i=0,x=ksm(n);i<n;++i) f[i]=f[i]*x;}
}
void poly_mul(const val *f,const val *g,val *h,int n,int m) {static val a[N],b[N];for(int i=0;i<n;++i) a[i]=f[i];for(int i=0;i<m;++i) b[i]=g[i];int len=plen(n+m-1);ntt(a,0,len),ntt(b,0,len);for(int i=0;i<len;++i) h[i]=a[i]*b[i];ntt(h,1,len);for(int i=0;i<len;++i) a[i]=b[i]=0;
}
}
val ksm(val a,ll b) { val s=1; for(;b;b>>=1,a=a*a) if(b&1) s=s*a; return s; }
val f[N],a[N],b[N];
void cdq(val p,val z,int n) {if(n==1) return f[0]=1,f[1]=p,void();int m=n/2;cdq(p,z,m);val w=1,o=ksm(z,m);for(int i=0;i<=m;++i) f[i+m+1]=f[i]*w,w=w*o;P::poly_mul(f,f+m+1,f,m+1,m+1);if(n&1) {w=ksm(z,n-1)*p;for(int i=n;i;--i) f[i]=f[i-1]*w+f[i];}
}
val solve(val p,val z,ll n) {if(n>i2) return ksm(solve(p,z,i2-1),n/i2)*solve(p,z,n%i2);if(n<=100) {val s=1,w=p;for(int i=0;i<=n;++i) s=s*(1+w),w=w*z;return s;}memset(f,0,sizeof(f)),memset(a,0,sizeof(a)),memset(b,0,sizeof(b));int B=sqrt(n),m=n/B;cdq(p,z,B);val c=ksm(z,B),ic=c.inv();for(int i=0;i<=B;++i) a[B-i]=f[i]*ksm(ic,i*(i-1)/2);for(int i=0;i<m+B;++i) b[i]=ksm(c,1ll*i*(i-1)/2);P::poly_mul(a,b,a,B+1,m+B);val s=1;for(int i=0;i<m;++i) s=s*a[B+i]*ksm(ic,i*(i-1)/2);val w=p*ksm(z,m*B);for(int i=m*B;i<=n;++i) s=s*(1+w),w=w*z;return s;
}
void solve() {ll n; int A,B;cin>>n>>A>>B,n-=2;if(n<0) return cout<<A<<"\n",void();val x(i2,i2),y(i2,MOD-i2),z=y/x,d=val(0,1).inv()*(A+B*x);val p=(val()-A-B*y)/(A+B*x),s=solve(p,z,n)*ksm(d,n+1)*A;if(n&1) s=s*ksm(ksm(x,n),(n+1)/2);else s=s*ksm(ksm(x,n+1),n/2);cout<<s.x<<"\n";
}
signed main() {P::poly_init();ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}

V. [ARC177E] Wrong Scoreboard (5)

Problem Link

枚举每种分数序列 $\{a_i\}$，然后把得分相同的人按 $r$ 从小到大排序。

注意到我们只关心 $a$ 的每个子集和的相对顺序，以及相邻两个元素和是 $<$ 还是 $=$。

注意到一个序列 $a$ 和另一个序列 $a'$ 相对顺序不变，只是把若干 $<$ 改成了 $=$，则 $a$ 严格优于 $a'$。

可以猜测 $a$ 的值域在较小的时候就能覆盖所有情况，可以证明值域 $[1,10]$ 就能覆盖所有情况，爆搜即可。

最终策略数 $k=113$，桶排计算每个策略的答案。

时间复杂度 $\mathcal O(nk)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+5,m=113,a[m]={16105,16106,16107,16108,16117,16118,16119,16120,16129,16130,16131,16132,16238,16239,16240,16241,16242,16250,16251,16252,16253,16254,16262,16263,16264,16265,16266,16372,16373,16384,16385,16396,16397,16506,16518,16530,17570,17572,17581,17582,17583,17584,17585,17586,17594,17596,17606,17608,17703,17704,17706,17714,17715,17716,17717,17718,17719,17720,17727,17728,17730,17739,17740,17742,17836,17838,17848,17849,17850,17860,17862,17872,17874,17982,17983,18116,19046,19059,19168,19179,19180,19192,19204,19216,19312,19325,19458,20644,32222,32344,32356,32368,32380,32392,33686,33687,33690,33808,33820,33822,33832,33844,33856,33868,33953,34086,35284,35296,36760,49792,49925,49926,66030};
int n,h[MAXN],p[MAXN],id[MAXN],w[m][32],b[m];
inline ll sqr(ll x) { return x*x; }
void solve() {cin>>n;for(int i=1;i<=n;++i) {h[i]=0;for(int j=0,c;j<5;++j) cin>>c,h[i]|=c<<j;}for(int i=1,x;i<=n;++i) cin>>x,p[x]=i;ll s=1e18;for(int k=0;k<m;++k) {fill(b,b+m,0);for(int i=1;i<=n;++i) ++b[w[k][h[i]]];for(int i=m-1;i;--i) b[i-1]+=b[i];ll z=0;for(int i=n;i>=1;--i) z+=sqr(i-(b[w[k][h[p[i]]]]--));s=min(s,z);}cout<<s<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);for(int i=0;i<m;++i) {int z[5],x=a[i];for(int j:{4,3,2,1,0}) z[j]=x%11,x/=11;for(int s=0;s<32;++s) for(int j=0;j<5;++j) if(s>>j&1) w[i][s]+=z[j];}int _; cin>>_;while(_--) solve();return 0;
}

*W. [AGC070B] Odd Namori (8)

Problem Link

首先每个环对应一个连通块，$2$ 的块数次方相当于选出若干个连通块的方案数，即选出一个点集，计数点集内部和外部分别形成基环树森林的方案数。

现在我们要求不能有偶环，那么相当于每选出一个偶环就给方案数乘以 $-1$。

枚举选出的环点集 $S$，计算对应的权值 $f(S)$，其他的每个点 $u$ 方案数都是 $n-1+[u=1]$。

首先假设没有 $fa_i\ne p_i$ 的要求，那么随便交换两个点的出边，则环数 $\pm 1$，由于奇环个数奇偶性不变，因此偶环个数奇偶性变化，从而符号变化，互相抵消，此时 $f(S)=[|S|=1]$。

然后考虑有树边的情况，考虑容斥，选择若干条树边加入，那么形成若干个新的点，同上，如果有 $>1$ 个点必定无解。

所以必须加入 $|S|-1$ 条边，即 $S$ 是树上一条链，注意到 $|S|$ 每增加 $1$，则多钦定一条树边，且环长奇偶性变化，因此 $-1$ 个数总是偶数，贡献必定为 $1$。

维护每个 $[1\in S]=x,|S|=y$ 的 $S$ 数量是平凡的。

时间复杂度 $\mathcal O(n\log n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5,MOD=998244353;
int n,d[MAXN],f[MAXN],g[MAXN],pw[MAXN],s;
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n,d[1]=1,f[1]=1;for(int i=2,x;i<=n;++i) cin>>x,d[i]=d[x]+1,++f[d[i]],++g[d[i]-1];for(int i=n;i>=1;--i) g[i]+=g[i+1];for(int i=pw[0]=1;i<=n;++i) pw[i]=1ll*pw[i-1]*(n-1)%MOD;for(int i=1;i<=n;++i) s=(s+1ll*f[i]*pw[n-i])%MOD;for(int i=1;i<n;++i) s=(s+1ll*g[i]*pw[n-i-1]%MOD*n)%MOD;cout<<(s+1ll*pw[n-1]*n)%MOD<<"\n";return 0;
}

X. [ARC193D] Magnets (6)

Problem Link

观察 $1$ 之间的距离，记两个序列中相邻 $1$ 的距离为 $\{a\},\{b\}$，此处假设字符串开头结尾有额外的 $1$。

每次操作就是选择一个位置 $-2$ 或两个位置 $-1$，形成 $0$ 就删掉，然后给开头结尾分别 $+1$，还可以给开头结尾中的一个 $-1$ 另一个 $+1$。

先考虑除去开头结尾的元素之后如何构造方案，显然贪心尽可能用单点 $-2$ 操作即可，dp 一下 $b$ 是 $a$ 的哪个子序列，$f_{i,j,0/1}$ 表示能否匹配到 $a_i$ 与 $b_j$，且是否给 $a_i$ 减一了。

然后考虑开头结尾的操作，注意到只有给前两个元素或后两个元素 $-1$ 的操作只会让中间元素和 $-1$，其他情况都是元素和 $-2$，枚举上述两种操作数量即可算出 $a_0,b_0$ 的差，容易证明这两种操作分别只有 $\{0,1\}$ 次。

然后优化 dp，注意到对于每个 $f_{i,0/1}$ 只要保留最大的 $j$ 即可做到线性。

时间复杂度 $\mathcal O(n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5,inf=1e9;
int a[MAXN],b[MAXN];
void solve() {int n=0,m=0,q;cin>>q;for(int i=1,j=0;i<=q;++i) {char c; cin>>c;if(c=='1') a[n++]=i-j,j=i;}for(int i=1,j=0;i<=q;++i) {char c; cin>>c;if(c=='1') b[m++]=i-j,j=i;}int s=inf;for(int l:{0,1}) {array <int,2> f={-inf,-inf},g;f[l]=1;for(int i=1;i<n;++i) {g=f;if(a[i]&1) swap(g[0],g[1]);for(int o:{0,1}) if(0<f[o]&&f[o]<m&&a[i]-b[f[o]]>=o) {int c=o^((a[i]-b[f[o]])&1);g[c]=max(g[c],f[o]+1);}f=g;}for(int r:{0,1}) if(f[r]==m) {int w=(accumulate(a+1,a+n,0)-accumulate(b+1,b+m,0)+l+r)/2;s=min(s,w+abs(a[0]+w-l-b[0]));}}cout<<(s==inf?-1:s)<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}

*Y. [ARC180E] LIS and Inversion (7.5)

Problem Link

考虑对每个代价求最大 LIS，先考虑代价为 $0$，那么 $f_{i,j}$ 表示填考虑到第 $i$ 个数，当前 LIS 的结尾相对顺序为第 $j$ 大的元素时的最小代价。

如果 $a_i<j$，那么最优策略就是把当前元素插入 LIS 末尾的后面，$f_{i+1,j}\gets f_{i,j}+1$，否则插什么位置都等价，$f_{i+1,j}\gets f_{i,j}$，容易证明其他策略无效。

那么答案关于每个 $j$ 独立，即 $\max_{x}\sum_{i=x}^n[a_i<x]$，设 $<x$ 的元素有 $f_x$ 个，则答案为 $\max_x f_{x-1}-(x-1)$。

如果代价为 $k$，那么就能让 $k$ 个 $a_i\gets 0$，答案为 $\max_x \min(n-x+1,f_{x-1}-(x-1))$。

容易用前缀和优化维护。

时间复杂度 $\mathcal O(n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2.5e5+5;
int n,a[MAXN],f[MAXN],g[MAXN],z[MAXN];
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1,x;i<=n;++i) cin>>x,++a[x];for(int i=1;i<n;++i) a[i]+=a[i-1]-1;memset(g,-0x3f,sizeof(g));for(int i=0;i<n;++i) {int d=n-i-a[i];if(d<0) { f[0]=max(f[0],n-i); continue; }f[d]=max(f[d],n-i),g[d]=max(g[d],n-i);}for(int i=n;i;--i) g[i-1]=max(g[i-1],g[i]-1);f[0]=max(f[0],g[0]);for(int i=1;i<=n;++i) f[i]=max({f[i],f[i-1],g[i]});memset(z,0x3f,sizeof(z));for(int i=0;i<=n;++i) z[f[i]]=min(z[f[i]],i);for(int i=n;i;--i) z[i]=min(z[i],z[i+1]);for(int i=1;i<=n;++i) cout<<z[i]<<" \n"[i==n];return 0;
}

*Z. [AGC066D] A Independent Set (7.5)

Problem Link

首先最终的串肯定是若干个 $B$ 以及 $(AB)^k$ 拼接形成。

注意到最终串中的每个 $B$ 都不会被 $A$ 跨过，否则在当前位置停止即可。

所以每个 $(AB)^k$ 在原串相应位置上也是 $A,B$ 个数相等的，且策略就是每个 $(AB)^k$ 内部调整。

$f_{i}$ 表示 $[1,i]$ 的最小代价，找到前缀和 $s_j=s_i$ 的 $f_j\to f_i$ 转移。

注意到 $s_k=s_j=s_i$ 则复原 $(k,i]$ 的代价等于复原 $(k,j]$ 的代价加上复原 $(j,i]$ 的代价，所以只要找到最大的 $j$。

而计算复原代价时，注意到所有 $A$ 要么都在匹配位置左边，要么都在匹配位置右边，否则会产生更大的 $s_{j'}=s_i$，那么维护区间和作差即可。

时间复杂度 $\mathcal O(n)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5;
const ll inf=1e18;
int n,a[MAXN],p[MAXN*2];
char s[MAXN];
ll f[MAXN],w[MAXN],s1[MAXN],s2[MAXN];
void solve() {cin>>n;for(int i=1;i<=n;++i) cin>>s[i];for(int i=2;i<=n;++i) cin>>w[i],w[i]+=w[i-1];s[++n]='B',w[n]=w[n-1],a[0]=n;for(int i=1;i<=n;++i) a[i]=a[i-1]+(s[i]=='A'?1:-1);for(int i=0;i<=2*n;++i) p[i]=-1;for(int i=2;i<=n;++i) s1[i]=s1[i-2]+w[i];for(int i=1,j=0;i<=n;++i) if(s[i]=='A') ++j,s2[j]=s2[j-1]+w[i];f[0]=0,p[a[0]]=0;for(int i=1,t=0;i<=n;++i) {f[i]=s[i]=='B'?f[i-1]:inf,t+=(s[i]=='A');if(~p[a[i]]) {int j=p[a[i]];f[i]=min(f[i],f[j]+abs((s1[i-1]-(j?s1[j-1]:0))-(s2[t]-s2[t-(i-j)/2])));}p[a[i]]=i;}cout<<f[n]<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}

AA. [AGC067D] Unique Matching (6)

Problem Link

首先不存在 $(l_i,r_i)=(l_j,r_j)$，否则显然可以交换 $x_i,x_j$，那么我们可以把 $(l_i,r_i)$ 按 $x_i$ 排序，因此可以假设 $x=[1,2,\dots,n]$。

然后刻画匹配唯一的条件，即求最大匹配的增广图上无环，在本题中就是 $i$ 向 $[l_i,r_i]\setminus\{i\}$ 连边后无环。

无环说明该图是 DAG，主旋律容斥，每次加入一层源点，那么其他点对应的区间不能跨过这些源点。

枚举选择的元素 $S$，系数乘上 $(-1)^{|S|-1}$，以及每个源点左右相邻源点的距离，以及删除源点后形成的每个段对应的答案。

那么 $f_n$ 表示答案，$g_n$ 表示 $n\in S$ 的贡献和，转移平凡。

时间复杂度 $\mathcal O(n^2)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5005;
int n,MOD;
ll f[MAXN],g[MAXN];
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>MOD;f[0]=f[1]=g[1]=1;for(int i=2;i<=n;++i) {g[i]=f[i-1]*i%MOD;for(int k=1;k<i;++k) {g[i]=(g[i]+(MOD-g[k])*f[i-k-1]%MOD*(i-k)*(i-k))%MOD;}for(int j=1;j<=i;++j) {f[i]=(f[i]+g[j]*f[i-j]%MOD*(i-j+1))%MOD;}}ll z=f[n];for(int i=1;i<=n;++i) z=z*i%MOD;cout<<z<<"\n";return 0;
}

*AB. [ARC177F] Two Airlines (7.5)

Problem Link

考虑最优解的策略：首先每条边只会被从左往右经过一次，然后有若干个点会从右往左一段，然后在停止位置接过宝藏。

那么 $f_{i,j,k,0/1}$ 表示当前宝藏在 $i$，当前宝藏被 A 或 J 拿着，需要把 $j$ 个 A 和 $k$ 个 J 从 $[i+1,L]$ 送到 $[0,i]$。

如果在某个点上改变颜色，就增加对应的 $j$ 或 $k$，然后再减掉当前点上 A、J 的个数即可转移。

一个想法是 $j,k$ 并不会特别大，假设在当前点上，第 $i$ 个往左的 A 比前一个的代价增加了 $c_1,c_2,\dots ,c_j$，考虑删掉第二个元素，直接让第一个走过去，则代价减少 $c_2+\cdots +c_j$，增加 $c_1$，想要该策略不优则 $c_1>c_2+\cdots +c_j$，则总和翻倍，因此 $j,k$ 都是 $\mathcal O(\log n)$ 级别。

时间复杂度 $\mathcal O(n\log^2n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5,m=17;
void upd(int &x,const int &y) { x=y<x?y:x; }
int n,q,a[MAXN],b[MAXN][2],dp[2][m+5][m+5];
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>q; char c;for(int i=1;i<=n;++i) cin>>c,a[i]=(c=='A');for(int i=1,x;i<=q;++i) cin>>x>>c,++b[x][c=='A'];memset(dp,0x3f,sizeof(dp)),dp[0][1][0]=dp[1][0][1]=0;for(int i=0;i<=n;++i) {for(int j=m;~j;--j) for(int k=m;~k;--k) {if(j) upd(dp[0][j][k],dp[1][j-1][k]);if(k) upd(dp[1][j][k],dp[0][j][k-1]);}for(int j=0;j<=m;++j) for(int k=0;k<=m;++k) for(int o:{0,1}) {upd(dp[o][max(0,j-b[i][0])][max(0,k-b[i][1])],dp[o][j][k]);}if(i<n) for(int j=0;j<=m;++j) for(int k=0;k<=m;++k) {dp[0][j][k]+=(a[i+1]?j+1:k),dp[1][j][k]+=(a[i+1]?j:k+1);}}cout<<min(dp[0][0][0],dp[1][0][0])<<"\n";return 0;
}

AC. [AGC069C] ABA Changing (9.5)

Problem Link

把字符串看成二进制数，A 看成 $0$，B 看成 $1$，那么操作就是选择一个不被 $S$ 包含的二进制位 $i$，让 $S\gets S+3\times 2^i$。

设 $i$ 操作了 $x_i$ 次，那么合法的一个必要条件显然是 $3\sum x_i2^i=T-S$，但我们要保证每次操作时 $s_i=0$，因此 $x_i$ 最多为 $[s_i=0]+\lfloor\frac1{2^i}(S+\sum_{j<i}2^jx_j)\rfloor-\lfloor\frac1{2^i}S\rfloor$，后面的项表示 $i-1\to i$ 的进位次数。

然后考虑如何最小化 $\sum x_i$，首先算出 $\dfrac{T-S}3$，然后从大往小每个点取尽可能大的 $x_i$。

那么限制有两个，一个是 $3\times 2^i\times x_i$ 不能超过当前的 $T-S$，可以从 $\dfrac{T-S}3$ 开始从高到低维护。

另一个限制是 $x_i\le [s_i=0]+\lfloor\frac1{2^i}(S+\sum_{j<i}2^jx_j)\rfloor-\lfloor\frac1{2^i}S\rfloor=[s_i=0]+\lfloor\frac1{2^i}(T-\sum_{j>i}2^jx_j)\rfloor-3x_i-\lfloor\frac1{2^i}S\rfloor$，这个也容易在从高到低确定 $x$ 的过程维护。

时间复杂度 $\mathcal O(n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n,c,z,a[MAXN];
char s[MAXN],t[MAXN];
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;++i) cin>>s[i],a[i]-=(s[i]=='B');for(int i=1;i<=n;++i) cin>>t[i],a[i]+=(t[i]=='B');for(int i=1;i<=n;++i) if(a[i]<0) a[i]+=2,--a[i+1];if(a[n+1]<0) return cout<<"-1\n",0;for(int i=n;i>=1;--i) c=c<<1|a[i],a[i]=c/3,c%=3;if(c) return cout<<"-1\n",0;c=0; //high bit T-S'for(int i=n;i>=1;--i) {c=c*2+(t[i]=='B')-(s[i]=='B');int k=min(a[i],(c+(s[i]=='A'))/4);c-=3*k,a[i-1]+=2*(a[i]-k),z+=k;}cout<<(c?-1:z)<<"\n";return 0;
}

*AD. [ARC180F] Yet Another Expected Value (9.5)

Problem Link

首先可以直接计算生成的序列满足 $x_1<x_2<\cdots <x_n$ 时的期望乘以 $n!$。

连乘相当于每个点选择一个 $j>i$ 或者不选，容易发现 $i\to j$ 构成森林，权值就是每个点父亲的 $A$ 次方之和。

考虑一棵树的答案关于 $x$ 的生成函数，然后合并成森林，那么删掉树根形成新的森林，但是这个森林和树根的权值有关。

那么我们假设 $[x^n]f(x,y)$ 表示有 $\prod_{i=1}^ny^A+\sum_{j>i} x_j^A$ 的期望，则树根的权值为 $[0,y)$ 之间的实数，所以一棵树的生成函数 $g=xy^A\int_0^yf(x,t)\mathrm d t$。

然后考虑从 $g$ 变成 $x$，注意合并两个 $g$ 的时候两棵树的标号是按照 $x$ 升序排列的，所以不用乘组合数排列标号，但是不同的树之间不可区分，所以 $f=\sum_{k\ge 1}\dfrac{g^k}{k!}=\exp g$（此时的 $f,g$ 依然是关于 $x$ 的 OGF 而非 EGF）。

然后打表发现 $[x^0]f=1,[x^1]f=y^{A+1},[x^2]f=\exp(xy^{A+1}+\frac{1}{A+2}x^2y^{2A+2})=(\frac 12+\frac 1{A+2})y^{2A+2}$。

可以猜测 $[x^i]f$ 是 $y^{i(A+1)}$ 倍数，可以使用归纳法证明，记 $z=xy^{A+1},f=\sum_{i\ge 0} f_iz^i$，则 $g=\sum _{i\ge 0}\dfrac{f_iz^{i+1}}{i(A+1)+1}$。

那么顺次暴力递推 $g_i,f_i$ 即可。

时间复杂度 $\mathcal O(n^2)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e4+5,MOD=1e9+7;
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
ll f[MAXN],g[MAXN];
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n,z;cin>>n>>z,f[0]=1;for(int i=1;i<=n;++i) {g[i]=f[i-1]*ksm((i-1)*(z+1)+1)%MOD;for(int j=1;j<=i;++j) f[i]=(f[i]+g[j]*f[i-j]%MOD*j)%MOD;f[i]=f[i]*ksm(i)%MOD;}for(int i=1;i<=n;++i) f[n]=f[n]*i%MOD;cout<<f[n]<<"\n";return 0;
}

*AE. [AGC072D] Magician (9)

Problem Link

01 均衡的字符串可以考虑与括号序列对应。

一个朴素的想法是：字符串 $s$ 填颜色 $i$ 当且仅当循环移位 $i$ 次后得到合法括号序列，然后要求构造 $x$ 时先把字符串循环移位 $x$，然后把前面的元素填 $0$，后面的元素填 $1$。

但是可能有两个不同的 $i,j$，使得某个序列 $s$ 循环移位 $i,j$ 都合法，那么就无法构造。

因此我们的目标变成构造 $1\sim 2n$ 排列 $p_1\sim p_n$，使得任意字符串 $s$ 都有 $s\circ p_1\sim s\circ p_n$ 两两不同，然后用上面的方法解决。如果其中没有合法括号序列，那么任意填一种颜色，容易证明任何时候我们的策略都不会构造出 $s$。

考虑构造 $s\circ p$ 合法且$s\circ q$ 不合法的充分条件：首先选出一个奇数 $k$，则 $s_{p_1}+\cdots +s_{p_k}>0$，如果 $\{q_{2n-k+1},\dots,q_k\}=\{p_1,\dots,p_k\}$，那么 $s_{q_1}+\cdots+s_{q_{2n-k}}<0$ 从而导出 $s\circ q$ 不合法。

如果不限制 $k$ 是奇数，那么直接记 $p_i$ 为 $[i,\dots,2n,1,\dots,i-1]$，对于 $(p_x,p_y)$ 取 $k=|y-x|$ 即可。

但是此时我们没办法满足所有 $|y-x| $ 都是奇数。

一个比较可能实现的目标是让所有 $|y-x|$ 都是偶数，那么我们要让 $k=|y-x|-1$ 合法，只需要把 $p_i$ 的末尾删掉，所以取 $p_i=[2i,\dots,2n,2i-1,1,\dots,2i-2]$ 就满足上述条件。

构造 $c$ 的时候只要比较两个位置在 $p_c$ 中的排名。

时间复杂度 $\mathcal O(\binom{2n}nn^2+Tn)$。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,p[15][25],q[15][25];
signed main() {cin>>n>>m;for(int i=1;i<=n;++i) {for(int j=1;j<=2*n-2*i+1;++j) p[i][j]=2*i+j-1;p[i][2*n-2*i+2]=2*i-1;for(int j=2*n-2*i+3;j<=2*n;++j) p[i][j]=j-(2*n-2*i+2);for(int j=1;j<=2*n;++j) q[i][p[i][j]]=j;}for(int s=0;s<(1<<(2*n));++s) if(__builtin_popcount(s)==n) {char h='A';for(int i=1;i<=n;++i) {for(int j=1,v=0;j<=2*n;++j) {v+=(s>>(2*n-p[i][j])&1)?-1:1;if(v<0) goto fl;}h='A'+i-1; break;fl:;}cout<<h;}cout<<endl;for(;m--;) {char h; cin>>h;for(int i=1,x,y;i<=n;++i) {cin>>x>>y;cout<<(q[h-'A'+1][x]<q[h-'A'+1][y]?y:x)<<endl;}}return 0;
}

*AF. [AGC072E] Flights 2 (9)

Problem Link

首先确定策略，肯定是从前往后尽可能少兑换积分，只要得到的钱数超过了。

因此大部分时候要么没钱要么没积分。

那么二分答案然后 dp，$f_i,g_i$，表示在 $i$，只有钱 / 积分时的最大值。

考虑转移 $u\to v$：

只有积分，原地换成钱。
只有钱，走到 $v$ 后把积分全部换成钱。
只有积分，换最少的积分恰好够走到 $v$。
只有钱，走到一个点 $x$ 换最少的钱恰好够走到 $v$，得到若干积分。

考虑每次移动和兑换的时候钱数加上积分 $\times F$ 严格不升，因此按照 $f_i,F\times g_i$ 排序，每次转移最大的一项即可。

此时复杂度 $\mathcal O(n^3 \log \epsilon)$，考虑优化。

注意到二分的不同值只影响 $f_1$ 的值，那么使用转置原理把转移过程倒过来，$f_i,g_i$ 表示从 $i$ 走到 $n$，只有钱 / 积分时最少需要多少。新的转移式只要对着原转移解不等式即可。

时间复杂度 $\mathcal O(n^3)$。

代码：

#include<bits/stdc++.h>
#define ld long double
using namespace std;
const int MAXN=405,INF=1e9;
const ld inf=1e18;
int n,m,d[MAXN][MAXN],R[MAXN],F;
ld f[MAXN],g[MAXN];
bool vf[MAXN],vg[MAXN];
void solve() {cin>>n>>m>>F;for(int i=1;i<=n;++i) vf[i]=vg[i]=0,f[i]=g[i]=(i<n?inf:0);for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) d[i][j]=(i==j?0:INF);for(int i=1,u,v,w;i<=m;++i) cin>>u>>v>>w,d[u][v]=min(d[u][v],w);for(int i=1;i<=n;++i) cin>>R[i];for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) {d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}while(true) {ld z=inf; int v=0,p=0;for(int i=1;i<=n;++i) {if(!vf[i]&&z>f[i]) z=f[i],v=i,p=0;if(!vg[i]&&z>g[i]*F) z=g[i]*F,v=i,p=1;}if(!v) break;(p?vg[v]:vf[v])=true;if(!p) {if(!vg[v]&&R[v]) g[v]=min(g[v],f[v]/R[v]);for(int u=1;u<=n;++u) if(!vf[u]&&d[u][v]<INF) {f[u]=min(f[u],max((ld)0,f[v]-R[v]*d[u][v])+F*d[u][v]);}} else {for(int u=1;u<=n;++u) if(!vg[u]&&d[u][v]<INF&&R[u]) {g[u]=min(g[u],max((ld)0,g[v]-d[u][v])+(ld)F*d[u][v]/R[u]);}for(int x=1;x<=n;++x) if(d[x][v]<INF) for(int u=1;u<=n;++u) if(!vf[u]&&d[u][x]<INF&&g[v]<=d[u][x]+d[x][v]) {f[u]=min(f[u],max({(ld)0,(ld)d[x][v]*F-d[u][x]*R[x],F*d[x][v]-R[x]*(d[u][x]+d[x][v]-g[v])})+F*d[u][x]);}}}cout<<fixed<<setprecision(20)<<f[1]<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}

查看全文

http://www.wxhsa.cn/company.asp?id=4058