P4828 Nagisa loves Tomoya题解

· · 题解

题目大意

给出一个序列，序列的长度为 n，定义一次操作为将所有的 a_i 变成 a_i + a_{(i \bmod n + {1})}，再给出两个数 x 和 y，求 x 次操作后 a_y 是多少。

思路分析

看到这种题，不妨模拟一下。

假设 n = 3，输入了三个数，分别是 a_1 到 a_3。

简单点来说，每个数都赋值为自己和下一个数的和，最后一个数赋值为自己和第一个数的和，所以得出下面的三组数。

     a1             a2           a3
   a1+a2          a2+a3         a3+a1
 a1+2a2+a3      a2+2a3+a1      a3+2a1+a2
a1+3a2+3a3+a1  a2+3a3+3a1+a2  a3+3a1+3a2+a3
   ......         ......         ......

我们再选一组调查。

     a1
   a1+a2   
 a1+2a2+a3      
a1+3a2+3a3+a1

把系数拎出来。

      1
    1   1
   1  2  1
  1  3  3  1

这就是杨辉三角，其它两组也是杨辉三角。

     a1  //操作0次后 
   a1+a2   //操作1次后 
 a1+2a2+a3   //操作2次后 
a1+3a2+3a3+a1   //操作3次后

我们为了让上面的数的层数与操作次数挂上关系，把层数从 0 一直编号到 3，于是问题从求 x 次操作后 a_y 的值变成了求上面数据的第 x 层的每个数的和。

系数有杨辉三角记录，那其余数呢？

我们把上面的数据的最后一行去掉系数后的序列拎出来，a1+a2+a3+a1，再把 a 也给省了，只剩下下标 1 2 3 1，我们发现下标是连续的，到 n 后再回到 1 开始循环。

我们只需要一个变量来记录 a 数组的下标就好了，但不用新开一个变量，因为每一层的第一个数等于塔尖的那个数，塔尖的数是我们要操作的数，那么 y 不就是塔尖那个数的下标？所以 y 也可以作为某一层第一个数的下标，往后计算的时候，不断把 y 加 1 就可以，特判一下是否到 n，如果到了，把 y 赋值为 1 即可。

操作步骤

下面上代码！

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=2005,M=1e6+5;
const int T=998244353;  
int n,q,ans=0;
int dp[N][N],a[M]; //用dp二维数组来构建杨辉三角 

inline int read(){  //快读优化 
    int x=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

void init(){   //构建杨辉三角 
    dp[0][0]=1; 
    for(int i=1;i<=N;++i){
        dp[i][0]=1; //每一层的第0列为1 
        for(int j=1;j<=N;++j){
            dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%T;//把它加上上面的数与左上角的数 
        }
    }
}

signed main(){
    init(); //初始化一下 
    n=read();
    for(int i=1;i<=n;++i)a[i]=read();
    q=read();
    while(q--){
        int x,y;
        x=read(),y=read();
        for(int i=0;i<=x;++i){  //枚举杨辉三角第x层的每一列 
            ans+=(dp[x][i]*a[y])%T; //dp[x][i]代表第x层第i个系数，把它与a[y]相乘的积模上T再加进答案 
            ans%=T;  //自己模一次，不加这个的话，就会喜获10分 
            if(y==n)y=1;    //如果已经到头了，就回到第一个数 
            else ++y;   //否则继续往下 
        }
        cout<<ans<<"\n"; //输出 
        ans=0;  //清零很重要 
    }
    return 0;
}

最后，求管理员通过！