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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。