题解

题意整理：

基本题意

​ 给出一个 $n\times nn\backslash times\; n$n×n 的棋盘，上面标有数字 $1,2,...,n\times n1,2,...,n\backslash times\; n$1,2,...,n×n ，并且给出了标数字的规则：左上角为 $11$1 ，然后向右方向标号 $2,\mathrm{3...}2,3...$2,3... 遇到边界或已经编号的格子时停下，转为方向向下……整体呈顺时针螺旋由外向内。

​ 现在给出棋子行走的规则：棋子最开始从 $11$1 出发。每次掷骰子行走 $x(1\le x\le 6)x(1\backslash le\; x\backslash le\; 6)$x(1≤x≤6) 步。如果当前在位置 $yy$y ，那么会走到数字 $x+yx+y$x+y 的位置上，如果棋子走到了 $n\times nn\backslash times\; n$n×n ，那么走的下一步就会回到 $11$1 。

​ 然后给出计分规则：如果掷骰子行走 $x(1\le x\le 6)x(1\backslash le\; x\backslash le\; 6)$x(1≤x≤6) 步，那么假设走完后棋子落在第 $ii$i 行第 $jj$j 列，那么这时将获得一定区域的数字和作为分数。具体来说，对于任意一个位于第 $uu$u 行第 $vv$v 列的数字，如果 ∣u−i∣<x 或 ∣v−j∣<x ，则将该数字计入得分。

​ 现在给出长度不超过 $mm$m 的数组 $q_{i}q\_i$qi​ 表示依次掷骰子的结果，输出每次移动后获得的累计得分。得分对 $10000000071000000007$1000000007 取模。

数据范围与性质

​ $1\le n\le 2000,1\le m\le 10^{5}1\backslash le\; n\; \backslash le\; 2000,\; 1\backslash le\; m\; \backslash le\; 10^5$1≤n≤2000,1≤m≤105 。

​ $1\le q_i\le 61\backslash le\; q\_i\; \backslash le\; 6$1≤qi​≤6

对棋盘的初步处理：

​ 无论是下面的哪种方法，都需要先对棋盘做处理，让我们知道下面几步能走到哪里。最好能在数字 $1,2,...,n\times n1,2,...,n\backslash times\; n$1,2,...,n×n 和格子坐标 $(1,1),(1,2),...,(n,n)(1,1),(1,2),...,(n,n)$(1,1),(1,2),...,(n,n) 之间建立双射。

​ 我们令 $f(i,j)f(i,j)$f(i,j) 表示第 $ii$i 行第 $jj$j 列的数字。

​ 令 $loc\left(a\right)loc(a)$loc(a) 表示数字 $aa$a 所在行列号的二元组。

​

​ 考虑一个模拟算法，求出所有的 $f(i,j)f(i,j)$f(i,j) 和 $loc\left(a\right)loc(a)$loc(a) 。

• 刚开始，令所有的 $f(i,j)=0f(i,j)=0$f(i,j)=0 ，然后 $f(1,1)=1,loc\left(1\right)=(1,1)f(1,1)=1,loc(1)=(1,1)$f(1,1)=1,loc(1)=(1,1) 。令 $a=1a=1$a=1 表示当前处理的数字，$b=(1,1)b=(1,1)$b=(1,1) 表示当前的位置。然后令方向 $dir=\text{RIGHT}dir=\backslash text\{RIGHT\}$dir=RIGHT 。表示此时向右走。
• 考察向当前 $dirdir$dir 所表示的方向走一步的位置 $b^{\prime }b^\backslash prime$b′ ，如果 $f\left(b^{\prime }\right)f(b^\backslash prime)$f(b′) 已经不为 $00$0 或者 $b^{\prime }b^\backslash prime$b′ 已经在棋盘外了，则调整方向 $dirdir$dir ，重新求出 $b^{\prime }b^\backslash prime$b′。（具体的方向调整方法：$\text{RIGHT -> DOWN}\backslash text\{RIGHT\; ->\; DOWN\}$RIGHT -> DOWN，$\text{DOWN -> LEFT}\backslash text\{DOWN\; ->\; LEFT\}$DOWN -> LEFT，$\text{LEFT -> UP}\backslash text\{LEFT\; ->\; UP\}$LEFT -> UP，$\text{UP -> RIGHT}\backslash text\{UP\; ->\; RIGHT\}$UP -> RIGHT）
• 如果 $a=n\times na=n\backslash times\; n$a=n×n 了，结束算法。否则令 $a^{\prime }=a+1a^\backslash prime\; =a+1$a′=a+1 ，记录 $loc\left(a^{\prime }\right)=b^{\prime },f\left(b^{\prime }\right)=a^{\prime }loc(a^\backslash prime)=b^\backslash prime,f(b^\backslash prime)=a^\backslash prime$loc(a′)=b′,f(b′)=a′ 。然后再把 $a,ba,b$a,b 用 $a^{\prime },b^{\prime }a^\backslash prime\; ,b^\backslash prime$a′,b′ 覆盖，回到上一步骤。直到算法结束。

​ 其实这个算法就是在模拟顺时针螺旋向内的过程（图1）。

​ 代码：

		static const int MAXN=2001;//棋盘边长最大范围
    static const int MAXM=100001;//询问最大长度
    static const int Right=0,Down=1,Left=2,Up=3;
    int f[MAXN][MAXN];//位置上的数字
    pair<int,int> loc[MAXN*MAXN];//数字对应的位置
    
    inline void turn_dir(int &dir)//顺时针旋转一次方向
    {
        dir=(dir+1)%4;
    }
    
    inline bool in_board(pair<int,int> x,int n)//位置是否在棋盘内
    {
        return 1<=x.first&&x.first<=n&&1<=x.second&&x.second<=n;
    }
    
    inline bool one_move(pair<int,int> &x,int dir,int n)//向dir方向前进一步，并且判断是否是合法位置
    {
        if(dir==Right)x.second+=1;
        else if(dir==Down)x.first+=1;
        else if(dir==Left)x.second-=1;
        else x.first-=1;
        
        //判断是否越界，或者位置已经求出。没有的话返回真。
        return in_board(x,n) && !f[x.first][x.second];
    }
    
    void init_board(int n)
    {
        memset(f,0,sizeof(f));
        int a=1;
        pair<int,int> b=make_pair(1,1);
        int dir = Right; //初始化
        
        while(a<=n*n)
        {
            f[b.first][b.second]=a;//处理当前位置的值
            loc[a]=b;
            
            pair<int,int> next_b = b;
            if(!one_move(next_b,dir,n))//判断下一步是否合法
            {
                turn_dir(dir);//不合法的情况调整方向重新走一次。
                next_b = b;
                one_move(next_b,dir,n);
            }
            b=next_b;//移动到下一个位置
            a++;
        }
    }

​ 此部分的复杂度分析：用到的数组 $f,locf,loc$f,loc 空间都是 $O\left(n^2\right)O(n^2)$O(n2) 的，空间复杂度 $O\left(n^2\right)O(n^2)$O(n2) ，因为每个格子有且仅访问了一次，时间复杂度 $O\left(n^2\right)O(n^2)$O(n2) 。

解法1：暴力算分求和

【知识点】模拟，循环，枚举，判断

分析与算法描述

​ 当棋盘确定了，我们只需要根据每次骰子的结果模拟并计算分数即可。

​ 加入当前棋子在数字 $kk$k ，然后骰子的值是 $xx$x ，那么我们直接可以得到下一步的棋子位置的二元组是 $loc(k+x)loc(k+x)$loc(k+x) 。不妨令其为 $(u,v)(u,v)$(u,v) 。我们可以将算分部分写成一个函数，和模拟过程分离开。

​ 那么我们的算分函数要做的事：给出一个 $(u,v,x)(u,v,x)$(u,v,x) 的三元组，计算所有 $1\le i,j\le n1\backslash le\; i,j\backslash le\; n$1≤i,j≤n 中满足 ∣i−u∣<x 或 ∣j−v∣<x 的 $f(i,j)f(i,j)$f(i,j) 的和（图 2 深***域）。我们可以把满足条件的范围看成 $33$3 个部分的运算结果。

1. 左上角为 $(\max (u-x+1,1),1)\backslash big(\backslash max(u-x+1,1),1\backslash big)$(max(u−x+1,1),1) ，右下角为 $(\min (u+x-1,n),n)\backslash big(\backslash min(u+x-1,n),n\backslash big)$(min(u+x−1,n),n) 的矩形区域（图3 - S1）。

2. 左上角为 $(1,\max (v-x+1,1\left)\right)\backslash big(1,\backslash max(v-x+1,1)\backslash big)$(1,max(v−x+1,1)) ，右下角为 $(n,\min (v+x-1,n\left)\right)\backslash big(n,\backslash min(v+x-1,n)\backslash big)$(n,min(v+x−1,n)) 的矩形区域（图3 - S2）。

3. 左上角为 $(\max (u-x+1,1),\max (v-x+1,1\left)\right)\backslash big(\backslash max(u-x+1,1),\backslash max(v-x+1,1)\backslash big)$(max(u−x+1,1),max(v−x+1,1)) ，右下角为 $(\min (u+x-1,n),\min (v+x-1,n\left)\right)\backslash big(\backslash min(u+x-1,n),\backslash min(v+x-1,n)\backslash big)$(min(u+x−1,n),min(v+x−1,n)) 的矩形区域（图3 - S3）。

于是我们的答案就是把区域2的数字和加上区域1的数字和，再减去区域3的数字和。

​ 我们可以采用枚举法求解矩形内数字的和。

参考代码（配合上处理棋盘的代码才完整）

		int sum(pair<int,int> lu,pair<int,int> rd)//矩形范围求和
    {
        int ret=0;
        for(int i=lu.first;i<=rd.first;i++)//暴力枚举即可
            for(int j=lu.second;j<=rd.second;j++)
                ret=(ret+f[i][j])%MOD;
        return ret;
    }
    
    int Query(pair<int,int> loc,int x,int n)//查询位置loc上，骰子为x时的区间答案
    {
        int ret=0;
        pair<int,int> lu_1 = make_pair( max(1,loc.first - x + 1) , 1 );//处理出三块区域的左上角和右下角
        pair<int,int> rd_1 = make_pair( min(n,loc.first + x - 1) , n );
        pair<int,int> lu_2 = make_pair( 1 , max(1,loc.second - x + 1) );
        pair<int,int> rd_2 = make_pair( n , min(n,loc.second + x - 1) );
        pair<int,int> lu_3 = make_pair( max(1,loc.first - x + 1) , max(1,loc.second - x + 1) );
        pair<int,int> rd_3 = make_pair( min(n,loc.first + x - 1) , min(n,loc.second + x - 1) );
        return ( ( sum(lu_1,rd_1) + sum(lu_2,rd_2) )%MOD + MOD - sum(lu_3,rd_3) )%MOD;//区域1+区域2-区域3，考虑取模
    }
    
    vector<int> getScores(int n, vector<int>& query) {
        // write code here
        vector<int> ans;
        init_board(n);
        int now=1;//当前的位置
        int sum_score=0;//累计分数
        for(auto &x: query)
        {
            now=now+x;//走这步
            while(now>n*n)
                now-=n*n;
            sum_score=(sum_score+Query(loc[now], x, n))%MOD;//计算分数
            ans.push_back(sum_score);//保存答案
        }
        
        return ans;
    }

复杂度分析

​ 求取一次矩形范围的数字和，由于矩形范围的宽度是 $O\left(x\right)O(x)$O(x) ，长最大是 $O\left(n\right)O(n)$O(n) 的，（$xx$x 是骰子的结果，最大是 $66$6 ）因此时间复杂度是 $O\left(6n\right)O(6n)$O(6n) 。一共掷 $mm$m 次骰子，并结合处理棋盘的复杂度，因此总时间复杂度是 $O(n^2+6nm)O(n^2+6nm)$O(n2+6nm) 会 $\text{TLE}\backslash text\{TLE\}$TLE 。

​ 空间复杂度主要来自于预处理棋盘和储存答案，是 $O(n^2+m)O(n^2+m)$O(n2+m) 。

解法2：前缀和优化

【知识点】二维前缀和

​

分析与算法描述

​ 上面的算法瓶颈在于每次求取二维区间和的复杂度是 $O\left(6n\right)O(6n)$O(6n) 。因为每次求二维区间和都是遍历每个位置求取的。

​ 如果采用二维前缀和的计算方法，可以做到 $O\left(n^2\right)O(n^2)$O(n2) 预处理，然后每次查询二维区间和的时间复杂度都是 $O\left(1\right)O(1)$O(1) 。

二维前缀和

​ 具体来讲，就是预处理出 $S(i,j),(1\le i,j\le n)S(i,j),\backslash \; (1\backslash le\; i,j\backslash le\; n)$S(i,j), (1≤i,j≤n) ，表示以 $(1,1)(1,1)$(1,1) 为左上角，$(i,j)(i,j)$(i,j) 为右下角的矩形区域的元素和，即 $S(i,j)={\sum }_{u=1}^i{\sum }_{v=1}^{j}f(u,v)S(i,j)=\backslash sum\_\{u=1\}^i\backslash sum\_\{v=1\}^\{j\}\; f(u,v)$S(i,j)=∑u=1i​∑v=1j​f(u,v) 。

​ 预处理的递推式如下：

​ 这是一个简单的容斥原理，如 图 4 所示。

​ 当所有内容预处理出来之后，我们需要查询左上角为 $(a,b)\backslash big(a,b)$(a,b) ，右下角为 $(c,d)\backslash big(c,d)$(c,d) 的矩形区域元素和时，同样根据容斥原理分析，答案值就应该是：

参考代码（配合上处理棋盘的代码才完整）

		int S[MAXN][MAXN];
    void init_sum(int n)//初始化二维前缀和数组
    {
        memset(S,0,sizeof(S));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                S[i][j]=((0ll + S[i-1][j] + S[i][j-1] - S[i-1][j-1] + f[i][j])%MOD+MOD)%MOD;//注意取模
    }
    int sum(pair<int,int> lu,pair<int,int> rd)//矩形范围求和
    {
        return ((0ll + S[rd.first][rd.second] - S[rd.first][lu.second-1] - S[lu.first-1][rd.second] + S[lu.first-1][lu.second-1])%MOD+MOD)%MOD;//直接用二维前缀和计算
    }
    
    int Query(pair<int,int> loc,int x,int n)//查询位置loc上，骰子为x时的区间答案
    {
        int ret=0;
        pair<int,int> lu_1 = make_pair( max(1,loc.first - x + 1) , 1 );//处理出三块区域的左上角和右下角
        pair<int,int> rd_1 = make_pair( min(n,loc.first + x - 1) , n );
        pair<int,int> lu_2 = make_pair( 1 , max(1,loc.second - x + 1) );
        pair<int,int> rd_2 = make_pair( n , min(n,loc.second + x - 1) );
        pair<int,int> lu_3 = make_pair( max(1,loc.first - x + 1) , max(1,loc.second - x + 1) );
        pair<int,int> rd_3 = make_pair( min(n,loc.first + x - 1) , min(n,loc.second + x - 1) );
        return ( ( sum(lu_1,rd_1) + sum(lu_2,rd_2) )%MOD + MOD - sum(lu_3,rd_3) )%MOD;//区域1+区域2-区域3，考虑取模
    }
    
    vector<int> getScores(int n, vector<int>& query) {
        // write code here
        vector<int> ans;
        init_board(n);
        init_sum(n);
        int now=1;//当前的位置
        int sum_score=0;//累计分数
        for(auto &x: query)
        {
            now=now+x;//走这步
            while(now>n*n)
                now-=n*n;
            sum_score=(sum_score+Query(loc[now], x, n))%MOD;//计算分数
            ans.push_back(sum_score);//保存答案
        }
        
        return ans;
    }

复杂度分析

​ 该算法的前缀和数组占用 $O\left(n^2\right)O(n^2)$O(n2) 的空间，需要 $O\left(n^2\right)O(n^2)$O(n2) 预处理前缀和数组，实现了 $O\left(1\right)O(1)$O(1) 查询，其余部分同方法一。因此该方法空间复杂度 $O(n^2+m)O(n^2+m)$O(n2+m) ，时间复杂度 $O(n^2+m)O(n^2+m)$O(n2+m) 。

​

​

完整代码

方法一（超时）

class Solution {
public:
    /**
     * 求每一步后的总分数，所有分数都对1,000,000,007取模
     * @param n int整型 棋盘大小
     * @param query int整型vector 每次掷出的点数的列表
     * @return int整型vector
     */
    
    static const int MAXN=2001;//棋盘边长最大范围
    static const int MAXM=100001;//询问最大长度
    static const int MOD=1000000007;
    static const int Right=0,Down=1,Left=2,Up=3;
    int f[MAXN][MAXN];//位置上的数字
    pair<int,int> loc[MAXN*MAXN];//数字对应的位置
    
    inline void turn_dir(int &dir)//顺时针旋转一次方向
    {
        dir=(dir+1)%4;
    }
    
    inline bool in_board(pair<int,int> x,int n)//位置是否在棋盘内
    {
        return 1<=x.first&&x.first<=n&&1<=x.second&&x.second<=n;
    }
    
    inline bool one_move(pair<int,int> &x,int dir,int n)//向dir方向前进一步，并且判断是否是合法位置
    {
        if(dir==Right)x.second+=1;
        else if(dir==Down)x.first+=1;
        else if(dir==Left)x.second-=1;
        else x.first-=1;
        
        //判断是否越界，或者位置已经求出。没有的话返回真。
        return in_board(x,n) && !f[x.first][x.second];
    }
    
    void init_board(int n)
    {
        memset(f,0,sizeof(f));
        int a=1;
        pair<int,int> b=make_pair(1,1);
        int dir = Right; //初始化
        
        while(a<=n*n)
        {
            f[b.first][b.second]=a;//处理当前位置的值
            loc[a]=b;
            
            pair<int,int> next_b = b;
            if(!one_move(next_b,dir,n))//判断下一步是否合法
            {
                turn_dir(dir);//不合法的情况调整方向重新走一次。
                next_b = b;
                one_move(next_b,dir,n);
            }
            b=next_b;//移动到下一个位置
            a++;
        }
    }
    
    int sum(pair<int,int> lu,pair<int,int> rd)//矩形范围求和
    {
        int ret=0;
        for(int i=lu.first;i<=rd.first;i++)//暴力枚举即可
            for(int j=lu.second;j<=rd.second;j++)
                ret=(ret+f[i][j])%MOD;
        return ret;
    }
    
    int Query(pair<int,int> loc,int x,int n)//查询位置loc上，骰子为x时的区间答案
    {
        int ret=0;
        pair<int,int> lu_1 = make_pair( max(1,loc.first - x + 1) , 1 );//处理出三块区域的左上角和右下角
        pair<int,int> rd_1 = make_pair( min(n,loc.first + x - 1) , n );
        pair<int,int> lu_2 = make_pair( 1 , max(1,loc.second - x + 1) );
        pair<int,int> rd_2 = make_pair( n , min(n,loc.second + x - 1) );
        pair<int,int> lu_3 = make_pair( max(1,loc.first - x + 1) , max(1,loc.second - x + 1) );
        pair<int,int> rd_3 = make_pair( min(n,loc.first + x - 1) , min(n,loc.second + x - 1) );
        return ( ( sum(lu_1,rd_1) + sum(lu_2,rd_2) )%MOD + MOD - sum(lu_3,rd_3) )%MOD;//区域1+区域2-区域3，考虑取模
    }
    
    vector<int> getScores(int n, vector<int>& query) {
        // write code here
        vector<int> ans;
        init_board(n);
        int now=1;//当前的位置
        int sum_score=0;//累计分数
        for(auto &x: query)
        {
            now=now+x;//走这步
            while(now>n*n)
                now-=n*n;
            sum_score=(sum_score+Query(loc[now], x, n))%MOD;//计算分数
            ans.push_back(sum_score);//保存答案
        }
        
        return ans;
    }
};

方法二

class Solution {
public:
    /**
     * 求每一步后的总分数，所有分数都对1,000,000,007取模
     * @param n int整型 棋盘大小
     * @param query int整型vector 每次掷出的点数的列表
     * @return int整型vector
     */
    
    static const int MAXN=2001;//棋盘边长最大范围
    static const int MAXM=100001;//询问最大长度
    static const int MOD=1000000007;
    static const int Right=0,Down=1,Left=2,Up=3;
    int f[MAXN][MAXN];//位置上的数字
    pair<int,int> loc[MAXN*MAXN];//数字对应的位置
    
    inline void turn_dir(int &dir)//顺时针旋转一次方向
    {
        dir=(dir+1)%4;
    }
    
    inline bool in_board(pair<int,int> x,int n)//位置是否在棋盘内
    {
        return 1<=x.first&&x.first<=n&&1<=x.second&&x.second<=n;
    }
    
    inline bool one_move(pair<int,int> &x,int dir,int n)//向dir方向前进一步，并且判断是否是合法位置
    {
        if(dir==Right)x.second+=1;
        else if(dir==Down)x.first+=1;
        else if(dir==Left)x.second-=1;
        else x.first-=1;
        
        //判断是否越界，或者位置已经求出。没有的话返回真。
        return in_board(x,n) && !f[x.first][x.second];
    }
    
    void init_board(int n)
    {
        memset(f,0,sizeof(f));
        int a=1;
        pair<int,int> b=make_pair(1,1);
        int dir = Right; //初始化
        
        while(a<=n*n)
        {
            f[b.first][b.second]=a;//处理当前位置的值
            loc[a]=b;
            
            pair<int,int> next_b = b;
            if(!one_move(next_b,dir,n))//判断下一步是否合法
            {
                turn_dir(dir);//不合法的情况调整方向重新走一次。
                next_b = b;
                one_move(next_b,dir,n);
            }
            b=next_b;//移动到下一个位置
            a++;
        }
    }
    
    int S[MAXN][MAXN];
    void init_sum(int n)
    {
        memset(S,0,sizeof(S));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                S[i][j]=((0ll + S[i-1][j] + S[i][j-1] - S[i-1][j-1] + f[i][j])%MOD+MOD)%MOD;
    }
    int sum(pair<int,int> lu,pair<int,int> rd)//矩形范围求和
    {
        return ((0ll + S[rd.first][rd.second] - S[rd.first][lu.second-1] - S[lu.first-1][rd.second] + S[lu.first-1][lu.second-1])%MOD+MOD)%MOD;
    }
    
    int Query(pair<int,int> loc,int x,int n)//查询位置loc上，骰子为x时的区间答案
    {
        int ret=0;
        pair<int,int> lu_1 = make_pair( max(1,loc.first - x + 1) , 1 );//处理出三块区域的左上角和右下角
        pair<int,int> rd_1 = make_pair( min(n,loc.first + x - 1) , n );
        pair<int,int> lu_2 = make_pair( 1 , max(1,loc.second - x + 1) );
        pair<int,int> rd_2 = make_pair( n , min(n,loc.second + x - 1) );
        pair<int,int> lu_3 = make_pair( max(1,loc.first - x + 1) , max(1,loc.second - x + 1) );
        pair<int,int> rd_3 = make_pair( min(n,loc.first + x - 1) , min(n,loc.second + x - 1) );
        return ( ( sum(lu_1,rd_1) + sum(lu_2,rd_2) )%MOD + MOD - sum(lu_3,rd_3) )%MOD;//区域1+区域2-区域3，考虑取模
    }
    
    vector<int> getScores(int n, vector<int>& query) {
        // write code here
        vector<int> ans;
        init_board(n);
        init_sum(n);
        int now=1;//当前的位置
        int sum_score=0;//累计分数
        for(auto &x: query)
        {
            now=now+x;//走这步
            while(now>n*n)
                now-=n*n;
            sum_score=(sum_score+Query(loc[now], x, n))%MOD;//计算分数
            ans.push_back(sum_score);//保存答案
        }
        
        return ans;
    }
};