10.23T1 杨辉三角

#3846 陷阱

描述

Jerryzhong 被 ljr 狠狠地嘲讽了一番，于是他想搞点事情。他制作了 n 个陷阱，每个陷阱的伤害值为 s[i]，这 n 个陷阱十分神奇，它们的伤害值能不断提高，由于不可抗力的原因，Jerryzhong 制作这 n 个陷阱时将它们连在了一起，所以它们是有序且伤害值是一起提升的。

Jerryzhong 总共能使陷阱提高 x 次伤害，他想知道提高伤害 x 次后陷阱 y 的伤害值 s[y]，由于 Jerryzhong 不会数数而且忙着追番，因此他将这个问题交给了身为 dalao 的你。

每提高一次伤害：将所有陷阱的伤害值 s[i]变为 s[i]+s[i%n+1]。

例如陷阱 1 7 4，提高一次伤害后变为 8 11 5，再提高一次伤害后变为 19 16 13

输入

第一行包含一个整数 n 表示陷阱个数。

接下来一行 n 个整数表示这 n 个陷阱的伤害值。

接下来一行一个整数 q 表示询问次数。

接下来 q 行，每行两个整数 x,y 意义如题所述

输出

~~如果你能做到则输出 yes，否则输出 no。~~

输出一共 q 行，表示每次询问的答案，由于答案可能很大，请对 998244353 取模。

样例输入[复制]

5
1 2 3 4 5
2
1 2
2 2

样例输出[复制]

5
12

提示

对于 30% 的数据，1<=n,x,q<=100。

对于 50% 的数据，1<=n<=100000,1<=x<=500,1<=q<=100。

对于 100% 的数据，1<=n<=1000000,1<=ai<=1e9,1<=x<=2000,1<=q<=10000。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string>
 4 #define N 1000006
 5 using namespace std;
 6 const long long mod=998244353;
 7 long long read() {
 8     long long x=0,f=1;
 9     char c=getchar();
10     while(!isdigit(c)) {
11         if(c=='-')f=-1;
12         c=getchar();
13     }
14     while(isdigit(c)) {
15         x=(x<<3)+(x<<1)+c-'0';
16         c=getchar();
17     }
18     return x*f;
19 }
20 long long n,sum;
21 long long a[N][2],b[N],fac[N],inv[N];
22 long long ksm(long long a,long long b) {
23     long long ans=1;
24     for(; b; b>>=1) {
25         if(b&1) {
26             ans*=a;
27             ans%=mod;
28         }
29         a*=a;
30         a%=mod;
31     }
32     return ans;
33 }
34 void pre() {
35     fac[0]=1;
36     for(long long i=1; i<=5000; i++)fac[i]=(fac[i-1]*i)%mod;
37     inv[5000]=ksm(fac[5000],mod-2);
38     for(long long i=4999; i>=0; i--)inv[i]=(inv[i+1]*(i+1))%mod;
39 }
40 long long C(long long m,long long n) {
41     return ((fac[m]*inv[n]%mod)*inv[m-n])%mod;
42 }
43 int c[N];
44 int main() {
45     freopen("trap.in","r",stdin);
46     freopen("trap.out","w",stdout);
47     n=read();
48     for(long long i=1; i<=n; i++)a[i][0]=read(),sum+=a[i][0];
49     long long q;
50     pre();
51     q=read();
52     for(long long i=1; i<=n; i++)b[i]=a[i][0];
53     if(n<=100) {
54         long long now=0;
55         while(q--) {
56             long long x,y;
57             x=read(),y=read();
58             now=0;
59             for(long long i=1; i<=x; i++) {
60                 for(long long j=1; j<=n; j++) {
61                     a[j][now^1]=a[j][now]+a[j%n+1][now];
62                     a[j][now^1]%=mod;
63                 }
64                 now^=1;
65             }
66             cout<<a[y][now]<<'
';
67             for(long long i=1; i<=n; i++)a[i][0]=b[i];
68         }
69         return 0;
70     }
71     //cout<<C(5,1)<<"---";
72     while(q--) {
73         int x,y;
74         x=read(),y=read();
75         long long ans=0;
76         for(int i=0; i<=x; i++) {
77             ans+=(C(x,i)*b[(y+i-1)%n+1])%mod;
78             ans%=mod;
79         }
80         cout<<ans<<'
';
81     }
82     return 0;
83 }

over