Description

Input

Output

Sample Input

输入样例一

5 4 1 1 3 5
1 0 0 0
5 2
3 1
1 2
2 3
4 3

输入样例二

10 5 233 2333 6 4
9 3 1 0 10
1 5
10 2
5 3
8 1

Sample Output

输出样例一

2
1
998244351
1
0

输出样例二

110343631
118211750
770559638
488601

Data Constraint

Solution

• 首先，知道了第 p 行，我们就可以向上向下推出其它的数。

• 接着我们可以找找规律，考虑用第 p 行的数表示出其它数（一个N元多项式）。

• 又可以发现它们的形式就像二项式展开一样：a 的几次方乘b 的几次方乘一个系数。

• 而系数就是杨辉三角中的组合数系数，向上向下推都同理。

• 那么 O(M) 预处理出阶乘和逆元，在每次询问时 O(N) 计算多项式的值即可。

• 总时间复杂度 O(M+NQ) 。

Code

#include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int N=1e5+5,M=1e7+5,mo=998244353; int f[M+N],g[M+N],c[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline int min(int x,int y) {return x<y?x:y; } inline int ksm(int x,int y) {int s=1;while(y){if(y&1) s=(LL)s*x%mo;x=(LL)x*x%mo;y>>=1;}return s; } inline int C(int x,int y) {return (LL)f[x]*g[y]%mo*g[x-y]%mo; } int main() {int m=read(),n=read(),a=read(),b=read(),p=read(),q=read();for(int i=1;i<=n;i++) c[i]=read();f[0]=g[0]=1;for(int i=1;i<=m+n;i++) f[i]=(LL)f[i-1]*i%mo;g[m+n]=ksm(f[m+n],mo-2);for(int i=m+n-1;i;i--) g[i]=(LL)g[i+1]*(i+1)%mo;int aa=ksm(a,mo-2);while(q--){int x=read(),y=read();if(x==p) printf("%d\n",c[y]); elseif(x>p){int num=x-p,a1=ksm(a,num),b1=1;int cnt=min(y,num+1),sum=0;for(int i=0,yy=y;i<=cnt;i++,yy--){sum=(sum+(LL)C(num,i)*a1%mo*b1%mo*c[yy]%mo)%mo;a1=(LL)a1*aa%mo;b1=(LL)b1*b%mo;}printf("%d\n",sum);}else{int num=p-x,a1=ksm(aa,num),b1=1;int sum=0,ff=1;for(int i=0,yy=y;i<y;i++,yy--){sum=(sum+(LL)C(num+i-1,i)*a1%mo*b1%mo*c[yy]%mo*ff%mo)%mo;a1=(LL)a1*aa%mo;b1=(LL)b1*b%mo;ff=mo-ff;}printf("%d\n",sum);}}return 0; }

总结

以上是生活随笔为你收集整理的JZOJ 5622. 【NOI2018模拟4.2】table的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。