Jzoj5622 table

p<=100

一道非常有意思的题目

如果将第一行看做一个多项式，那么每过一行就是乘上了一个(a+bx)

那么我们可以求出(a+bx)^p的逆,让后就可以求出第一行

当然也可以有简单做法

首先如果推下式子，很容易知道第p行到第x行的转移 (x>p)

f[x][y]=∑f[p][y-i]*a^(x-p-i)*b^i*C(x-p,i) (0<=i<=x-p)

那么我们考虑一下怎么用第p行推出p行上面的东西

我们可以向上走一步，等于乘上1/a，也可以向右走，等于乘上-b/a

那么类似的，我们可以推出向上走的式子

f[x][y]=∑f[p][i]*(-b)^(y-i)*C(y-i+p-x-1,p-x-1)/(a^(p-x+y-i)) (1<=i<=y)

预处理逆元和组合数，那么做一次就是O(n)，总复杂度O(np)可以通过

#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define LL long long
#define M 998244353
using namespace std;
int n,m,q,p,a,b,f[100010],ia,ib,ic;
LL js[11000010],inv[11000010],S=0;
inline LL C(int n,int m){ return js[n]*inv[m]%M*inv[n-m]%M; }
inline LL pow(LL x,LL k,LL s=1){
	for(;k;x=x*x%M,k>>=1) k&1?s=s*x%M:0;
	return s;
}
int main(){
	freopen("table.in","r",stdin);
	freopen("table.out","w",stdout);
	scanf("%d%d%d%d%d%d",&m,&n,&a,&b,&p,&q);
	for(int i=*js=1;i<=n;++i) scanf("%d",f+i);
	m+=n; ia=pow(a,M-2);
	for(int i=1;i<=m;++i) js[i]=js[i-1]*i%M;
	inv[m]=pow(js[m],M-2);
	for(int i=m;i;--i) inv[i-1]=inv[i]*i%M;
	m-=n; ib=pow(b,M-2); ic=pow(M-b,M-2);
	for(int x,y;q--;){ LL A,B;
		scanf("%d%d",&x,&y); S=0;
		if(x==p) S=f[y]; else
		if(x>p){
//			for(int i=0;i+p<=x&&y-i;++i)
//				S=(S+f[y-i]*pow(a,x-p-i)%M*pow(b,i)%M*C(x-p,i))%M;
			A=pow(a,x-p); B=1;
			for(int i=0;i+p<=x&&y-i;++i){
				S=(S+f[y-i]*A%M*B%M*C(x-p,i)%M)%M;
				A=A*ia%M; B=B*b%M;
			}
			
		} else {
//			for(int i=1;i<=y;++i)
//				S=(S+f[i]*pow(-b,y-i)%M*C(y-i+p-x-1,p-x-1)%M*pow(pow(a,p-x+y-i),M-2)%M+M)%M;
			B=pow(M-b,y-1);
			A=pow(pow(a,p-x+y-1),M-2);
			for(int i=1;i<=y;++i){
				S=(S+f[i]*A%M*C(y-i+p-x-1,p-x-1)%M*B%M+M)%M;
				A=A*a%M;
				B=B*ic%M;
			}
			
		}
		printf("%lld
",S);
	}
}