用户工具

站点工具


2020-2021:teams:legal_string:组队训练比赛记录:contest17

这是本文档旧的修订版!


比赛链接

补题情况

题目 蒋贤蒙 王赵安 王智彪
C 0 0 0
D 0 0 0
E 2 0 0
H 2 0 0
J 0 0 0
M 0 0 0

题解

E. Easy Math Problem

题意

$$ \sum_{i=1}^n\sum_{j=1}^n {i+j\choose j}f(i,j)\\ f(i,j)= \begin{cases} 0, &i=0\\ a, &i=1\\ b\times f(i-1,j)+c\times f(i-2,j), &2\le i\le j\\ d\times f(i-1,j)+e\times f(i-2,j), &i\gt j \end{cases} $$

题解

$$ A=\begin{pmatrix}b & 1 \\ c & 0\\ \end{pmatrix},B=\begin{pmatrix}d & 1 \\ e & 0\\ \end{pmatrix} $$

不难发现

$$ (f(i+j,j),f(i+j-1,j))=(a,0)A^{i-1}B^j $$

设 $S(i)=\sum_{j=1}^n {i+j\choose j}A^{i-1}B^j$,于是有

$$ \begin{equation}\begin{split} S(i+1)&=\sum_{j=1}^n {i+j+1\choose j}A^iB^j \\ &=\sum_{j=1}^n \left({i+j\choose j}+{i+j\choose j+1}\right)A^iB^j\\ &=AS(i)+\sum_{j=0}^{n-1}{i+j\choose j}A^{i-1}B^jB\\ & =AS(i)+\left(S(i+1)+A^i-{i+n+1\choose i+1}A^iB^n\right)B \end{split}\end{equation} $$ 移项,得 $$ S(i+1)=\left(AS(i)+A^iB-{i+n+1\choose i+1}A^iB^{n+1}\right)(E-B)^{-1} $$

不难发现 $|E-B|=1-d-e\lt 0$,所以 $(E-B)$ 可逆。通过预处理上式可实现 $O(n)$ 递推。

查看代码

查看代码

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 frac[MAXN<<1],invf[MAXN<<1];
int C(int n,int m){
	return 1LL*frac[n]*invf[m]%mod*invf[n-m]%mod;
}
void Init(){
	int n=MAXN<<1;
	frac[0]=1;
	_for(i,1,n)
	frac[i]=1LL*frac[i-1]*i%mod;
	invf[n-1]=quick_pow(frac[n-1],mod-2);
	for(int i=n-1;i;i--)
	invf[i-1]=1LL*invf[i]*i%mod;
}
struct Matrix{
	int a[2][2];
	Matrix(int a00=0,int a01=0,int a10=0,int a11=0){
		a[0][0]=a00;
		a[0][1]=a01;
		a[1][0]=a10;
		a[1][1]=a11;
	}
	Matrix operator * (const Matrix &b)const{
		Matrix c;
		_for(i,0,2)_for(j,0,2)
		c.a[i][j]=(1LL*a[i][0]*b.a[0][j]+1LL*a[i][1]*b.a[1][j])%mod;
		return c;
	}
	Matrix operator * (const int b)const{
		Matrix c;
		_for(i,0,2)_for(j,0,2)
		c.a[i][j]=1LL*a[i][j]*b%mod;
		return c;
	}
	Matrix operator + (const Matrix &b)const{
		Matrix c;
		_for(i,0,2)_for(j,0,2)
		c.a[i][j]=(a[i][j]+b.a[i][j])%mod;
		return c;
	}
	Matrix operator - (const Matrix &b)const{
		Matrix c;
		_for(i,0,2)_for(j,0,2)
		c.a[i][j]=(a[i][j]+mod-b.a[i][j])%mod;
		return c;
	}
}A[MAXN],B[MAXN],f[MAXN];
Matrix Inv(Matrix mat){
	static int temp[2][4];
	_for(i,0,2)_for(j,0,2)
	temp[i][j]=mat.a[i][j];
	temp[0][2]=1,temp[0][3]=0;
	temp[1][2]=0,temp[1][3]=1;
	_for(i,0,2){
		int pos=-1;
		_for(j,i,2){
			if(temp[j][i]){
				pos=j;
				break;
			}
		}
		if(pos!=i)swap(temp[i],temp[pos]);
		for(int j=3;j>=i;j--)
		temp[i][j]=1LL*temp[i][j]*quick_pow(temp[i][i],mod-2)%mod;
		_for(j,0,2){
			if(j==i)continue;
			for(int k=3;k>=i;k--)
			temp[j][k]=(temp[j][k]-1LL*temp[j][i]*temp[i][k])%mod;
		}
	}
	Matrix ans;
	_for(i,0,2)_for(j,0,2)
	ans.a[i][j]=(temp[i][j+2]+mod)%mod;
	return ans;
}
void solve(){
	int n=read_int(),a=read_int(),b=read_int(),c=read_int(),d=read_int(),e=read_int();
	A[0]=B[0]=Matrix(1,0,0,1);
	A[1]=Matrix(b,1,c,0);
	B[1]=Matrix(d,1,e,0);
	_rep(i,1,n){
		A[i+1]=A[i]*A[1];
		B[i+1]=B[i]*B[1];
	}
	Matrix div=Inv(B[0]-B[1]);
	f[1]=Matrix();
	_rep(i,1,n)
	f[1]=f[1]+B[i]*(i+1);
	_for(i,1,n)
	f[i+1]=(A[1]*f[i]-A[i]*B[n+1]*C(i+n+1,i+1)+A[i]*B[1])*div;
	Matrix ans=Matrix();
	_rep(i,1,n)
	ans=ans+f[i];
	enter(1LL*ans.a[0][0]*a%mod);
}
int main(){
	Init();
	int T=read_int();
	while(T--)
	solve();
	return 0;
}
2020-2021/teams/legal_string/组队训练比赛记录/contest17.1630330525.txt.gz · 最后更改: 2021/08/30 21:35 由 jxm2001