CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:contest:arc_124 [2021/09/02 20:14]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:contest:arc_124 [2021/09/03 19:35] (当前版本)
jxm2001
@@ 行 74: / 行 74: @@
 </hidden>
+===== E - Pass to Next =====
+==== 题意 ====
+给定 $n$ 个人围成一个环，第 $i$ 个人初始时有 $a_i$ 个球，接下来第 $i$ 个人选中 $0\le k\le a_i$ 个球传给第 $i+1$ 个人。
+注意第 $n$ 个人把球给第一个人，且所有人同时传球。设一次操作后第 $i$ 个人手上有 $b_i$ 个球，则得到序列 $B$。
+对所有可能序列 $B$，先进行一次去重，然后定义每个序列权值为 $\prod_{i=1}^n b_i$，求余下所有序列的权值和。
+==== 题解 ====
+设每个人的传球数为 $c_i$，不难发现 $\min(c_i)\gt 0$ 时所有 $c_i$ 减一最终得到的序列 $B$ 不变。
+于是不妨假设 $\min(c_i)=0$，不难发现在此基础上不同的序列 $C$ 对应不同的序列 $B$。
+利用容斥，答案就等于 $c_i$ 不限制时产生的所有序列 $B$ 的权值和减去 $c_i$ 强制都大于 $0$ 时产生的所有序列 $B$ 的权值和。
+接下来考虑如何计算 $c_i$ 无限制时的答案。首先不考虑环的情况，设 $\text{dp}(i,j)$ 表示第 $c_i=j$ 时只考虑前 $i$ 个人产生的序列的权值和，于是有
+$$
+\text{dp}(i,j)=\sum_{k=0}^{c_{i-1}}\text{dp}(i-1,k)(c_i+k-j)
+$$
+考虑加速 $\text{dp}$，设 $s_1(i)=\sum_{j=0}^{c_i}\text{dp}(i,j),s_2(i)=\sum_{j=0}^{c_i}j\times \text{dp}(i,j)$，于是有
+$$
+\text{dp}(i,j)=(c_i-j)s_1(i-1)+s_2(i-1)\\
+s_1(i)=\sum_{j=0}^{c_i}\text{dp}(i,j)=\sum_{j=0}^{c_i}((c_i-j)s_1(i-1)+s_2(i-1))=(c_is_1(i-1)+s_2(i-1))\sum_{j=0}^{c_i}1-s_1(i-1)\sum_{j=0}^{c_i}j\\
+s_2(i)=\sum_{j=0}^{c_i}j\times \text{dp}(i,j)=\sum_{j=0}^{c_i}j((c_i-j)s_1(i-1)+s_2(i-1))=(c_is_1(i-1)+s_2(i-1))\sum_{j=0}^{c_i}j-s_1(i-1)\sum_{j=0}^{c_i}j^2
+$$
+于是上式可以 $O(n)$ 递推。最后考虑环的处理，不难发现 $b_i$ 的贡献可以分解为本来属于自己的球和来自别人的球。
+于是答案可以分解 $\prod_{i=1}^n b_i=(b_1-c_n)\prod_{i=2}^n b_i+c_n\prod_{i=2}^n b_i$。
+对于 $(b_1-c_n)\prod_{i=2}^n b_i$，由于只考虑第一个人自己的球，于是有 $\text{dp}(1,i)=a_1-i$，最后贡献为 $\sum_{i=0}^{a_n}\text{dp}(n,i)=s_1(n)$。
+对于 $c_n\prod_{i=2}^n b_i$，由于只考虑第 $n$ 个人传给第一个人的球，于是有 $\text{dp}(1,i)=1$，最后贡献为 $\sum_{i=0}^{a_n}i\times \text{dp}(n,i)=s_2(n)$。
+关于 $c_i$ 强制都大于 $0$ 的情况，无非是部分公式的下标从 $1$ 开始，计算过程与上述情况类似。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,mod=998244353;
+int quick_pow(int n,int k){
+	int ans=1;
+	while(k){
+		if(k&1)ans=1LL*ans*n%mod;
+		n=1LL*n*n%mod;
+		k>>=1;
+	}
+	return ans;
+}
+int inv2,inv6,a[MAXN],dp[2][MAXN];
+int pre1(int n){
+	return 1LL*n*(n+1)%mod*inv2%mod;
+}
+int pre2(int n){
+	return 1LL*n*(n+1)%mod*(2*n+1)%mod*inv6%mod;
+}
+void calc(int n,int s1,int s2,bool zero){
+	dp[0][1]=s1,dp[1][1]=s2;
+	_rep(i,2,n){
+		dp[0][i]=((1LL*a[i]*dp[0][i-1]+dp[1][i-1])%mod*(a[i]+zero)-1LL*dp[0][i-1]*pre1(a[i]))%mod;
+		dp[1][i]=((1LL*a[i]*dp[0][i-1]+dp[1][i-1])%mod*pre1(a[i])-1LL*dp[0][i-1]*pre2(a[i]))%mod;
+	}
+}
+int solve(int n,bool zero){
+	calc(n,a[1]+zero,pre1(a[1]),zero);
+	int t=dp[1][n];
+	calc(n,(1LL*(a[1]+zero)*a[1]-pre1(a[1]))%mod,(1LL*pre1(a[1])*a[1]-pre2(a[1]))%mod,zero);
+	return (t+dp[0][n])%mod;
+}
+int main(){
+	int n=read_int();
+	_rep(i,1,n)
+	a[i]=read_int();
+	inv2=quick_pow(2,mod-2);
+	inv6=quick_pow(6,mod-2);
+	int ans=(solve(n,true)-solve(n,false))%mod;
+	ans=(ans+mod)%mod;
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+===== F - Chance Meeting =====
+==== 题意 ====
+给定 $n\times m$ 的网格。$A$ 开始位于 $(1,1)$，可以从 $(r,c)$ 到达 $(r+1,c)$ 或 $(r,c+1)$，最终目的地为 $(n,m)$。
+$B$ 开始位于 $(n,1)$，可以从 $(r,c)$ 到达 $(r-1,c)$ 或 $(r,c+1)$，最终目的地为 $(1,m)$。
+每个时刻只有一个人能移动，问两个人恰好相遇一次的方案。两个方案不同当且仅当某一时刻移动的人物不同或人物的移动方向不同。
+==== 题解 ====
+为方便计算，令 $n\gets n-1,m\gets m-1$，坐标从 $0$ 开始计算。$B$ 选择 $(r,c)\to (r-1,c)$ 等效于 $A$ 选择 $(r,c)\to (r+1,c)$。
+于是 $A$ 最终目的地变为 $(2n,m)$，$B$ 最终目的地变为 $(n,m)$，$B$ 只在横线运动，于是可以认为两个人只能在 $(n,i)(0\le i\le m)$ 相遇。
+设两人在 $(n,i)$ 相遇，且在到达前不相遇的方案数为 $f(i)$。
+由于两人仅相遇一次，所有两人从 $(n,i)$ 出发向终点移动的过程也不相遇，该过程的逆过程可以认为是从起点出发到 $(n,m-i)$ 相遇的过程。
+由于将 $B$ 选择 $(r,c)\to (r-1,c)$ 等效于 $A$ 选择 $(r,c)\to (r+1,c)$，所以总方案数还要乘上 ${2n\choose n}$，于是合法方案数为
+$$
+\sum_{i=0}^m {2n\choose n}f(i)f(m-i)
+$$
+接下来考虑计算 $f(i)$。设 $g(i)$ 表示两个人在 $(n,i)$ 相遇的方案数，于是有 $g(i)={n+2i\choose n}{2i\choose i}$。
+$f(i)$ 等于 $g(i)$ 再减去多次相遇的方案。考虑枚举两个人在 $(n,i)$ 相遇前最后一次相遇的位置 $j$，于是两个人在 $(n,j)\to (n,i)$ 的过程中不相遇。
+可以任取一个人先走，假定先走的人的每次移动为 $+1$，后走的人的每次移动为 $-1$。
+于是问题等价于现有 $i-j$ 个 $\pm 1$，要求构造序列，使得序列中间部分前缀和大于 $0$，且序列开头是 $+1$，序列末尾是 $-1$。
+删去序列头尾，问题等价于 $i-j-1$ 个 $\pm 1$，要求构造序列，使得序列前缀和不小于 $0$。
+上述序列数对应 $C(i-j-1)$，其中 $C(n)=\frac {2n\choose n}{n+1}$ 表示卡特兰数，于是有
+$$
+f(i)=g(i)-\sum_{j=0}^{i-1}g(j)C(i-j-1)
+$$
+卷积加速即可，时间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e5+5,MAXV=MAXN*3,mod=998244353;
+int quick_pow(int n,int k){
+	int ans=1;
+	while(k){
+		if(k&1)ans=1LL*ans*n%mod;
+		n=1LL*n*n%mod;
+		k>>=1;
+	}
+	return ans;
+}
+int frac[MAXV],invf[MAXV];
+int C(int n,int m){
+	return 1LL*frac[n]*invf[m]%mod*invf[n-m]%mod;
+}
+int Inv(int n){
+	return 1LL*invf[n]*frac[n-1]%mod;
+}
+namespace Poly{
+	const int G=3,Mod=998244353;
+	int rev[MAXN<<2],Wn[30][2];
+	void init(){
+		int m=Mod-1,lg2=0;
+		while(m%2==0)m>>=1,lg2++;
+		Wn[lg2][1]=quick_pow(G,m);
+		Wn[lg2][0]=quick_pow(Wn[lg2][1],Mod-2);
+		while(lg2){
+			m<<=1,lg2--;
+			Wn[lg2][0]=1LL*Wn[lg2+1][0]*Wn[lg2+1][0]%Mod;
+			Wn[lg2][1]=1LL*Wn[lg2+1][1]*Wn[lg2+1][1]%Mod;
+		}
+	}
+	int build(int k){
+		int n,pos=0;
+		while((1<<pos)<=k)pos++;
+		n=1<<pos;
+		_for(i,0,n)rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
+		return n;
+	}
+	void NTT(int *f,int n,bool type){
+		_for(i,0,n)if(i<rev[i])
+		swap(f[i],f[rev[i]]);
+		int t1,t2;
+		for(int i=1,lg2=0;i<n;i<<=1,lg2++){
+			int w=Wn[lg2+1][type];
+			for(int j=0;j<n;j+=(i<<1)){
+				int cur=1;
+				_for(k,j,j+i){
+					t1=f[k],t2=1LL*cur*f[k+i]%Mod;
+					f[k]=(t1+t2)%Mod,f[k+i]=(t1-t2)%Mod;
+					cur=1LL*cur*w%Mod;
+				}
+			}
+		}
+		if(!type){
+			int div=quick_pow(n,Mod-2);
+			_for(i,0,n)f[i]=(1LL*f[i]*div%Mod+Mod)%Mod;
+		}
+	}
+	void mul(int *f,int _n,int *g,int _m){
+		int n=build(_n+_m-2);
+		_for(i,_n,n)f[i]=0;_for(i,_m,n)g[i]=0;
+		NTT(f,n,1);NTT(g,n,1);
+		_for(i,0,n)f[i]=1LL*f[i]*g[i]%Mod;
+		NTT(f,n,0);
+	}
+}
+void Init(){
+	int n=MAXV-1;
+	frac[0]=1;
+	_rep(i,1,n)
+	frac[i]=1LL*frac[i-1]*i%mod;
+	invf[n]=quick_pow(frac[n],mod-2);
+	for(int i=n;i;i--)
+	invf[i-1]=1LL*invf[i]*i%mod;
+	Poly::init();
+}
+int f[MAXN],g[MAXN],A[MAXN<<2],B[MAXN<<2];
+int main(){
+	Init();
+	int n=read_int()-1,m=read_int()-1,ans=0;
+	_rep(i,0,m){
+		g[i]=1LL*C(n+2*i,n)*C(2*i,i)%mod;
+		A[i]=g[i];
+		B[i]=1LL*C(2*i,i)*Inv(i+1)%mod;
+	}
+	Poly::mul(A,m,B,m);
+	f[0]=g[0];
+	_rep(i,1,m)
+	f[i]=(g[i]+1LL*(mod-2)*A[i-1])%mod;
+	_rep(i,0,m)
+	ans=(ans+1LL*f[i]*f[m-i])%mod;
+	ans=1LL*ans*C(2*n,n)%mod;
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具