专栏文章

题解：P4351 [CERC2015] Frightful Formula

zzifanwang
P4351题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minz4m50
此快照首次捕获于
2025/12/02 10:43
3 个月前
此快照最后确认于
2025/12/02 10:43
3 个月前
查看原文
题意，即给定 F(1,i),F(i,1)F(1,i),F(i,1)，定义 F(i,j)=aF(i,j−1)+bF(i−1,j)+c (i,j∈[2,n])F(i,j)=aF(i,j-1)+bF(i-1,j)+c\ (i,j\in [2,n])，求 F(n,n)F(n,n)。
考虑将其转化为网格图计数问题，定义向下走的权值为 bb，向右走的权值为 aa，一条路径的权值为各步权值之积。将所有 (i,2)(i,2) 和 (2,i)(2,i) 到 (n,n)(n,n) 的路径权值分别乘上 F(i,1),F(1,i)F(i,1),F(1,i) 求和，就得到了答案的一部分。
考虑剩下的部分，也就是 cc 乘上一些东西。显然这一部分就是所有满足 i,j∈[2,n]i,j\in [2,n] 的 (i,j)→(n,n)(i,j)\rightarrow (n,n) 的路径权值乘上 cc 的和。
将两部分求和即可得到答案：
∑i=2n(2n−i−2n−2)an−2bn−iF(i,1)+∑i=2n(2n−i−2n−2)bn−2an−iF(1,i)+c∑i=0n−2∑j=0n−2(i+jj)aibj\sum_{i=2}^n {2n-i-2\choose n-2}a^{n-2}b^{n-i}F(i,1)+ \sum_{i=2}^n {2n-i-2\choose n-2}b^{n-2}a^{n-i}F(1,i)+ c\sum_{i=0}^{n-2}\sum_{j=0}^{n-2}{i+j\choose j}a^ib^j
根据经典结论 ∑i=0n(i+mi)=(m+n+1n)\sum_{i=0}^n{i+m\choose i}={m+n+1\choose n} 容易求出第一部分的值。考虑第二部分：
c∑i=0n−2∑j=0n−2(i+jj)aibjc\sum_{i=0}^{n-2}\sum_{j=0}^{n-2}{i+j\choose j}a^ib^j
枚举 ii，那么剩下要求的就是 fi=∑j=0n−2(i+jj)bjf_i=\sum_{j=0}^{n-2}{i+j\choose j}b^j，答案即为 c∑i=0n−2fiaic\sum_{i=0}^{n-2}f_ia^i。f0f_0 是好求的，考虑通过 fif_i 求出 fi+1f_{i+1}，由组合数基本性质易得：
fi+1=∑j=0n−2((i+jj)+[j>0](i+1+j−1j−1))bj=fi+bfi+1−(i+n−1n−2)bn−1f_{i+1}=\sum_{j=0}^{n-2}\left({i+j\choose j}+[j>0]{i+1+j-1\choose j-1}\right)b^j=f_i+bf_{i+1}-{i+n-1\choose n-2}b^{n-1}
解得：
fi+1=(i+n−1n−2)bn−1−fib−1f_{i+1}=\frac{{i+n-1\choose n-2}b^{n-1}-f_i}{b-1}
特判一下 b=1b=1，然后就做完了，时间复杂度 O(n)\mathcal O(n)。
参考代码：
CPP
#include<bits/stdc++.h>
#define ll long long
#define mxn 400003
#define md 1000003
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rept(i,a,b) for(int i=(a);i<(b);++i)
#define drep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int n;
ll a,b,c,xi,ans,f[mxn],d1[mxn],d2[mxn],p1[mxn],p2[mxn],fac[mxn],ifac[mxn];
ll power(ll x,int y){
	ll ans=1;
	for(;y;y>>=1){
		if(y&1)ans=ans*x%md;
		x=x*x%md;
	}
	return ans;
}
inline ll C(int n,int m){
	if(m>n||m<0)return 0;
	return fac[n]*ifac[m]%md*ifac[n-m]%md;
}
void init(int n){
	fac[0]=1;
	rep(i,1,n)fac[i]=fac[i-1]*i%md;
	ifac[n]=power(fac[n],md-2);
	drep(i,n,1)ifac[i-1]=ifac[i]*i%md;
}
signed main(){
	scanf("%d%lld%lld%lld",&n,&a,&b,&c),xi=power(b-1,md-2);
	p1[0]=p2[0]=1;
	rep(i,1,n){
		p1[i]=p1[i-1]*a%md;
		p2[i]=p2[i-1]*b%md;
	}
	init(n<<1);
	rep(i,1,n)scanf("%lld",&d1[i]);
	rep(i,1,n)scanf("%lld",&d2[i]);
	rep(i,2,n){
		ans=(ans+C(n*2-i-2,n-2)*p1[n-1]%md*p2[n-i]%md*d1[i])%md;
		ans=(ans+C(n*2-i-2,n-2)*p2[n-1]%md*p1[n-i]%md*d2[i])%md;
	}
	if(b==1){
		rep(i,0,n-2)ans=(ans+c*p1[i]%md*C(i+n-1,i+1))%md;
	}else{
		rep(i,0,n-2)f[0]=(f[0]+p2[i])%md;
		rept(i,0,n-2)f[i+1]=(C(i+n-1,n-2)*p2[n-1]-f[i])%md*xi%md;
		rep(i,0,n-2)ans=(ans+c*p1[i]%md*f[i])%md;
	}
	cout<<ans;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...