标签：le Noip 记录 int ll 2024 MAXN mathcal MOD

$\text{By DaiRuiChen007}$

Round #17 - 2024.10.8

A. [ARC135D] Square

Problem Link

题目大意

给定 $n\times m$ 矩阵，每次操作可以把 $2\times 2$ 子矩形中的每个元素 $\pm 1$，若干次操作后最小化所有元素的绝对值和，给出构造。

数据范围：$n,m\le 500$。

思路分析

给矩阵黑白间隔染色，并把白格取反，这样不改变答案。

此时所有的操作都不改变每行每列的元素和，因此答案的下界是每行元素和的绝对值之和以及每列元素和的绝对值之和。

不难发现这个下界是可以取到的，下给出构造性证明：

不妨设每行元素的绝对值之和大于每列元素的绝对值之和，那么一组解取到下界当且仅当每个元素的符号和其行和符号相等。
如果有一行一列同为正，那么在交点处填行和与列和的较小值（同为负同理）。
由于行和列和总和相等，因此该过程停止时所有列和一定为 $0$。
此时找到一正一负的两行，任取一列填绝对值较小值。

每次填数至少使得一行或一列和为 $0$，操作次数 $\mathcal O(n+m)$。

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

思路分析

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=505;
int n,m;
ll a[MAXN][MAXN],R[MAXN],C[MAXN],ans=0;
void add(int i,int j,ll x) { a[i][j]+=x,R[i]-=x,C[j]-=x; }
signed main() {
	scanf("%d%d",&n,&m);
	for(int i=1,w;i<=n;++i) for(int j=1;j<=m;++j) {
		scanf("%d",&w),w*=(i+j)&1?-1:1,R[i]+=w,C[j]+=w;
	}
	while(true) {
		int ip=0,in=0,jp=0,jn=0;
		for(int i=1;i<=n;++i) ip=(R[i]>0?i:ip),in=(R[i]<0?i:in);
		for(int j=1;j<=m;++j) jp=(C[j]>0?j:jp),jn=(C[j]<0?j:jn);
		if(ip&&jp) add(ip,jp,min(R[ip],C[jp]));
		else if(in&&jn) add(in,jn,max(R[in],C[jn]));
		else if(ip&&in) {
			ll z=min(R[ip],-R[in]);
			add(ip,1,z),add(in,1,-z);
		} else if(jp&&jn)  {
			ll z=min(C[jp],-C[jn]);
			add(1,jp,z),add(1,jn,-z);
		} else break;
	}
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) ans+=abs(a[i][j]);
	printf("%lld\n",ans);
	for(int i=1;i<=n;++i,puts("")) for(int j=1;j<=m;++j) printf("%lld ",a[i][j]*((i+j)&1?-1:1));
	return 0;
}

B. [ARC173E] Adjacent

Problem Link

题目大意

给定 $a_1\sim a_n$，一次操作可以把所有 $a$ 重排，然后把 $a$ 替换成 $a'_i=a_i\oplus a_{i+1}(1\le i<n)$，最大化 $n-1$ 次操作后序列中剩下的元素。

数据范围：$n\le100,a_i<2^{60}$。

思路分析

考虑最终的元素是可能 $a$ 的哪些子集 $S$ 的异或和。

由于我们可以进行任意重排，因此一个子集是否合法只和 $|S|$ 有关。

由于异或不改变 $|S|$ 奇偶性，且我们至少进行一次操作，因此 $|S|$ 一定是偶数。

考虑如何构造，设 $S=a_1\sim a_{2k}$。

如果 $k$ 是偶数，那么直接用原排列，我们就要在 $n-1$ 个元素中导出 $a'_1,a'_3\sim a'_{2k-1}$ 这 $k$ 个元素的异或和。
如果 $k$ 是奇数，那么构造 $a_1\sim a_{2k-1},a_n,a_{2k},\dots$，我们要在 $n-1$ 个元素中导出 $a'_1,a'_3\sim a'_{2k-1},a'_{2k}$ 这 $k+1$ 个元素的异或和。

容易发现无法构造当且仅当 $k$ 是奇数时 $2k=n$，且 $n>2$。

因此 $4\mid n$ 或 $n=2$ 时，$S$ 可以是所有 $a_1\sim a_n$ 大小为偶数的子集，把所有 $a_1\oplus a_i$ 插入线性基后查询即可。

否则 $S$ 是所有 $a_1\sim a_n$ 大小为偶数且不为全集的子集，枚举一个 $a_i$ 删除，然后做上一部分的过程。

可以预处理 $a_1\oplus a_i$ 的前后缀线性基，这样只要做 $\mathcal O(n)$ 次线性基合并。

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=105;
struct LB {
	ll a[60];
	LB() { memset(a,0,sizeof(a)); }
	void ins(ll x) {
		for(int k=59;~k;--k) if(x>>k&1) {
			if(!a[k]) return a[k]=x,void();
			else x^=a[k];
		}
	}
	ll qry() {
		ll x=0;
		for(int k=59;~k;--k) x=max(x,a[k]^x);
		return x;
	}
	friend LB operator +(LB x,LB y) {
		for(int k=59;~k;--k) if(y.a[k]) x.ins(y.a[k]);
		return x;
	}
}	B,e[MAXN];
ll a[MAXN];
signed main() {
	int n; scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	if(n==2||n%4==0) {
		for(int i=2;i<=n;++i) B.ins(a[1]^a[i]);
		return printf("%lld\n",B.qry()),0;
	}
	for(int i=3;i<=n;++i) B.ins(a[i]^a[2]);
	ll ans=B.qry();
	B=LB();
	for(int i=n;i>=2;--i) e[i]=e[i+1],e[i].ins(a[1]^a[i]);
	for(int i=2;i<=n;++i) {
		ans=max(ans,(B+e[i+1]).qry()),B.ins(a[1]^a[i]);
	}
	printf("%lld\n",ans);
	return 0;
}

C. [ARC118E] Obstacle

Problem Link

题目大意

定义 $n$ 阶排列 $a$ 的权值为从 $(0,0)$ 到 $(n+1,n+1)$ 且不经过任何 $(i,a_i)$ 的路径数。

给定不完整排列 $a$，求每种补全方案中 $a$ 的权值和。

数据范围：$n\le 200$。

思路分析

考虑如何计算单个排列的权值，可以考虑容斥，钦定 $k$ 个 $(i,a_i)$ 必须经过，求对应格路数乘 $(-1)^k$ 求和。

那么对于一般的情况，我们可以 dp 格路，对每条格路在其中选出 $k$ 个障碍并以 $(-1)^k$ 贡献到答案、

即 $f_{i,j,0/1,0/1}$ 表示走到 $(i,j)$ 的格路，第 $i$ 行或第 $j$ 列是否有钦定过障碍的贡献总和。

然后转移时考虑能否在 $(i+1,j)$ 或 $(i,j+1)$ 上放障碍并容斥即可。

但最终的方案数还要记录未确定位置的障碍个数，因此再加一维 $k$ 表示确定了多少个原先未知的 $a_i$。

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

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=205,MOD=998244353;
int n,a[MAXN],cnt,fac[MAXN],f[MAXN][MAXN][MAXN][2][2];
bool vis[MAXN];
inline void add(int &x,const int &y) { x=(x+y>=MOD)?x+y-MOD:x+y; }
inline void sub(int &x,const int &y) { x=(x>=y)?x-y:x+MOD-y; }
signed main() {
	scanf("%d",&n);
	for(int i=fac[0]=1;i<=n;++i) fac[i]=1ll*i*fac[i-1]%MOD;
	for(int i=1;i<=n;++i) {
		scanf("%d",&a[i]);
		if(~a[i]) vis[a[i]]=true;
		else ++cnt;
	}
	f[0][0][0][0][0]=1;
	for(int i=0;i<=n+1;++i) for(int j=0;j<=n+1;++j) for(int k=0;k<=cnt;++k) {
		for(int x:{0,1}) for(int y:{0,1}) {
			const int &w=f[i][j][k][x][y]; if(!w) continue;
			if(i<=n) {
				add(f[i+1][j][k][0][y],w);
				if(!y&&i<n&&1<=j&&j<=n&&(a[i+1]==j||(a[i+1]==-1&&!vis[j]))) {
					sub(f[i+1][j][k+(a[i+1]==-1)][1][1],w);
				}
			}
			if(j<=n) {
				add(f[i][j+1][k][x][0],w);
				if(!x&&j<n&&1<=i&&i<=n&&(a[i]==j+1||(a[i]==-1&&!vis[j+1]))) {
					sub(f[i][j+1][k+(a[i]==-1)][1][1],w);
				}
			}
		}
	}
	int ans=0;
	for(int k=0;k<=cnt;++k) ans=(ans+1ll*fac[cnt-k]*f[n+1][n+1][k][0][0])%MOD;
	printf("%d\n",ans);
	return 0;
}

D. [ARC135E] Multiple

Problem Link

题目大意

给定 $n,x$，求出长度为 $n$ 的严格递增序列 $a$ 满足 $i\mid a_i$ 且 $a_1=x$，最小化 $\sum a_i$。

数据范围：$n,x\le 10^{18}$。

思路分析

很显然我们只需要贪心填最小的 $a_i$，因此有 $a_i=i\times \left(\left\lfloor\dfrac{a_{i-1}}i\right\rfloor+1\right)$。

设 $b_i=\dfrac{a_i}i$，那么 $b_i=\left\lfloor\dfrac{(i-1)b_{i-1}}i\right\rfloor+1$，则 $b_{i+1}-b_{i}=1-\left\lceil\dfrac{b_{i}}{i+1}\right\rceil\le 0$，因此 $b_i$ 严格递减。

最坏情况下 $a_i<x+\sum_{j=2}^i j<x+\dfrac{i(i+1)}2$，因此 $b_i<\dfrac{x}i+\dfrac{i+1}2$。

考虑本质不同的 $b_{i+1}-b_{i}$ 数量的上界，取 $B=\sqrt[3] x$。

那么 $i\le B$ 时只有 $\mathcal O(B)$ 个 $b_{i+1}-b_{i}$。
当 $i>B$ 时 $b_{i+1}-b_i=1-\left\lceil\dfrac{b_{i}}{i+1}\right\rceil>1-\left\lceil\dfrac 12+\dfrac x{i(i+1)}\right\rceil$，因此本质不同的 $b_{i+1}-b_i$ 大约是 $\mathcal O\left(\dfrac{x}{B^2}\right)=\mathcal O(B)$ 级别的。

因此本质不同的 $b_i-b_{i-1}$ 只有 $\mathcal O(\sqrt[3]x)$ 个，对于同一段，我们要求的就是形如 $\sum_{x=l}^r x\times (kx+b)$ 的式子，拆开 $x$ 的一次二次前缀和即可 $\mathcal O(1)$ 计算。

我们只要考虑对每个 $l$ 求出极大的 $r$ 使得 $i\in [l,r]$ 中的 $b_{i}-b_{i-1}$ 相等。

那么 $r$ 就是最大的 $x=\left\lceil\dfrac{b_l+(r-l)(1-x)}{r+1}\right\rceil$ 的 $r$，其中 $x=\left\lceil\dfrac{b_{i}}{i+1}\right\rceil$，用整除分块类似的技巧可以 $\mathcal O(1)$ 计算。

时间复杂度 $\mathcal O(\sqrt[3]x)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=998244353,i2=(MOD+1)/2,i6=(MOD+1)/6;
ll s1(ll x) { return x*(x+1)%MOD*i2%MOD;}
ll s2(ll x) { return x*(x+1)%MOD*(2*x+1)%MOD*i6%MOD; }
ll F(ll l,ll r,ll s,ll d) {
	l%=MOD,r%=MOD,s%=MOD,d%=MOD;
	return (d*(s2(r)-s2(l-1))%MOD+(s-d*l)%MOD*(s1(r)-s1(l-1))%MOD)%MOD;
}
void solve() {
	ll n,s,ans=0;
	scanf("%lld%lld",&n,&s);
	for(ll l=1,r;l<=n;l=r+1) {
		ll d=(s+l)/(l+1);
		r=(d==1)?n:min(n,max(l,(s+(l-1)*(d-1)-1)/(2*d-2)));
		ans=(ans+F(l,r,s,1-d))%MOD;
		s+=(r-l+1)*(1-d);
	}
	printf("%lld\n",(ans+MOD)%MOD);
}
signed main() {
	int T; scanf("%d",&T);
	while(T--) solve();
	return 0;
}

E. [ARC133E] Median

Problem Link

题目大意

给定 $n,m,k,x$，对所有值域 $[1,k]$ 的序列对 $a_n,b_m$ 求 $f(x,a,b)$ 的和。

其中 $f(x,a,b)$ 定义为对于 $i\in[0,nm)$，依次将 $x$ 变成 $a_{i\bmod n+1},b_{i\bmod m+1}$ 的中位数后，最终的 $x$。

数据范围：$n,m,k,x\le 2\times 10^5$。

思路分析

很显然考虑转 $01$ 序列，对于所有 $i\in [0,k]$，将 $>i$ 的看成 $1$，其余看成 $0$ 得到 $x',a'_i,b'_i$。

对每个 $i$，求 $f(x',a',b')$ 只和即可得到答案。

那么我们发现如果 $a'_{i}=b'_i$，那么 $x'$ 经过后一定会变成 $a'_i$，否则保持不变。

如果 $x'$ 被某个 $a'_i$ 覆盖，那么我们把所有原本的 $a,b,i$ 在值域内翻转，此时恰好反转所有 $a',b'$，那么就能得到一个相反的 $f$。

因此所有被覆盖过的 $x'$ 对答案的贡献是对称的。

我们只要对每个 $i$ 算出没被覆盖的 $a',b'$ 有多少个，剩余的所有 $a',b'$ 对答案的贡献就是 $\dfrac{k+1}2$。

一对 $a',b'$ 没覆盖过 $i$，就要求所有 $a'_{i\bmod n+1}\ne b'_{i\bmod m+1}$，设 $d=\gcd (n,m)$，那么所有 $i\equiv j\pmod d$ 的 $a'_i,b'_j$ 都不能相等。

那么对于若干 $\bmod d$ 同余的 $i,j$，所有 $a'_i$ 都一定相等，$b'_j$ 都一定相等，且 $a',b'$ 不同，那么总方案数就是 $(i^{n/d}(k-i)^{m/d}+i^{m/d}(k-i)^{n/d})^d$。

$i\le x$ 时把这个贡献也加进答案里即可。

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=998244353,i2=(MOD+1)/2;
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 n,m,w,x;
signed main() {
	scanf("%lld%lld%lld%lld",&n,&m,&w,&x);
	ll g=__gcd(n,m);
	ll tot=ksm(w,n+m)*(w+1)%MOD,ans=0;
	for(int i=1;i<w;++i) {
		ll t=(ksm(i,n/g)*ksm(w-i,m/g)+ksm(i,m/g)*ksm(w-i,n/g))%MOD;
		t=ksm(t,g);
		if(i<x) ans=(ans+t)%MOD;
		tot=(tot+MOD-t)%MOD;
	}
	printf("%lld\n",(tot*i2+ans)%MOD);
	return 0;
}

*F. [AGC054D] Swap

Problem Link

题目大意

给定长度为 $n$ 的字符串 $S$，包含 (,),x,o 四种字符，交换若干对相邻元素后，把 o 换成 ()，把 x 换成 )(，最小化交换次数使得得到的串是合法括号序列。

数据范围：$n\le 8000$。

思路分析

我们只要求出最终的 $S_i$ 来自哪里，得到一个排列，最小化该排列的逆序对数即可。

考虑 $S$ 中不包含 x,o 的情况，那么对于一个分界点 $(i,i+1)$，如果 $S[1,i]$ 中右括号比左括号多 $x$ 个，我们就要在 $S[i+1,n]$ 中选至少 $x$ 个右括号放到 $S[1,i]$ 中，产生 $x$ 的贡献。

这个下界是可以取到的，按如下方式构造：从左到右依次加入字符，如果右括号多于左括号，就把当前的右括号和后面最近的一个左括号交换。

不难证明如下方式构造出来的排列逆序对数恰好取到下界。

回到原题，我们发现 o 可以放在任何位置，而 x 至少要被一对括号包住。

那么为了使一对 x 合法，交换一对已匹配的括号 (,) 是完全没有意义的。

并且我们只要把 x 放进括号中间，那么通过交换 o,x 把 x 放进去不优于把括号给交换出来。

因此 (,) 和 o,x 内部都不会产生交换，预处理出 (,) 的最优排列，然后维护 dp，设 $f_{i,j}$ 表示当前填了 $i$ 个 (,) 和 $j$ 个 o,x 的最小代价，转移前预处理一些逆序对数即可。

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

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=8005;
char s[MAXN];
int n,m,sz,a[MAXN],b[MAXN],w[MAXN],dp[MAXN][MAXN],fa[MAXN][MAXN],fb[MAXN][MAXN];
inline void chkmin(int &x,const int &y) { x=x<y?x:y; }
signed main() {
	scanf("%s",s+1),sz=strlen(s+1);
	for(int i=1;i<=sz;++i) {
		if(s[i]=='('||s[i]==')') a[++n]=i;
		else b[++m]=i;
	}
	for(int i=1;i<=n;++i) {
		w[i]=w[i-1]+(s[a[i]]=='('?1:-1);
		if(w[i]<0) {
			for(int j=i+1;;++j) if(s[a[j]]=='(') {
				rotate(a+i,a+j,a+j+1); break;
			}
			w[i]+=2;
		}
	}
	memset(dp,0x3f,sizeof(dp)),dp[0][0]=0;
	for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) dp[0][0]+=a[j]<a[i];
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {
		fa[i][j]=fa[i][j-1]+(a[i]<b[j]);
		fb[i][j]=fb[i-1][j]+(b[j]<a[i]);
	}
	for(int i=0;i<=n;++i) for(int j=0;j<=m;++j) {
		if(i<=n) chkmin(dp[i+1][j],dp[i][j]+fa[i+1][j]);
		if(j<=m&&(w[i]||s[b[j+1]]=='o')) chkmin(dp[i][j+1],dp[i][j]+fb[i][j+1]);
	}
	printf("%d\n",dp[n][m]);
	return 0;
}

*G. [AGC055D] Fill

Problem Link

题目大意

定义一个长度为 $3n$ 的字符串 $S$ 是好的，当且仅当其可以划分为 $n$ 个 $\texttt{ABC,BCA,CAB}$ 序列。

给定字符串的一部分，求有多少种补全方式使得该串是好的。

数据范围：$n\le 15$。

思路分析

我们设 $f_{A}(i)$ 表示 $S[1,i]$ 中 $\texttt B$ 的个数减去 $\texttt A$ 的个数，并记 $\max f_{A}(i)=f_A$，同理定义 $f_B,f_C$。

那么我们发现 $S$ 是好的当且仅当 $f_A+f_B+f_C\le n$，下面给出证明：

先证充分性：

我们观察字符串 $S+S$，由于每个 $S$ 中 $\texttt{A,B,C}$ 个数相等，因此 $S\to 2S$ 的 $f_A,f_B,f_C$ 不变。

考虑第 $i$ 个 $\texttt A$ 所在位置 $p_i$，由于 $f_A(p_i-1)\le f_A$，因此 $S[1,p_i-1]$ 中 $\texttt B$ 的个数不超过 $i-1+f_A$。

因此第 $i+f_A$ 个 $\texttt B$ 在第 $i$ 个 $\texttt A$ 右边，同理第 $i+f_A+f_B$ 个 $\texttt C$ 在第 $i+f_A$ 个 $\texttt B$ 右边，第 $i+f_A+f_B+f_C$ 个 $\texttt A$ 在第 $i+f_A+f_B$ 个 $\texttt C$ 右边。

由于 $f_A+f_B+f_C\le n$，那么 $\texttt C$ 的位置在第 $i+n$ 个 $\texttt{A}$ 左边，因此这三个 $\texttt{A,B,C}$ 在 $S+S$ 范围内，且距离 $<|S|$。

因此我们取出这三个 $\texttt{A,B,C}$ 匹配成子序列（$>|S|$ 的减去 $|S|$），由于他们之间的距离 $<|S|$，只会把一段后缀提到前缀上，因此划分出来的一定是 $\texttt{ABC,BCA,CAB}$ 中的一个。

再证必要性：

对于一个合法的 $S$，我们设 $\texttt{ABC,BCA,CAB}$ 数量分别为 $g_A,g_B,g_C$。

注意到一个 $\texttt{ABC,CAB}$ 只会让 $f_{A}(i)$ 区间 $-1$，只有 $\texttt{BCA}$ 会让 $f_A(i)$ 区间 $+1$，因此显然有 $f_A\le g_B$。

同理可知 $f_B\le g_C,f_C\le g_A$，因此 $f_A+f_B+f_C\le g_A+g_B+g_C$。

所以我们 dp 记录 $f_{a,b,c,fa,fb,fc}$ 表示当前 $\texttt{A,B,C}$ 个数，以及当前 $f_A,f_B,f_C$ 即可，转移枚举下一个字符。

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

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int n,f[16][16][16][16][16][16],ans;
char s[55];
inline void add(int &x,const int &y) { x=(x+y>=MOD)?x+y-MOD:x+y; }
signed main() {
	scanf("%d%s",&n,s+1);
	f[0][0][0][0][0][0]=1;
	for(int i=0;i<=n;++i) for(int j=0;j<=n;++j) for(int k=0;k<=n;++k) {
		for(int x=0;x<=n;++x) for(int y=0;x+y<=n;++y) for(int z=0;x+y+z<=n;++z) {
			const int &w=f[i][j][k][x][y][z];
			if(!w) continue;
			int t=i+j+k+1;
			if(t>3*n) { add(ans,w); continue; }
			if((s[t]=='?'||s[t]=='A')&&i<n) add(f[i+1][j][k][x][y][max(z,i-k+1)],w);
			if((s[t]=='?'||s[t]=='B')&&j<n) add(f[i][j+1][k][max(x,j-i+1)][y][z],w);
			if((s[t]=='?'||s[t]=='C')&&k<n) add(f[i][j][k+1][x][max(y,k-j+1)][z],w);
		}
	}
	printf("%d\n",ans);
	return 0;
}

*H. [ARC174F] Nim

Problem Link

题目大意

有一堆石子，两个人轮流从中取石子，共取 $n$ 次，第 $i$ 次要取 $[l_i,r_i]$ 个石子，无法操作的人输，$q$ 次询问如果初始有 $c$ 个石子，谁会获胜。

数据范围：$n,q\le 3\times 10^5$。

思路分析

如果 $n=1$，那么 $[0,l_i)$ 必败，$[l_i,+\infty)$ 平局。

然后考虑加入 $[l_{n-1},r_{n-1}]$，此时对于每个必败区间 $[x,y]$，其会变成 $[x+l_{n-1},y+r_{n-1}]$ 并取并，然后翻转必胜必败情况，最后设 $[0,0]$ 必败。

我们要动态维护这些操作，可以只维护所有差分位置，即 $c=i-1$ 与 $c=i$ 时结果不同的位置。

那么奇数项差分位置就是必败区间的左端点，偶数项差分位置就是必败区间的右端点。

给不同奇偶的差分位置分别加上 $l_{n-1}/r_{n-1}$，如果两个差分位置相交，说明两个必败区间相交，把这两个差分位置都删除。

用堆维护所有奇偶差分位置的距离，每次把会相遇的差分位置弹出并暴力删除即可，双向链表维护所有差分位置即可。

而翻转必胜必败情况只要在最开头加入一个差分位置 $0$。

从 $n$ 到 $1$ 加入所有线段后处理出每段区间的胜负情况，查询时只需要二分。

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int MAXN=3e5+5;
ll l[MAXN],r[MAXN],x[MAXN],tl,tr,ans[MAXN];
int n,q,pr[MAXN],sf[MAXN];
set <pair<ll,int>> ql,qr;
signed main() {
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%lld%lld",&l[i],&r[i]);
	int hd=1,tot=2;
	sf[1]=2,pr[2]=1,x[2]=l[n];
	ql.insert({l[n],1});
	for(int o=n-1;o;--o) {
		tl+=l[o],tr+=r[o];
		while(qr.size()&&qr.begin()->fi<=tr-tl) {
			int i=qr.begin()->second,j=sf[i]; qr.erase(qr.begin());
			if(!sf[j]) { sf[i]=0; continue; }
			if(!pr[i]) hd=sf[j];
			sf[pr[i]]=sf[j],pr[sf[j]]=pr[i];
			if(pr[i]) ql.erase({x[i]-x[pr[i]],pr[i]});
			if(sf[j]) ql.erase({x[sf[j]]-x[j],j});
			if(pr[i]&&sf[j]) ql.insert({x[sf[j]]-x[pr[i]],pr[i]});
		}
		swap(tl,tr),swap(ql,qr);
		++tot,pr[hd]=tot,sf[tot]=hd;
		x[tot]=-tl,ql.insert({x[hd]-x[tot],tot}),hd=tot;
	}
	int m=0;
	for(int i=hd;i;i=sf[i]) ++m,ans[m]=x[i]+(m&1?tl:tr);
	for(int i=1;i<=m;++i) cerr<<ans[i]<<" \n"[i==m];
	scanf("%d",&q);
	for(ll z;q--;) {
		scanf("%lld",&z);
		int i=upper_bound(ans+1,ans+m+1,z)-ans-1;
		puts(i==m?"Draw":(i&1?"Bob":"Alice"));
	}
	return 0;
}

*I. [ARC176F] Cover

Problem Link

题目大意

给定一棵 $nm+1$ 个点的树，由 $n$ 条长度为 $m$ 的链连到一个根节点上构成。

第 $i$ 条链上节点颜色为 $i-1$，根节点颜色为 $0$，每次操作可以把一个点的颜色设成其某个邻居的颜色，求能得到多少种颜色序列。

数据范围：$n,m\le 2\times 10^5$。

思路分析

倒序维护所有操作，一次操作会把一对相邻的同色节点中的一个任意染成其他颜色。

称这种可以任意染色的节点为自由节点，那么如果一次操作使用的是一个自由节点和一个颜色为 $c$ 的节点，实际上相当于交换两个节点的颜色。

因此我们可以把自由节点看成空位，节点的颜色看成一枚该颜色的棋子，那么操作就是把一枚棋子移动到相邻的空位上，或者把两枚相邻同色棋子中的一枚删掉。

我们最终的目的是让每种同色棋子都在一条链上。

手玩发现当空位 $\ge 3$ 时，我们可以把他们聚集在根节点附近，并且无论如何都能找到一步进行操作。

我们只需要考虑空位 $\le 2$ 的情况，反面考虑减去这种终态数量。

空位 $=0$，只要所有点和父亲不同色即可，方案数 $n(n-1)^{nm}$。
空位 $=1$，设空位在根节点上，那么要求每个儿子不同色。

先给每个儿子填色，再枚举一对点颜色相同，剩余的和父亲不同色即可，方案数 $n!\times nm\times(n-1)^{(m-1)n}$。
空位 $=2$，设空位在根节点和其儿子上，那么剩余的 $n-1$ 个儿子必须不同色，且所有深度 $=2$ 的点都是剩下的那种颜色。

如果初始就能生成两个空位，枚举产生位置，类似得到方案数 $n!\times\binom{nm}2\times (n-1)^{(m-2)n}$。

否则相当于把第一个空位移动到根节点后，有两个儿子颜色相同，方案数 $n!\times nm\times\binom{n-1}2\times (n-1)^{(m-2)n}$

特判 $n\le 2,m\le 1$ 的情况。

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=998244353;
ll ksm(ll a,ll b) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
ll C(ll x) { return x*(x-1)/2%MOD; }
signed main() {
	ll n,m,fac=1;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i) fac=fac*i%MOD;
	if(n==1) return puts("1"),0;
	if(n==2) return printf("%lld\n",n*m+2),0;
	if(m==1) {
		ll ans=ksm(n,n+1);
		ans-=n*ksm(n-1,n)%MOD;
		ans-=n*(fac-1)%MOD;
		printf("%lld\n",(ans%MOD+MOD)%MOD);
		return 0;
	}
	ll ans=ksm(n,n*m+1);
	ans-=n*ksm(n-1,n*m)%MOD;
	ans-=n*m%MOD*fac%MOD*ksm(n-1,n*(m-1))%MOD;
	ans-=C(n*m%MOD)*fac%MOD*ksm(n-1,n*(m-2))%MOD;
	ans-=n*m%MOD*C(n-1)%MOD*fac%MOD*ksm(n-1,n*(m-2))%MOD;
	printf("%lld\n",(ans%MOD+MOD)%MOD);
	return 0;
}

Round #18 - 2024.10.10

A. [ARC126E] Exchange

Problem Link

题目大意

给定长度为 $n$ 的序列 $a$，定义一次操作为 $a_i\gets a_i-x,a_j\gets a_j+x$，产生 $x$ 的收益，需要保证 $a_i-2x\ge a_j$。

支持 $q$ 次单点修改，动态维护最大收益。

数据范围：$n,q\le 3\times 10^5$。

思路分析

猜测答案为 $\dfrac 12\sum_{i<j}|a_i-a_j|$，这是可以证明的：

每次操作 $(i,j)$ 的贡献都会减小 $x$，而 $a_k>a_{i}+x$ 就会让 $(i,k)$ 贡献 $-x$，可以抵消 $(j,k)$ 贡献增量，同理 $a_k<a_j-x$ 的贡献会抵消。

因此一次代价为 $x$ 的操作至少会让上式 $-x$。

构造方案是容易的，每次取出排序后相邻的两个元素操作即可。

维护 $\sum |a_i-a_j|$ 直接主席树维护值域区间元素数量和元素和，合并左右区间时计算跨越区间的 $(i,j)$ 对贡献。

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+5,MOD=998244353,V=1e9,i2=(MOD+1)/2;
struct Segt {
	int tot,ls[MAXN*60],rs[MAXN*60],siz[MAXN*60];
	ll sum[MAXN*60],val[MAXN*60];
	void psu(int p) {
		siz[p]=siz[ls[p]]+siz[rs[p]];
		sum[p]=(sum[ls[p]]+sum[rs[p]])%MOD;
		val[p]=(val[ls[p]]+val[rs[p]]+sum[rs[p]]*siz[ls[p]]-sum[ls[p]]*siz[rs[p]])%MOD;
	}
	void ins(int x,int op,int l,int r,int &p) {
		if(!p) p=++tot;
		if(l==r) return siz[p]+=op,sum[p]=(sum[p]+op*x)%MOD,void();
		int mid=(l+r)>>1;
		x<=mid?ins(x,op,l,mid,ls[p]):ins(x,op,mid+1,r,rs[p]);
		psu(p);
	}
}	T;
int n,q,a[MAXN],rt;
signed main() {
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]),T.ins(a[i],1,1,V,rt);
	for(int x,y;q--;) {
		scanf("%d%d",&x,&y);
		T.ins(a[x],-1,1,V,rt);
		T.ins(a[x]=y,1,1,V,rt);
		printf("%lld\n",(T.val[rt]+MOD)*i2%MOD);
	}
	return 0;
}

B. [ARC128E] Different

Problem Link

题目大意

给出 $m$ 个值域 $[1,n]$ 的元素，其中有 $a_i$ 个 $i$，求一组字典序最小的排列使得每个长度为 $k$ 的子区间中都没有相同元素。

数据范围：$n\le 500,m\le 2.5\times 10^5$。

思路分析

容易发现同一种颜色的元素最多填 $\left\lceil\dfrac nk\right\rceil$ 个，并且这样的元素至多 $n\bmod k$ 个。

可以递归证明这个条件是充分的。

构造方案时从小到大找到第一个可以填并且上一次填入位置距离当前位置 $\ge k$ 的元素即可。

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

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=505,MAXL=2e5+5;
int n,m,k,a[MAXN],mx,cnt[MAXL],pre[MAXN];
void del(int x) {
	--cnt[a[x]];
	if(!cnt[mx]) --mx;
	++cnt[--a[x]];
}
void add(int x) {
	--cnt[a[x]];
	++cnt[++a[x]];
	if(cnt[mx+1]) ++mx;
}
bool judge() {
	if(!n) return true;
	if(n%k) return mx<n/k+1||(mx==n/k+1&&cnt[mx]<=n%k);
	return mx<n/k||(mx==n/k&&cnt[mx]<=k);
}
signed main() {
	scanf("%d%d",&m,&k);
	for(int i=1;i<=m;++i) {
		scanf("%d",&a[i]),n+=a[i];
		mx=max(mx,a[i]),++cnt[a[i]];
	}
	while(n--) {
		for(int i=1;i<=m;++i) if(a[i]&&(!pre[i]||pre[i]>=n+k)) {
			del(i);
			if(judge()) { printf("%d ",i),pre[i]=n; goto fd; }
			add(i);
		}
		return puts("-1"),0;
		fd:;
	}
	return 0;
}

C. [ARC132F] Strategy

Problem Link

题目大意

给定三个人玩石头剪刀布，进行 $k$ 轮，已知前两个人会选择的策略集合。

对于第三个人的每种策略，求出前两个人有多少种选择策略的方法使得第三个人至少获胜一轮。

数据范围：$k\le 12$。

思路分析

考虑枚举第 $i$ 轮并钦定第三个人在这一轮获胜。

我们就要计算有多少第一个人和第二个人的策略对，使得他们在第 $i$ 位相等。

回到原问题，进行容斥，钦定第三个人获胜了其中 $x$ 轮，容斥系数 $(-1)^{x-1}$。

我们就要对于 $3^x$ 个可能的决策 $s$，求第一个人和第二个人在这 $x$ 位恰好是 $s$ 的数量，可以四进制 FWT，某一位 $=3$ 说明不钦定这一位取值。

然后做一个类似的过程，把每一位 $=3$ 的值加给这一位 $=0/1/2$ 的值。

注意输出的时候要轮换一下（第三个人要出石头才能赢另外两个人出剪刀）。

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,N,Z,X,Y;
ll f[1<<24],g[1<<24];
int read() {
	string o; cin>>o;
	int s=0;
	for(int i=0;i<n;++i) s=s<<2|(o[i]=='P'?0:(o[i]=='R'?1:2));
	return s;
}
void out(int i,int s) {
	if(i==n) return cout<<f[s]<<"\n",void();
	out(i+1,s<<2|1);
	out(i+1,s<<2|2);
	out(i+1,s<<2);
}
signed main() {
	ios::sync_with_stdio(false);
	cin>>n>>X>>Y,N=1<<(n*2);
	for(int i=0;i<n;++i) Z=Z<<2|1;
	for(int i=0;i<X;++i) ++f[read()];
	for(int i=0;i<Y;++i) ++g[read()];
	for(int k=1;k<N;k<<=2) for(int i=0;i<N;i+=k<<2) for(int j=i;j<i+k;++j) {
		f[j+3*k]+=f[j]+f[j+k]+f[j+2*k];
		g[j+3*k]+=g[j]+g[j+k]+g[j+2*k];
	}
	for(int s=0;s<N;++s) {
		f[s]*=g[s];
		if((n&1)^__builtin_parity(s&(s>>1)&Z)^1) f[s]*=-1;
	}
	f[N-1]=0;
	for(int k=1;k<N;k<<=2) for(int i=0;i<N;i+=k<<2) for(int j=i;j<i+k;++j) {
		f[j]+=f[j+3*k],f[j+k]+=f[j+3*k],f[j+2*k]+=f[j+3*k];
	}
	out(0,0);
	return 0;
}

D. [ARC130E] Minimum

Problem Link

题目大意

给定序列 $b_1\sim b_m$，构造一个长度为 $n$ 的序列 $a_1\sim a_n$，使得第 $i$ 次操作前 $a_{b_i}=\min a_{1\sim n}$，操作后给 $a_{b_i}$ 加一，求字典序最小解。

数据范围：$n,m\le 3\times 10^5$。

思路分析

观察 $b$ 的操作过程，把 $a_{b_i}$ 相同的若干操作划分成一段，那么每次操作会让所有最小值 $+1$。

对于同一段的操作，不可能有 $b_i$ 相等，并且上一段的 $b_i$ 会被下一段的 $b_i$ 包含。

不难发现满足这两个条件的划分方式一定是合法的，并且我们只要最小化划分轮数即可求出字典序最小解。

设 $f_i$ 表示 $b[1,i]$ 的最小划分轮数，容易发现左端点 $l$ 有一个下界，并且要求 $b[1,l)$ 的数被 $b[l,i]$ 包含，显然 $l$ 越小越好，因此可以直接贪心。

注意最后一轮可以不划分满，即在倒数第二轮所有可能的终止点 $i$ 中取 $f_i$ 最小的一个，重复时取 $i$ 最大的一个。

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

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5;
int n,m,a[MAXN],pre[MAXN],dp[MAXN],ans[MAXN];
signed main() {
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	int lst=0,cnt=0;
	for(int i=1;i<=n;++i) {
		lst=max(lst,pre[a[i]]),cnt+=!pre[a[i]],pre[a[i]]=i;
		if(i-lst==cnt&&~dp[lst]) dp[i]=dp[lst]+1;
		else dp[i]=-1;
	}
	int o=-1;
	for(int i=n;i>=lst;--i) if(~dp[i]&&(o==-1||dp[i]<dp[o])) o=i;
	if(o==-1) return puts("-1"),0;
	for(int i=1;i<=m;++i) ans[i]=dp[o]+1;
	for(int i=1;i<=o;++i) --ans[a[i]];
	for(int i=1;i<=m;++i) printf("%d ",ans[i]); puts("");
	return 0;
}

E. [ARC129E] Cost

Problem Link

题目大意

给定 $n$ 个变量 $x_i$，每个变量有 $m$ 种取值，每种取值有代价，并且会产生 $\sum w_{i,j}|x_i-x_j|$ 的额外代价，最小化总代价。

数据范围：$n\le 50,m\le 5$。

思路分析

先考虑所有变量取值范围都相等怎么做，设取值范围为 $v_1\sim v_m$，可以拆每对 $(v_k,v_{k+1})$ 的贡献。

即 $x_i\le v_k,x_{j}>v_k$ 的时候产生 $w_{i,j}\times (v_{k+1}-v_k)$ 的代价，用切糕模型刻画之。

但是原问题中每个点就会有 $nm$ 个取值，取不到的点设为 $+\infty$ 代价，建图网络流难以接受。

注意到每个点网络流图上的链只会有 $\mathcal O(m)$ 条非平凡边，剩余的全是 $+\infty $ 链，把这些链缩成一条边即可。

时间复杂度 $\mathcal O(\mathrm{Flow}(nm,n^2m))$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace F {
const int MAXV=365,MAXE=1e5+5;
const ll inf=1e18;
struct Edge {
	int v,lst; ll f;
}	G[MAXE];
int S,T,tot=1,hd[MAXV],cur[MAXV],dep[MAXV];
void init() { tot=1,memset(hd,0,sizeof(hd)); }
void adde(int u,int v,ll w) { G[++tot]={v,hd[u],w},hd[u]=tot; }
void link(int u,int v,ll w) { adde(u,v,w),adde(v,u,0); }
bool BFS() {
	memcpy(cur,hd,sizeof(cur)),memset(dep,-1,sizeof(dep));
	queue <int> Q;
	Q.push(S),dep[S]=0;
	while(!Q.empty()) {
		int u=Q.front(); Q.pop();
		for(int i=hd[u];i;i=G[i].lst) if(G[i].f&&dep[G[i].v]==-1) {
			dep[G[i].v]=dep[u]+1,Q.push(G[i].v);
		}
	}
	return ~dep[T];
}
ll dfs(int u,ll f) {
	if(u==T) return f;
	ll r=f;
	for(int i=cur[u];i;i=G[i].lst) {
		int v=G[cur[u]=i].v;
		if(G[i].f&&dep[v]==dep[u]+1) {
			ll g=dfs(v,min(r,G[i].f));
			if(!g) dep[v]=-1;
			G[i].f-=g,G[i^1].f+=g,r-=g;
		}
		if(!r) return f;
	}
	return f-r;
}
ll Dinic() {
	ll f=0;
	while(BFS()) f+=dfs(S,inf);
	return f;
}
}
using F::link;
const ll inf=1e18;
int n,m,q=0,k,a[55][10],id[55][10];
ll c[55][10],w[55][55],v[15];
signed main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d%lld",&a[i][j],&c[i][j]);
	for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) scanf("%lld",&w[i][j]);
	int s=F::S=++q,t=F::T=++q;
	for(int i=1;i<=n;++i) {
		for(int j=0;j<=m;++j) id[i][j]=++q;
		for(int j=1;j<=m;++j) link(id[i][j-1],id[i][j],c[i][j]);
		link(s,id[i][0],inf);
		link(id[i][m],t,inf);
	}
	for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) {
		k=0;
		for(int o=1;o<=m;++o) v[++k]=a[i][o],v[++k]=a[j][o];
		sort(v+1,v+k+1),k=unique(v+1,v+k+1)-v-1;
		for(int o=1;o<k;++o) {
			ll z=w[i][j]*(v[o+1]-v[o]);
			int x=upper_bound(a[i]+1,a[i]+m+1,v[o])-a[i]-1;
			int y=upper_bound(a[j]+1,a[j]+m+1,v[o])-a[j]-1;
			link(id[j][y],id[i][x],z);
			link(id[i][x],id[j][y],z);
		}
	}
	printf("%lld\n",F::Dinic());
	return 0;
}

*F. [ARC129F] Catch

Problem Link

题目大意

给定 $n$ 个负半轴上的动点和 $m$ 个正半轴的动点，初始位置为 $l_1\sim l_n,r_1\sim r_m$，每个点以 $1$ 的速度远离原点。

一个人从原点次以 $2$ 的速度抓捕最近的正半轴或负半轴上的点，对于每种抓捕顺序求出花费时间之和。

数据范围：$n,m\le 2.5\times 10^5$。

思路分析

事实上我们只关心所有抓捕后转向的点 $a_1\sim a_k$（包含最后一个抓到的点）。

那么设抓到 $a_i$ 的时刻是 $t_i$，由于 $a_{i+1}$ 一定和 $a_i$ 不同方向，因此当前两点距离为 $|a_i|+|a_{i+1}|+2t_i$，因此 $t_{i+1}=t_i+|a_i|+|a_{i+1}|+2t_i$。

化简得到 $t_k=|a_k|+\sum_{i<k}(3^{k-i-1}+3^{k-i})|a_i|$。

我们只考虑 $a$ 为 $l_i$ 的情况，剩余情况是对称的。

枚举 $k$，并枚举 $l_{1}\sim l_{i-1},l_{i+1}\sim l_n$ 选了几个进入 $a$，以及 $r_1\sim r_{m-1}$ 选了几个进入 $a$。

因为 $l_n,r_{m}$ 一定是 $a_k,a_{k-1}$ 之一，因此特殊讨论，$l_1\sim l_{n-1}$ 的答案为：

\[\dfrac 43\sum_{i=1}^{n-1}l_i\sum_{k=1}^n\left(\binom{m-1}{k-2}+4\binom{m-1}{k-1}+3\binom{m-1}k\right)\sum_{j=1}^{n-1}9^j\binom{n-i-1}{j-1}\binom{i-1}{k-j-1} \]

$l_n$ 的贡献为：

\[l_n\sum_{k=1}^{n-1}\binom{m-1}{k-2}+5\binom{m-1}{k-1}+4\binom{m-1}k \]

下面的式子容易算，我们只要快速计算上式，考虑单个 $\binom{m-1}{k-s}$ 的贡献，其中 $s\in\{0,1,2\}$，交换求和顺序后把 $k$ 的枚举用范德蒙德卷积替换得到：

\[\sum_{k=1}^n\binom{m-1}{k-s}\sum_{j=1}^{n-1}9^j\binom{n-i-1}{j-1}\binom{i-1}{k-j-1}=\sum_{j=1}^{n-1}9^j\binom{n-i-1}{j-1}\binom{m+i-2}{m-j+s-2} \]

不难用 NTT 优化计算。

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

代码呈现

#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;
	}
}
}
using P::ntt;
int C(int x,int y) {
	if(x<0||y<0||y>x) return 0;
	return 1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;
}
int n,m,w[N],a[N],b[N],pw[N];
const int cof[3]={3,4,1},i3=(MOD+1)/3; //cof of C(m-1,x-k)
int solve() {
	int ans=0;
	memset(a,0,sizeof(a));
	for(int i=1;i<n;++i) a[i]=1ll*w[i]*fac[m+i-2]%MOD*fac[n-i-1]%MOD;
	ntt(a,0,N);
	for(int k:{0,1,2}) {
		memset(b,0,sizeof(b));
		for(int j=1;j<n&&m-j+k-2>=0;++j) b[j]=1ll*pw[j]*ifac[j-1]%MOD*ifac[m-j+k-2]%MOD;
		ntt(b,0,N);
		for(int i=0;i<N;++i) b[i]=1ll*a[i]*b[i]%MOD;
		ntt(b,1,N);
		for(int s=k;s<=n;++s) ans=(ans+1ll*cof[k]*b[s]*ifac[n-s]%MOD*ifac[s-k])%MOD;
	}
	ans=4ll*ans*i3%MOD;
	for(int i=1;i<=n;++i) ans=(ans+(5ll*C(m-1,i-1)+4ll*C(m-1,i)+C(m-1,i-2))%MOD*w[n]%MOD*C(n-1,i-1))%MOD;
	return ans;
}
signed main() {
	P::poly_init();
	for(int i=pw[0]=1;i<N;++i) pw[i]=9ll*pw[i-1]%MOD;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&w[i]);
	int ans=solve();
	for(int i=1;i<=m;++i) scanf("%d",&w[i]);
	swap(n,m);
	printf("%d\n",(ans+solve())%MOD);
	return 0;
}

*G. [ARC131F] Pattern

Problem Link

题目大意

给定长度为 $n$ 的字符串 $S$，字符集 $\texttt {A,R,C}$，进行 $\le k$ 次操作得到 $T$：每次把一个长度为 $3$ 的子串替换成 $\texttt{ARC}$。

已知 $T$，求有多少个可能的 $S$。

数据范围：$n\le 5000,k\le 10^4$，

思路分析

时光倒流，一次操作会把 $T$ 中的 $\texttt{ARC}$ 子串变成三个任意字符，设为 $\texttt{???}$。

那么每次操作会把 $\texttt{ARC,AR?,A??,?RC,??C,?R?}$ 中的一个变成 $\texttt{???}$，这个过程中显然不可能产生 $\texttt{A?C}$。

考虑 $k=\infty$ 时怎么做，按 $\texttt{ARC,AR?,A??,?RC,??C,?R?}$ 的顺序把 $T$ 中若干元素变成 $\texttt{?}$，显然只有 $\texttt ?$ 上的元素能修改。

回到原问题，此时我们把 $T$ 分成若干 $\texttt{ARC,AR,A,RC,C,R,X}$ 子串（$\texttt X$ 表示未匹配字符），每个子串可以变成 $\texttt ?$ 但有些子串会依赖其前驱、后继。

考虑 dp，设 $f_{i,j,0/1}$ 表示决策了前 $i$ 个子串，最小操作次数为 $j$，是否钦定第 $i,i+1$ 个子串必须是 $\texttt ?$。

一个子串可以不变成 $\texttt ?$，不产生贡献，如果选择了变成 $\texttt ?$，就有 $3^{|o|}$ 贡献（其中 $o$ 是当前子串），有依赖关系的子串就会改变 $0/1$ 符号位。

但如果 $o$ 的前驱后继都不依赖 $o$，那么实际上没必要操作 $o$，因此我们钦定 $S$ 中的这个位置不等于 $o$，贡献变为 $3^{|o|}-1$。

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e4+5,MOD=998244353,pw[]={1,3,9,27};
int n,m; string s;
ll f[MAXN][2];
struct info {
	int l,r;
	vector <string> q;
};
signed main() {
	ios::sync_with_stdio(false);
	cin>>s>>m,n=s.size();
	vector <info> Q;
	for(int i=0;i<n;++i) if(s.substr(i,3)=="ARC") {
		info o{i,i+3};
		while(true) {
			if(o.l>=1&&s.substr(o.l-1,1)=="A") o.q.push_back("A"),--o.l;
			else if(o.l>=2&&s.substr(o.l-2,2)=="AR") o.q.push_back("AR"),o.l-=2;
			else break;
		}
		reverse(o.q.begin(),o.q.end());
		o.q.push_back("ARC");
		while(true) {
			if(o.r<=n-1&&s.substr(o.r,1)=="C") o.q.push_back("C"),++o.r;
			else if(o.r<=n-2&&s.substr(o.r,2)=="RC") o.q.push_back("RC"),o.r+=2;
			else break;
		}
		Q.push_back(o);
	}
	vector <string> A;
	for(int i=0;i<(int)Q.size();++i) {
		if(i>=1) {
			A.push_back({Q[i-1].r+1==Q[i].l&&s[Q[i-1].r]=='R'?"R":" "});
		}
		A.insert(A.end(),Q[i].q.begin(),Q[i].q.end());
	}
	f[0][0]=1;
	for(auto o:A) {
		int w=pw[o.size()];
		for(int i=m-1;~i;--i) {
			if(o=="ARC") for(int x:{0,1}) for(int y:{0,1}) f[i+1][y]+=f[i][x]*(x||y?w:w-1);
			else if(o=="AR"||o=="A") for(int x:{0,1}) f[i+1][1]+=f[i][x]*(x?w:w-1);
			else if(o=="RC"||o=="C") for(int y:{0,1}) f[i+1][y]+=f[i][1]*(y?w:w-1);
			else if(o=="R") f[i+1][1]+=2*f[i][1];
			f[i][1]=0;
		}
		for(int i=0;i<=m;++i) for(int x:{0,1}) f[i][x]%=MOD;
	}
	ll ans=0;
	for(int i=0;i<=m;++i) ans=(ans+f[i][0])%MOD;
	cout<<ans<<"\n";
	return 0;
}

*H. [ARC118F] Ratio

Problem Link

题目大意

给定 $a_1\sim a_n$，求有多少值域 $[1,m]$ 的序列 $x_1\sim x_{n+1}$ 满足 $x_{i+1}\ge a_i\times x_i$。

数据范围：$n\le 1000,m\le 10^{18}$。

思路分析

正序 dp 较难维护，考虑倒序 dp，设 $f_{i,j}$ 表示决策 $x[i,n+1]$ 后 $x_i=j$ 的方案数。

转移时 $f_{i,j}=\sum_{k\ge a_i\times j} f_{i+1,k}$，设 $g_{i,j}$ 表示 $f_{i,j}$ 的前缀和，那么有 $f_{i,j}=g_{i+1,m}-g_{i+1,a_i\times j-1}$。

初始 $f_{n+1,i}=1,g_{n+1,i}=i$，猜测 $f_{i,j}$ 是某个低次多项式在 $j$ 处的点值。

发现 $f_i$ 和 $g_{i+1}$ 次数相同，都是 $n-i+1$ 次多项式的点值。

因此可以拉格朗日插值，每次维护 $g_{i,1\sim n}$，转移时直接插值求 $g$。

我们可以 $\mathcal O(n)$ 线性插值，但是此时要求 $\mathcal O(n^2)$ 次 $g$，难以接受。

由于 $\prod a_i\le m$，因此 $a_i$ 中非 $1$ 项只有 $\mathcal O(\log m)$ 个，对于 $a_i=1$ 的问题，我们求的是 $g_{i+1,j-1}$，可以 $\mathcal O(1)$ 回答，只要插值求 $g_{i+1,m}$ 即可。

因此插值次数是 $\mathcal O(n\log m)$ 的。

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1005,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; }
int n,T;
ll m,a[MAXN],f[MAXN],inv[MAXN],g[MAXN],pl[MAXN],pr[MAXN];
ll larg(ll x) {
	if(x<=T) return f[x];
	pl[0]=pr[T+1]=1;
	for(int i=1;i<=T;++i) pl[i]=(x-i)%MOD*pl[i-1]%MOD;
	for(int i=T;i>=1;--i) pr[i]=(x-i)%MOD*pr[i+1]%MOD;
	ll ans=0;
	for(int i=1;i<=T;++i) ans=(ans+f[i]*pl[i-1]%MOD*pr[i+1]%MOD*inv[i])%MOD;
	return ans;
}
signed main() {
	scanf("%d%lld",&n,&m),T=n+2;
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	for(int i=1;i<=T;++i) {
		inv[i]=1;
		for(int j=1;j<=T;++j) if(i!=j) inv[i]=inv[i]*(i+MOD-j)%MOD;
		inv[i]=ksm(inv[i]);
	}
	for(int i=1;i<=T&&i<=m;++i) f[i]=i;
	for(int i=n;i>=1;--i) {
		ll S=larg(m); m/=a[i];
		memset(g,0,sizeof(g));
		for(int j=1;j<=T&&j<=m;++j) g[j]=(S+MOD-larg(j*a[i]-1))%MOD;
		for(int j=1;j<=T&&j<=m;++j) g[j]=(g[j-1]+g[j])%MOD;
		memcpy(f,g,sizeof(f));
	}
	printf("%lld\n",larg(m));
	return 0;
}

*I. [ARC119F] Distance

Problem Link

题目大意

给定节点 $0\sim n$，用一条 $i,i+1$ 的链连接。

$1\sim n-1$ 有黑白两种颜色，每个点会向其同色前驱后继连双向边（不存在设为 $0/n$）。

已知一些点的颜色，求有多少种染色方法使得 $0,n$ 之间最短路长度 $\le m$。

数据范围：$n,m\le 4000$。

思路分析

设 $f_{i,j,k,0/1}$ 表示前 $i$ 个点，到最后一个白色，黑色点的最短距离为 $j,k$，第 $i$ 个点的颜色为白或黑的方案数。

设当前颜色为白，那么再加入一个白点会令 $j\gets j+1$，加入一个黑点会令 $j\gets \min(k+2,j),k\gets \min(j+1,k+1)$。

暴力转移复杂度 $\mathcal O(nm^2)$，考虑优化状态数。

依然设当前颜色为白，那么我们发现 $j$ 应该会 $\ge k$，取出最后一个黑点的下一个白点，设其最短距离为 $x$，那么此时 $k\le x+1$ 因为可以从该点往回走一步，并且由于要面对连续的一段白点，那么 $j\ge x$。

因此 $j\ge k-1$。

我们又发现如果 $j$ 比 $k$ 大很多的时候，计算答案时不太可能用 $j$ 更新最短距离。

如果 $j>k+2$，那么填一个黑色格子后 $j$ 就会被 $k+2$ 覆盖，如果不填黑色格子那么 $j$ 始终 $>k$。

因此我们只要维护 $j'=\min(k+2,j)$。

那么我们此时维护的状态 $j',k'$ 就有 $|j'-k'|\le 2$，状态数 $\mathcal O(m)$。

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

代码呈现

#include<bits/stdc++.h> 
using namespace std;
const int MAXN=4005,MOD=1e9+7;
inline void add(int &x,const int &y) { x=(x+y>=MOD)?x+y-MOD:x+y;}
int f[MAXN][5][2],g[MAXN][5][2];
char s[MAXN];
signed main() {
	int n,m;
	scanf("%d%d%s",&n,&m,s+1);
	f[0][2][0]=1;
	for(int i=1;i<n;++i) {
		memset(g,0,sizeof(g));
		auto upd=[&](int j,int k,int o,const int &w) {
			j=min(j,k+2),k=min(k,j+2),add(g[j][k-j+2][o],w);
		};
		for(int j=0;j<=m+2;++j) for(int k=j-2;k<=j+2;++k) {
			const int &w0=f[j][k-j+2][0],&w1=f[j][k-j+2][1];
			if(s[i]!='B') {
				upd(j+1,k,0,w0);
				upd(min(j+1,k+1),min(j+2,k),0,w1);
			}
			if(s[i]!='A') {
				upd(min(j,k+2),min(j+1,k+1),1,w0);
				upd(j,k+1,1,w1);
			}
		}
		memcpy(f,g,sizeof(f));
	}
	int ans=0;
	for(int j=0;j<=m+2;++j) for(int k=j-2;k<=j+2;++k) if(min(j,k)+1<=m) {
		add(ans,f[j][k-j+2][0]),add(ans,f[j][k-j+2][1]);
	}
	printf("%d\n",ans);
	return 0;
}

*J. [ARC127F] Express

Problem Link

题目大意

给定 $a,b,v,m$，每次操作可以给 $v$ 加上或减去 $a/b$，任何时候要在 $[0,m]$ 范围内，求能得到多少 $v$。

数据范围：$a,b,v,m\le 10^9,\gcd(a,b)=1$。

思路分析

我们发现当 $a+b\le m+1$ 时，我们能得到任何一个 $x$。

设 $x=v+pa+qb$，其中 $p\in[0,b),a\le b$，此时我们不断进行 $+a$ 直到进行 $p$ 次或 $p+a>m$。

如果进行了 $p$ 次，直接进行 $q$ 次 $+b$ 即可。

否则由于 $b\le m+1-a$，因此 $p-b>m-a-b\ge -1$，即 $p-b\ge 0$，我们总能进行 $-b$ 后再 $+a$ 的操作。

否则 $a+b\ge m+2$，如果我们第一次操作是 $+a$，很显然下一次操作不会是 $-a$，且 $p+a+b>m$，因此也不会是 $+b$，所以我们只能操作 $+a,-b$，并且每次操作都是这两个之一。

由于 $a+b\ge m+2$，所以每次 $+a$ 和 $-b$ 至多有一个可以使用。

那么我们就能得到生成所有 $v$ 的方式：

每次选择 $v+a,v-b$ 中合法的一个直到无法操作。
每次选择 $v-a,v+b$ 中合法的一个直到无法操作。

那么所有的 $v$ 构成两条链，我们首先可以证明每条链不成环：

设一个极小的环由 $p$ 个 $+a$ 和 $q$ 个 $-b$ 构成，那么 $pa=qb$，由于 $\gcd(a,b)=1$，因此 $p=kb,q=ka,k\in\mathbb{Z^+}$。

因此 $p+q\ge a+b\ge m+2$，那么这个环经过了 $\ge m+2$ 个不同的点，显然导出矛盾。

并且我们还能证明两条链不相交：

取出第一个交点 $x$，我们可以通过 $+a,-b$ 和 $-a,+b$ 操作同时得到 $v\to x$。

那么我们发现 $-a,+b$ 的 $v\to x$ 路径等价于 $+a,-b$ 的 $x\to v$ 路径，那么我们就找到了 $+a,-b$ 操作做构成的简单环，导出矛盾。

那么我们只要计算两条链的长度。

先考虑 $+a,-b$ 的链，显然我们能把 $v$ 不断对 $b$ 取模再 $+a$，那么链上 $+a$ 次数 $p$ 就是第一个 $(v+pa)\bmod b+a>m$ 的 $p$。

确定 $p$ 后链上 $-b$ 次数就是 $\left\lfloor\dfrac{v+ap}{b}\right\rfloor$。

考虑把 $v$ 从 $\bmod b$ 中提出来，这是可以做到的，设 $v_0=v\bmod b$，那么 $(v+pa)\bmod b=v_0+pa\bmod b$ 当且仅当 $pa\bmod b\le b-1-v_0$。

我们发现 $pa\bmod b>b-1-v_0$ 时 $(v+(p-1)a)\bmod b+a\ge a+b\ge m+2$，因此此时的 $p$ 一定不合法。

那么我们只要考虑 $pa\bmod b\le b-1-v_0$ 且 $v_0+pa\bmod b+a>m$ 的第一个 $p$。

即求出最小的 $p$ 使得 $pa\bmod b\in[m+1-v_0-a,b-1-v_0]$，这就是 ARC166E 那题的技巧，类似辗转相除地做即可。

时间复杂度 $\mathcal O(\log \max(a,b))$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll solve(ll l,ll r,ll a,ll p) { //ax mod p in [l,r]
	if(!l) return 0;
	if((l+a-1)/a*a<=r) return (l+a-1)/a;
	// l <= ax-kp <= r
	// x >= (kp+l)/a
	// -r%a <= pk%a <= -l%a
	ll k=solve((a-r%a)%a,(a-l%a)%a,p%a,a);
	return (k*p+l+a-1)/a;
}
ll calc(ll a,ll b,ll v,ll m) { //+a -b
	ll p=0,v0=v%b;
	if(v0+a<=m) p=solve(m-a-v0+1,b-v0-1,a,b);
	return p+(v+a*p)/b;
}
signed main() {
	ios::sync_with_stdio(false);
	int T; cin>>T;
	while(T--) {
		ll a,b,v,m;
		cin>>a>>b>>v>>m;
		if(a+b<=m+1) cout<<m+1<<"\n";
		else cout<<calc(a,b,v,m)+calc(b,a,v,m)+1<<"\n";
	}
	return 0;
}

Round #19 - 2024.10.11

A. [ARC125E] Box

Problem Link

题目大意

$n$ 个物品，第 $i$ 种物品有 $a_i$ 个，$m$ 盒子，每个盒子每种物品 $\le b_i$ 个，总数 $\le c_i$，求放入盒子的物品总数最大值。

数据范围：$n,m\le 2\times 10^5$。

思路分析

直接建立网络流模型，左部点为物品，$S\to i$ 流量 $a_i$，右部点为盒子，$j\to T$ 流量 $c_j$，$i\to j$ 流量 $b_j$。

考虑最小割最大流转化，用组合意义计算最小割。

设 $S\to i$ 切掉了 $k$ 个，那么对于每个盒子，不存在 $S\to j\to T$ 的最小代价为 $\min(c_j,(n-k)\times b_j)$。

注意这个和值具体切掉了哪 $k$ 条边没有关系，直接切掉最大的 $k$ 条，枚举 $k$，动态维护 $\min(c_j,(n-k)\times b_j)$，维护 $j$ 决策切换到 $b_j$ 的时刻即可。

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
int n,m;
ll a[MAXN],b[MAXN],c[MAXN],A,B,C,ans;
vector <int> s[MAXN];
signed main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]),A+=a[i];
	for(int i=1;i<=m;++i) scanf("%lld",&b[i]),B+=b[i];
	for(int i=1;i<=m;++i) {
		scanf("%lld",&c[i]);
		if(b[i]*n>c[i]) s[c[i]/b[i]+1].push_back(i);
	}
	sort(a+1,a+n+1),ans=A;
	for(int k=0;k<=n;++k) { //min(kb,c)
		for(int j:s[k]) B-=b[j],C+=c[j];
		ans=min(ans,A+k*B+C),A-=a[n-k];
	}
	printf("%lld\n",ans);
	return 0;
}

B. [ARC124E] Pass

Problem Link

题目大意

$n$ 个人站成环，第 $i$ 个人手里有 $a_i$ 个球，每个人选择 $x_i\in[0,a_i]$，同时把 $x_i$ 个球传给下一个人。

求所有可能得到的局面中每个人手中球数乘积之和。

数据范围：$n\le 10^5$。

思路分析

首先我们对每种局面刻画一组唯一的 $\{x_i\}$，如果所有 $x_i>0$，可以把他们全部 $-1$，容易证明每一种终态都唯一对应一组解。

因此我们计算所有操作序列的结果之和，减去所有 $x_i>0$ 的操作序列结果之和。

只考虑所有操作序列的结果之和，那么乘积等价于在每个人手中取一个球的方案数，枚举每个人手中的球来自自己还是前一个人。

设 $f_{i,0/1}$ 表示考虑了前 $i$ 个人的 $x$，第 $i$ 个人选择的球来自自己还是前一个人，并且球来自 $1\sim i-1$ 的贡献已经计算完毕。

转移时把原来第 $i$ 个人手中球的贡献计算掉，初始值枚举第 $1$ 个人的状态后断环为链即可。

钦定 $x_i>0$ 只需要简单改变一些转移贡献的计算。

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5,MOD=998244353,i6=(MOD+1)/6;
ll s1(ll x) { return x*(x+1)/2%MOD; }
ll s2(ll x) { return x*(x+1)%MOD*(2*x+1)%MOD*i6%MOD; }
int n,a[MAXN];
ll f[MAXN][2];
ll dp(int o,int c) {
	memset(f,0,sizeof(f)),f[1][c]=1;
	for(int i=1;i<=n;++i) {
		f[i+1][0]=(f[i][0]*s1(a[i]-o)+f[i][1]*(a[i]+1-o))%MOD;
		f[i+1][1]=(f[i][0]*(s1(a[i])*a[i]%MOD+MOD-s2(a[i]))+f[i][1]*s1(a[i]))%MOD;
	}
	return f[n+1][c];
}
signed main() {
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	printf("%lld\n",(dp(0,0)+dp(0,1)+MOD*2-dp(1,0)-dp(1,1))%MOD);
	return 0;
}

C. [ARC123F] Insert

Problem Link

题目大意

对于一个序列 $a$，一次操作会在所有 $a_i,a_{i+1}$ 中间插入一个 $a_i+a_{i+1}$，初始 $a=[x,y]$，求 $a^{\infty}$ 中 $\le n$ 的元素中的第 $l\sim r$ 个。

数据范围：$n\le 3\times 10^5$。

思路分析

序列中的每个元素都是 $ux+vy$，并且 $\dfrac{u}v$ 就是 Stern-Brocot Tree。

根据 Stern-Brocot Tree 的结论，其子树中会出现所有最简真分数恰好一次，即所有 $\gcd(u,v)=1$ 的 $ux+vy$ 恰好一次。

那么我们就可以快速计算子树大小，求有多少 $ux+vy\le n$ 且 $\gcd(u,v)=1$，莫比乌斯反演得到：

\[\sum_{d=1}^n\mu(d)\sum_{i=1}^{n/d/x}\left\lfloor\dfrac{\lfloor n/d\rfloor-ix}{y}\right\rfloor \]

可以用整除分块配合拓展欧几里得做到 $\mathcal O(\sqrt n\log n)$ 计算。

求 Stern-Brocot Tree 上第 $l$ 个元素的过程可以倍增地跳方向相同的链，这样的转向次数是 $\mathcal O(\log n)$ 的，复杂度 $\mathcal O(n+\sqrt n\log ^3n)$。

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+5;
ll fs(ll a,ll b,ll c,ll n) { //i=0~n[ai+b/c]
	if(!a) return (b/c)*(n+1);
	if(a*n+b<c) return 0;
	if(a>=c||b>=c) return fs(a%c,b%c,c,n)+(a/c)*n*(n+1)/2+(b/c)*(n+1);
	return (a*n+b)/c*(n+1)-fs(c,c-b+a-1,a,(a*n+b)/c-1);
}
ll Fs(ll a,ll b,ll c,ll n) {
	ll s=0;
	if(a<0) {
		ll ta=(a%c+c)%c;
		s+=n*(n+1)/2*((a-ta)/c);
		a=ta;
	}
	if(b<0) {
		ll tb=(b%c+c)%c;
		s+=(n+1)*((b-tb)/c);
		b=tb;
	}
	return s+fs(a,b,c,n);
}
int n,mu[MAXN],smu[MAXN];
vector <int> PR;
bool isc[MAXN];
inline ll calc(ll a,ll b) {
	ll ans=0;
	for(ll l=1,r;l<=n;l=r+1) {
		r=n/(n/l);
		if(n/l<a+b) break;
		ans+=(smu[r]-smu[l-1])*Fs(-a,n/l-a,b,n/l/a-1);
	}
	return ans;
}
ll A,B;
typedef array<ll,2> pii;
inline pii operator +(const pii &x,const pii &y) { return {x[0]+y[0],x[1]+y[1]}; }
inline pii operator *(const pii &x,ll y) { return {x[0]*y,x[1]*y}; }
inline ll val(const pii &x) { return x[0]*A+x[1]*B; }
ll rem=0;
void out(pii x,pii y,ll l,ll r) {
	if(rem<=0) return ;
	ll mid=val(x+y);
	if(mid>n) return ;
	out(x,x+y,l,r);
	if(rem) printf("%lld ",mid),--rem;
	out(x+y,y,l,r);
}
void dfs(pii x,pii y,ll l,ll r) {
	if(rem<=0) return ;
	ll a=val(x),b=val(y),mid=val(x+y);
	if(mid>n) return ;
	ll cnt=calc(a,mid)+1;
	if(l==cnt) {
		printf("%lld ",mid),--rem;
		return out(x+y,y,l,r);
	}
	if(l<cnt) {
		int d=0;
		for(int k=19;~k;--k) {
			if(l<=calc(a,val(x*(d|1<<k)+y))) d|=1<<k;
		}
		dfs(x,x*d+y,l,r);
		for(int i=d;i&&rem>0;--i) {
			printf("%lld ",val(x*i+y)),--rem;
			out(x*i+y,x*(i-1)+y,l,r);
		}
	} else {
		ll all=calc(a,b);
		int d=0;
		for(int k=19;~k;--k) {
			if(all-calc(val(x+y*(d|1<<k)),b)<l) d|=1<<k;
		}
		ll sz=all-calc(val(x+y*d),b);
		dfs(x+y*d,y,l-sz,r-sz);
	}
}
signed main() {
	ll l,r;
	scanf("%lld%lld%d%lld%lld",&A,&B,&n,&l,&r);
	mu[1]=1;
	for(int i=2;i<=n;++i) {
		if(!isc[i]) PR.push_back(i),mu[i]=-1;
		for(int p:PR) {
			if(i*p>n) break;
			isc[i*p]=true,mu[i*p]=-mu[i];
			if(i%p==0) { mu[i*p]=0; break; }
		}
	}
	for(int i=1;i<=n;++i) smu[i]=smu[i-1]+mu[i];
	ll all=calc(A,B);
	if(l==1) printf("%lld ",A),--r;
	else --l,--r;
	if(l>r) return 0;
	if(l<=all) rem=r-l+1,dfs({1,0},{0,1},l,r);
	if(r>all) printf("%lld ",B);
	return 0;
}

*D. [ARC125F] Backpack

Problem Link

题目大意

给定 $n$ 个点的树，求有多少 $(s,i)$ 满足 $s$ 可以表示成树上 $i$ 个不同节点的度数和。

数据范围：$n\le 2\times 10^5$。

思路分析

很显然树只是限定度数序列 $d_i$ 满足 $\sum d_i=2n-2$，给所有 $d_i$ 减去一得到 $\sum d_i=n-2$ 的自然数序列。

对于每个 $s$，设 $L_s,R_s$ 表示 $\sum d=s$ 时最少、最多分别能选出多少个点。

设有 $z$ 个 $d_i=0$，那么 $L_s$ 对应方案不包含 $0$，$R_s$ 对应方案一定包含所有 $0$。

因此通过修改 $0$ 数量能得到选出节点数量 $[L_s,L_s+z]\cup [R_s-z,R_s]$ 的所有方案。

观察发现 $R_s-L_s\le 2z+1$。

对于任何一种方案，设选出 $i$ 个物品和为 $s$，一定有 $s-i\ge -z$，因为只有 $d_i=0$ 的点会有 $-1$ 贡献。

考虑取出补集得到 $n-i$ 个物品和为 $n-2-s$，那么 $s-i\le z-2$。

因此 $s-L_s,s-R_s\in[-z,z-2]$，原结论得证。

我们只要求 $\sum R_s-L_s+1$，由于本质不同的 $d_i$ 只有 $\mathcal O(\sqrt n)$ 个，单调队列优化多重背包即可。

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

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n,d[MAXN],c[MAXN],f[MAXN],g[MAXN],mx[MAXN],q[MAXN];
signed main() {
	scanf("%d",&n);
	for(int i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),++d[u],++d[v];
	for(int i=1;i<=n;++i) ++c[d[i]-1];
	memset(f,-0x3f,sizeof(f)),f[0]=c[0];
	for(int x=1;x<=n;++x) if(c[x]) {
		memcpy(g,f,sizeof(g));
		for(int r=0;r<x;++r) {
			int hd=1,tl=0;
			for(int i=0;i*x+r<=n;++i) {
				int k=i*x+r;
				while(hd<=tl&&q[hd]<i-c[x]) ++hd;
				if(hd<=tl) g[k]=max(g[k],f[q[hd]*x+r]+i-q[hd]);
				while(hd<=tl&&f[q[hd]*x+r]-q[hd]<=f[k]-i) --tl;
				q[++tl]=i;
			}
		}
		memcpy(f,g,sizeof(f));
	}
	memcpy(mx,f,sizeof(mx));
	memset(f,0x3f,sizeof(f)),f[0]=0;
	for(int x=1;x<=n;++x) if(c[x]) {
		memcpy(g,f,sizeof(g));
		for(int r=0;r<x;++r) {
			int hd=1,tl=0;
			for(int i=0;i*x+r<=n;++i) {
				int k=i*x+r;
				while(hd<=tl&&q[hd]<i-c[x]) ++hd;
				if(hd<=tl) g[k]=min(g[k],f[q[hd]*x+r]+i-q[hd]);
				while(hd<=tl&&f[q[hd]*x+r]-q[hd]>=f[k]-i) --tl;
				q[++tl]=i;
			}
		}
		memcpy(f,g,sizeof(f));
	}
	long long ans=0;
	for(int i=0;i<=n;++i) if(f[i]<=mx[i]) ans+=mx[i]-f[i]+1;
	printf("%lld\n",ans);
	return 0;
}

*E. [AGC054E] Delete

Problem Link

题目大意

对于一个 $n$ 阶排列 $a$，一次操作可以删除 $a_i>\max(a_{i+1},a_{i-1})$ 或 $a_i<\min(a_{i+1},a_{i-1})$ 的 $a_i$。

求有多少 $a_1=x$ 的 $n$ 阶排列可以通过操作删成 $2$ 个元素。

数据范围：$n\le 10^6$。

思路分析

不妨设 $a_1<a_n$，$a_1>a_n$ 等价于统计 $a_1=n-x+1$ 的方案数。

一个排列能被删成两个元素的充分必要条件是存在 $i$ 使得 $a_i\le a_1<a_n\le a_{i+1}$：

考虑充分性：不断删除 $(1,i)$ 和 $(i+1,n)$ 内部元素，最终得到的序列一定有 $a_1>a_2>\cdots>a_i<a_{i+1}>a_{i+2}>\cdots>a_n$，先删 $a_i\sim a_2$，再删 $a_{i+1}\sim a_{n-1}$ 就是一组方案。

必要性可以归纳法证明。

计算不合法排列数，相当于 $[1,a_1]$ 的元素后面不能是 $[a_n,n]$ 的元素，设 $a_n=a_1+k$，得到方案数 $(k-1)!(k-1)^{\overline{k-2}}(k-1)^{\overline{x-1}}$。

化简得到 $(n-x-2)!(x-1)!\sum_{k=0}^{n-x-2}\binom{x+k-1}{k}(k+1)$，把 $\binom{x+k-1}{k}(k+1)$ 看成 $\binom{x+k-1}{k}+x\binom{x+k-1}{k-1}$。

分别用组合数上指标前缀和得到答案为 $(n-2)!\left(\dfrac 1x+\dfrac{n-x-2}{x+1}\right)$。

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

代码呈现

#include<bits/stdc++.h> 
#define ll long long
using namespace std;
const int MAXN=1e6+5,MOD=998244353;
ll fac[MAXN],inv[MAXN];
ll solve(int n,int p) {
	if(p>=n-1) return 0;
	return (inv[p+1]*(n-p-2)+inv[p])%MOD*fac[n-2]%MOD;
}
signed main() {
	for(int i=fac[0]=1;i<MAXN;++i) fac[i]=fac[i-1]*i%MOD;
	inv[1]=1;
	for(int i=2;i<MAXN;++i) inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
	int T; scanf("%d",&T);
	for(int n,p;T--;) {
		scanf("%d%d",&n,&p);
		printf("%lld\n",(fac[n-1]+MOD-solve(n,p)+MOD-solve(n,n-p+1))%MOD);
	}
	return 0;
}

Round #20 - 2024.10.12

A. [ARC119D] Color

Problem Link

题目大意

给定 $n\times m$ 矩阵，每个格子是红或蓝，每次可以选择一个红格子将其所在行或列涂白。

构造一组方案最大化白格子数量。

数据范围：$n,m\le 1000$。

思路分析

对于一个 $(i,j)$ 上的红格子看成左部第 $i$ 个点对右部第 $j$ 个点的连边。

一次染色就是选择一个非孤立点，将其邻边全部删除。

对于一个连通块，显然无论怎么删都会留下一个点，并且可以构造方案：以该点为根求出 dfs 树，每次删叶子即可。

那么设有 $k$ 个连通块，直接枚举有多少个连通块剩下的点是行，非孤立的行、列分别有 $r,c$ 个，那么答案就是 $\max_{i=0}^k(n-r+i)(m-c+k-i)$。

构造方案是简单的，直接 dfs。

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

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2505;
char a[MAXN][MAXN];
int n,m,c=0,sl=0,sr=0;
vector <int> G[MAXN<<1];
vector <int> ver[MAXN<<1];
bool vis[MAXN<<1];
void dfs(int u) {
	vis[u]=true,++(u<=n?sl:sr),ver[c].push_back(u);
	for(int v:G[u]) if(!vis[v]) dfs(v);
}
void out(int u,int fz) {
	vis[u]=true;
	for(int v:G[u]) if(!vis[v]) out(v,u);
	if(fz) {
		if(u<=n) printf("X %d %d\n",u,fz-n);
		else printf("Y %d %d\n",fz,u-n);
	}
}
signed main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) {
		scanf("%s",a[i]+1);
		for(int j=1;j<=m;++j) if(a[i][j]=='R') {
			G[i].push_back(j+n),G[j+n].push_back(i);
		}
	}
	for(int i=1;i<=n+m;++i) if(!vis[i]&&!G[i].empty()) ++c,dfs(i);
	int x=0;
	for(int i=1;i<=c;++i) if((n-sl+x)*(m-sr+c-x)>(n-sl+i)*(m-sr+c-i)) x=i;
	printf("%d\n",sl+sr-c);
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=x;++i) {
		for(int z:ver[i]) if(z<=n) { out(z,0); break;}
	}
	for(int i=x+1;i<=c;++i) {
		for(int z:ver[i]) if(z>n) { out(z,0); break; }
	}
	return 0;
}

B. [ARC121F] Shrink

Problem Link

题目大意

给定 $n$ 个点的树，每个点上填 $0,1$，边上填 $\mathrm{AND},\mathrm{OR}$。

一次操作可以选定一条边 $(u,v)$，将 $u,v$ 合并成一个新的点，权值就是 $u,v$ 两个点的权值经过 $(u,v)$ 上的运算后得到的树。

对于一种填树方法，其是好的当且仅当能通过若干次操作得到一个节点，且其权值为 $1$。

数据范围：$n\le 10^5$。

思路分析

对于每条 $\mathrm{AND}$ 边，优先缩掉一定不劣，因此一棵树是好的当且仅当至少存在一个 $\mathrm{AND}$ 连通块中不包含 $0$。

反面考虑相当于计数所有 $\mathrm{AND}$ 连通块中都有 $0$ 的方案数，$f_{u,0/1}$ 表示 $u$ 子树连通块中是否有 $0$ 的方案数。

转移时先从子树 $\mathrm{AND}$ 卷积，然后分讨 $(u,fa_u)$ 的选择情况。

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5,MOD=998244353;
int n;
ll f[MAXN][2];
vector <int> G[MAXN];
void dfs(int u,int fz) {
	array <ll,2> g{0,1};
	for(int v:G[u]) if(v^fz) {
		dfs(v,u);
		g[0]=(g[0]*(f[v][0]+f[v][1])+g[1]*f[v][0])%MOD;
		g[1]=g[1]*f[v][1]%MOD;
	}
	if(fz) {
		f[u][1]=(g[1]*2+g[0]*2)%MOD;
		f[u][0]=(g[1]+g[0]*2)%MOD;
	} else f[u][0]=g[0],f[u][1]=g[1];
}
signed main() {
	scanf("%d",&n);
	for(int i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
	ll ans=1;
	for(int i=1;i<2*n;++i) ans=ans*2%MOD;
	dfs(1,0);
	ans=(ans-f[1][0]*2-f[1][1])%MOD;
	printf("%lld\n",(ans+MOD)%MOD);
	return 0;
}

C. [ARC120F] Independ

Problem Link

题目大意

给定 $a_1\sim a_n$，求所有大小为 $k$ 的链上独立集的 $a$ 元素之和。

数据范围：$n\le 3\times 10^5$。

思路分析

设独立集个数为 $f(n,k)=\binom{n-k+1}k$

注意到链上独立集并不具有对称性，而环上独立集有较好的性质，每个点被选入独立集的方案都相同，都是 $f(n-2,k-1)$。

回到原问题，未计算的情况一定同时选择了 $a_1,a_n$。

这种独立集一共有 $f(n-4,k-2)$ 个，$a_1,a_n$ 的系数也是这个。

我们只要考虑这种独立集中 $a_3\sim a_{n-2}$ 中的 $a_i$ 贡献，容易发现所有选择 $a_1,a_n$ 的 $k$ 元独立集和 $a_3\sim a_{n-2}$ 中的 $k-2$ 元独立集一一对应。

因此我们只要递归 $a_3\sim a_{n-2},k-2$ 递归算一遍原问题答案即可。

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+5,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; }
ll a[MAXN],s[MAXN],fac[MAXN],ifac[MAXN];
ll g(int n,int m) {
	if(m<0||n<2*m-1) return 0;
	return fac[n+1-m]*ifac[m]%MOD*ifac[n+1-2*m]%MOD;
}
ll f(int l,int r,int k) {
	if(k<=1) return k*(s[r]+MOD-s[l-1])%MOD;
	return ((s[r]-s[l-1])*g(r-l-2,k-1)+(a[l]+a[r])*g(r-l-3,k-2)+f(l+2,r-2,k-2))%MOD;
}
signed main() {
	for(int i=fac[0]=ifac[0]=1;i<MAXN;++i) ifac[i]=ksm(fac[i]=fac[i-1]*i%MOD);
	int n,k,d;
	scanf("%d%d%d",&n,&k,&d);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]),s[i]=(s[i-1]+a[i])%MOD;
	printf("%lld\n",f(1,n,k));
	return 0;
}

*D. [ARC117F] Cycle

Problem Link

给定 $x_0\sim x_{2n-1}$ 排成一个环，限定 $x_i\sim x_{i+n-1}$ 的和 $\ge a_i$，最小化 $\sum x_i$。

数据范围：$n\le 1.5\times 10^5$。

思路分析

显然答案具有可二分性，二分 $X=\sum x_i$ 后，设 $s_i$ 为 $x_i$ 的前缀和，那么所有的限制都是对 $s_i$ 的差分约束：

$s_i\le s_{i+1}$。
$s_i+a_i\le s_{i+n}$。
$s_{i+n}+a_{i+n}-X\le s_i$。
$s_{2n-1}-X\le s_{0}$。

我们发现对 $(i,i+n)$ 分层，按 $i$ 从小到大转移，只有 $n\to n-1$ 和 $2n-1\to 0$ 两条边是逆序转移的。

因此只需要常数轮增广就能得到最短路。

如果常数轮增广后最短路过程仍未结束，说明图上有负环。

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+5;
const ll inf=3e14;
int n;
ll a[MAXN],f[MAXN];
bool chkmax(ll &x,const ll&y) { return x<y?(x=y,1):0; }
bool chk(ll x) {
	memset(f,0,sizeof(f));
	bool fg;
	for(int Q=0;Q<5;++Q) {
		fg=0;
		for(int i=0;i<n;++i) {
			fg|=chkmax(f[i+n],f[i]+a[i]);
			fg|=chkmax(f[i],f[i+n]+a[i+n]-x);
			fg|=chkmax(f[i+1],f[i]);
			if(i<n) chkmax(f[i+n+1],f[i+n]);
		}
		chkmax(f[0],f[2*n-1]-x);
	}
	return !fg&&f[0]>=0;
}
signed main() {
	scanf("%d",&n);
	for(int i=0;i<2*n;++i) scanf("%lld",&a[i]);
	ll l=0,r=inf,w=r;
	for(int i=0;i<n;++i) l=max(l,a[i]+a[i+n]);
	while(l<=r) {
		ll mid=(l+r)>>1;
		if(chk(mid)) r=mid-1,w=mid;
		else l=mid+1;
	}
	printf("%lld\n",w);
	return 0;
}

E. [ARC124F] Meet

Problem Link

题目大意

$n\times m$ 网格中，A 要从 $(1,1)$ 走到 $(n,m)$，B 要从 $(n,1)$ 走到 $(1,m)$。

每次操作可以让 A 往下或往右，B 往上或往右，求有多少种操作序列使得 A，B 恰有一个时刻重合。

数据范围：$n,m\le 2\times 10^5$。

思路分析

先考虑两个人在 $(i,j)$ 重合的方案数，同时走到 $(i,j)$ 的方案数就是 $\binom{n-1+2(j-1)}{i-1,n-i,j-1,j-1}$，从 $(i,j)$ 出发同时走到终点的方案数就是 $\binom{n-1+2(m-j)}{i-1,n-i,m-j,m-j}$。

然后考虑容斥，先求出至少重合一次的方案数，那么在相邻的两次相遇点之间连边，答案再减去边数即可。

显然两次相遇一定在同一行，那么枚举 $(i,j),(i,k)$，从 $j\to k$ 不重合的方案数相当于 $(j,j)\to (k,k)$ 不经过 $y=x$ 直线，即 $2\mathrm{Cat}_{k-j-1}$。

答案还要乘以 $(i,j),(i,k)$ 分别作为起点、终点的方案数。

容易发现 $i$ 对答案无影响，最后乘以 $\dfrac{1}{(i-1)!^2(n-i)!^2}$ 即可。

然后我们要容斥掉重合次数 $>1$ 的方案，即至少存在一条边的方案数，先对每条边产生 $-1$ 的贡献，在对长度为 $2$ 的链 $j\to x\to k$ 的方案计数再减掉。

对于这种情况，$j\to x\to k$ 的方案数就是 $2\mathrm{Cat}_{i-1}$ 自卷积的结果。

我们最后能求出所有 $(i,j)\to (i,k)$ 总的贡献系数是一个和 $k-j$ 有关的值，卷积一次即可。

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

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353,N=1<<20;
int fac[N],ifac[N];
namespace P {
const int G=3;
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;
	}
}
void 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);
}
}
int n,m,f[N],g[N],h[N],c[N],d[N];
signed main() {
	P::poly_init();
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) c[i]=2ll*fac[2*i-2]*ifac[i]%MOD*ifac[i-1]%MOD;
	P::poly_mul(c,c,d,m+1,m+1);
	f[0]=1;
	for(int i=1;i<=m;++i) f[i]=(d[i]+2ll*(MOD-c[i]))%MOD;
	for(int j=1;j<=m;++j) g[j]=1ll*fac[n-1+2*(j-1)]*ifac[j-1]%MOD*ifac[j-1]%MOD;
	P::poly_mul(f,g,h,m+1,m+1);
	int ans=0,sum=0;
	for(int i=1;i<=n;++i) sum=(sum+1ll*ifac[i-1]*ifac[i-1]%MOD*ifac[n-i]%MOD*ifac[n-i])%MOD;
	for(int j=1;j<=m;++j) ans=(ans+1ll*h[j]*fac[n-1+2*(m-j)]%MOD*ifac[m-j]%MOD*ifac[m-j])%MOD;
	printf("%lld\n",1ll*ans*sum%MOD);
	return 0;
}

*F. [AGC057E] Sort

Problem Link

题目大意

给定一个 $n\times m$ 矩阵 $B$，求有多少个矩阵 $A$ 同时满足：

依次对 $A$ 每一行、每一列排序最终得到 $B$。

依次对 $A$ 每一列、每一行排序最终得到 $B$。

数据范围：$n,m\le 1500,B_{i,j}\le 9$。

思路分析

考虑 $B_{i,j}\in\{0,1\}$ 如何做。

那么对 $A$ 每行每列排序，相当于把 $A$ 的每一列按 $0$ 的个数升序排列，每列每行同理。

因此 $A$ 合法当且仅当 $A$ 每行每列 $0$ 的个数构成的可重集和 $B$ 相同。

进一步一定存在排列 $p_n,q_m$ 使得 $B_{p_i,q_i}=A_{i,j}$（把 $B$ 的每行每列根据 $0$ 的个数一一对应到 $A$ 的行列上）。

回到原问题，可以证明 $B$ 合法当且仅当对于每个 $k$，把 $\le k$ 的看成 $0$，剩余看成 $1$ 后合法。

设我们每次取出的排列为 $p^k_n,q^k_m$，那么我们要求 $B(p^k_i,q^k_j)\le k\implies B(p^{k+1}_i,q_{j}^{k+1})\le k+1$。

然后对所有 $p,q$ 计数，但是对于每个 $k$，行和相同的列是本质相同的，要除以对应的排列数。

我们计数 $p^k$ 可以转成计数 $p^k\times \mathrm{inv}(p^{k-1})$，因此要求变成 $B(i,j)\le k\implies B(p^k_i,q^k_j)\le k+1$，这样每层的方案都是独立的。

由于 $B$ 一定是杨表，因此设 $r^k_{i},c^k_j$ 表示此时第 $i$ 行、第 $j$ 列的 $0$ 的个数，那么 $B(i,j)\le k\iff j\le r^k_i\iff i\le r^k_j$。

那么对于 $j\in[1,r_i^k]$ 都有 $p_i^{k}\le c(q_j^k)$，由于 $c$ 单调递减，因此等价于 $p_{i}^k\le c(\max_{j=1}^{r_i^k}q_j^k)$。

因此可以 dp，设 $f_{i,j}$ 表示 $\max q^k_1\sim q^k_i=j$ 的方案数，转移时考虑 $q_i$ 是否是最大值，并且把 $r_x^k=i$ 的 $p_x^k$ 确定取值，由于每个 $p$ 的取值范围单调减小，因此当前 $p_x^k$ 方案数就是 $\max(0,j-x+1)$，

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1505,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; }
int n,m,r[10][MAXN],c[10][MAXN],a[MAXN][MAXN],cnt[MAXN];
ll f[MAXN][MAXN],fac[MAXN],ifac[MAXN];
signed main() {
	for(int i=fac[0]=ifac[0]=1;i<MAXN;++i) ifac[i]=ksm(fac[i]=fac[i-1]*i%MOD);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {
		scanf("%d",&a[i][j]);
		for(int k=a[i][j];k<10;++k) ++r[k][i],++c[k][j];
	}
	ll ans=1;
	for(int k=0;k<9;++k) {
		memset(f,0,sizeof(f)),f[0][0]=1;
		int p=n;
		for(;p&&!r[k][p];--p);
		for(int i=1;i<=m;++i) {
			ll s=f[i-1][0];
			for(int j=1;j<=m;++j) {
				f[i][j]=(f[i-1][j]*(j-i+1)+s)%MOD;
				s=(s+f[i-1][j])%MOD;
			}
			for(;p&&r[k][p]==i;--p) {
				for(int j=1;j<=m;++j) f[i][j]=f[i][j]*max(0,c[k+1][j]-p+1)%MOD;
			}
		}
		ans=ans*f[m][m]%MOD;
		for(int i=1;i<=n;++i) if(r[k][i]) ++cnt[r[k][i]];
		for(int i=1;i<=m;++i) ans=ans*ifac[cnt[i]]%MOD,cnt[i]=0;
		for(int i=1;i<=m;++i) ++cnt[c[k][i]];
		for(int i=0;i<=n;++i) ans=ans*ifac[cnt[i]]%MOD,cnt[i]=0;
	}
	printf("%lld\n",ans);
	return 0;
}

标签：le,Noip,记录,int,ll,2024,MAXN,mathcal,MOD
From： https://www.cnblogs.com/DaiRuiChen007/p/18488174

2024 Noip 做题记录（五）

Round #17 - 2024.10.8

A. [ARC135D] Square

B. [ARC173E] Adjacent

C. [ARC118E] Obstacle

D. [ARC135E] Multiple

E. [ARC133E] Median

*F. [AGC054D] Swap

*G. [AGC055D] Fill

*H. [ARC174F] Nim

*I. [ARC176F] Cover

Round #18 - 2024.10.10

A. [ARC126E] Exchange

B. [ARC128E] Different

C. [ARC132F] Strategy

D. [ARC130E] Minimum

E. [ARC129E] Cost

*F. [ARC129F] Catch

*G. [ARC131F] Pattern

*H. [ARC118F] Ratio

*I. [ARC119F] Distance

*J. [ARC127F] Express

Round #19 - 2024.10.11

A. [ARC125E] Box

B. [ARC124E] Pass

C. [ARC123F] Insert

*D. [ARC125F] Backpack

*E. [AGC054E] Delete

Round #20 - 2024.10.12

A. [ARC119D] Color

B. [ARC121F] Shrink

C. [ARC120F] Independ

*D. [ARC117F] Cycle

E. [ARC124F] Meet

*F. [AGC057E] Sort

相关文章

赞助商

阅读排行