「dwjshift毒瘤模拟赛」table - 二项式定理

题目大意

    给出一个$m\times n$的数表：

$$\begin{cases}f_{i,1}=af_{i-1,1} \\ f_{i,j}=af_{i-1,j}+bf_{i-1,j-1} & (j\gt 1)\end{cases}$$

    给出第$p$行，还原任意位置的数值。

---

题目分析

草稿纸上算算递推过程，得出结果：
当$x\gt p$时：

$$f_{x,y}=\sum_{i=0}^{x-p}f_{p,y-i}a^{x-p-i}b^i\binom {x-p}{i}$$

$x\lt p$时怎么办呢？
对于$60$分，你可以$O(n^2)$暴力解出第一行的数，之后都变成询问下面了。
对于$100$分，算算往上递推的过程，得出结果：

$$f_{x,y}=\sum_{i=1}^y\frac{f_{p,i}(-b)^{y-i}\binom{y-i+p-x-1}{p-x-1}}{a^{p-x+y-i}}$$

时间复杂度$O(nq+m)$。

---

代码

#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int maxn=100005,maxm=10100005,mod=998244353;

int n,m,a,b,p,q;
int f[maxn],Powa[maxm],Powb[maxm],inv[maxm],inva[maxm];

int Down(int x,int y) {
	int ans=0,C=1;
	for(int i=0; i<=min(x-p,y-1); i++) {
		ans=(ans+1ll*f[y-i]*C%mod*Powa[x-p-i]%mod*Powb[i]%mod)%mod;
		C=1ll*C*(x-p-i)%mod*inv[i+1]%mod;
	}
	return ans;
}

int Up(int x,int y) {
	int ans=0,C=1;
	for(int i=y; i>=1; i--) {
		int t=(y-i)&1?mod-1:1;
		ans=(ans+1ll*t*Powb[y-i]%mod*inva[p-x+y-i]%mod*f[i]%mod*C%mod)%mod;
		C=1ll*C*(y-i+p-x)%mod*inv[y-i+1]%mod;
	}
	return ans;
}

int Quick_Pow(int a,int b) {
	int ans=1;
	for(; b; b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;
	return ans;
}

int main() {
	m=Get_Int();
	n=Get_Int();
	Powa[1]=Get_Int();
	Powb[1]=Get_Int();
	Powa[0]=Powb[0]=inv[0]=inv[1]=inva[0]=1;
	inva[1]=Quick_Pow(Powa[1],mod-2);
	for(int i=2; i<=n+m; i++) {
		Powa[i]=1ll*Powa[i-1]*Powa[1]%mod;
		Powb[i]=1ll*Powb[i-1]*Powb[1]%mod;
		inva[i]=1ll*inva[i-1]*inva[1]%mod;
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	}
	p=Get_Int();
	q=Get_Int();
	for(int i=1; i<=n; i++)f[i]=Get_Int();
	while(q--) {
		int x=Get_Int(),y=Get_Int();
		printf("%d\n",x==p?f[y]:(x>p?Down(x,y):Up(x,y)));
	}
	return 0;
}