HDU 5084 HeHe （找规律）

HeHe

Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 311 Accepted Submission(s): 116

Problem Description

You are expected to write a program to point out some elements of

M∗M.

Input

Multi test cases (about 100), every case occupies two lines.
The first line contains an integer n.
Then second line contain 2*n-1 integers

t0,t1,t2,t3,…,t2∗n−4,t2∗n−3,t2∗n−2 separated by exact one space.
The third line contains an integer m, indicates the number of query.
Next m lines will give queries

r0r1r2⋮rm−1c0c1c2⋮cm−1
For

r0,c0 the program will query the element of

M∗M which locates in the

rth0 row,

cth0 column. For

ri,ci(0<i<m), assume that the answer of

i−1th query is ANS, the program will query the element of

M∗M which locates in

((ri+ANS)%n)th row,

((ci+ANS)%n)th column.
Please process to the end of file.
[Technical Specification]

1≤n≤1000

0≤ti≤100

0≤ri,ci≤n−1

1≤m≤100000

Output

For each case，output the sum of the answer of each query.

Sample Input

3
1 2 3 1 2
2
0 0
1 2
4
10 5 7 2 10 5 7
3
1 2
3 0
2 1
2
1 2 3
4
0 0
0 1
1 0
1 1

Sample Output

23
348
22

Hint

Source

BestCoder Round #15

题目大意：给出一个矩阵M里元素的值t[0]，t[1]，t[2]，……，t[n-1]，t[n]，t[n+1]，……，t[2*n-1]，t[2*n-2]。

求出S=M*M，给出m对r[i]，c[i]，

当i = 0时，得到S[ r[0] ][ c[0] ]；

当i = 1时，ans=S[ r[0] ][ c[0] ]，得到S[ (r[1]+ans)%n ][ (c[1]+ans)%n ]；

当i = 2时，ans=S[ (r[1]+ans)%n ][ (c[1]+ans)%n ]，得到S[ (r[2]+ans)%n ][ (c[2]+ans)%n ]；

……………………………………………………………………

当 i = m-1时，ans=S[ (r[m-2]+ans)%n ][ (c[m-2]+ans)%n ]，得到S[ (r[m-1]+ans)%n ][ (c[m-1]+ans)%n ]。

求S[ r[0] ][ c[0] ]+S[ (r[1]+ans)%n ][ (c[1]+ans)%n ]+……+S[ (r[m-2]+ans)%n ][ (c[m-2]+ans)%n ]+S[ (r[m-1]+ans)%n ][ (c[m-1]+ans)%n ]。

解题思路：

1、矩阵S=M*M的所有元素值都求出后，做m次操作。

对于矩阵M，我们假设行列的下标均是从0开始的，则行列的下标均是由n-1结束的，如果对矩阵M和矩阵S，都以矩阵M中元素的下标为下标，如上图中红黄线所画，每一个t都有一个下标，即以该下标为矩阵M和矩阵S的下标。那么对于矩阵M，有M[n-1][n-1]=t[n-1]，M[0][2*n-2]=t[n-1]，……

对于矩阵S=M*M，我们有

S[0][2*n-2]=t[0]*t[2*n-2] +t[1]*t[2*n-3]+t[2]*t[2*n-4]+……+t[n-2]*t[n]+t[n-1]*t[n-1]；

S[1][2*n-3]= t[1]*t[2*n-3]+t[2]*t[2*n-4]+……+t[n-2]*t[n]+t[n-1]*t[n-1] + t[n]*t[n-2]；

S[2][2*n-4]= t[2]*t[2*n-4]+……+t[n-2]*t[n]+t[n-1]*t[n-1] + t[n]*t[n-2] + t[n+1]*t[n-3]；

………………………………………………………………

S[n-1][n-1]=

根据上面的式子，知道S[0][2*n-2]，就可以快速求出S[1][2*n-3]；知道S[1][2*n-3]，就可以快速求出S[2][2*n-4]……因此知道矩阵S的一个元素值，可以快速求出矩阵S的n个元素值。

代码如下：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <fstream>
#include <limits.h>
#define debug "output for debug\n"
#define pi (acos(-1.0))
#define eps (1e-6)
#define inf (1<<28)
#define sqr(x) (x) * (x)
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
#define MAX 1005
//
ll t[2*MAX],S[2*MAX][2*MAX];
//标记矩阵S[i][j]的值是否已经求出
bool vis[2*MAX][2*MAX];

int main()
{
    int i,j,n,m,r,c;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<=2*n-2;i++)
            scanf("%I64d",&t[i]);

        memset(vis,false,sizeof(vis));
        //计算矩阵S=M*M中元素的值
        for(i=0;i<=n-1;i++)
        {
            for(j=2*n-2;j>=n-1;j--)
            {
                //已经计算过的不必重复计算
                if(vis[i][j])
                    continue;

                ll ans=0;
                int k1=i,k2=j,k3=n;
                //计算第一个元素的值
                while(k3--)
                    ans+=t[k1++]*t[k2--];
                S[i][j]=ans;
                vis[i][j]=true;//标记

                k1=i+1;
                k2=j-1;
                //计算剩余的n-1个
                while(k1<=n-1&&k2>=n-1)
                {
                    ans=ans-t[k1-1]*t[k2+1]+t[k1+n-1]*t[k2-n+1];
                    S[k1][k2]=ans;
                    vis[k1][k2]=true;//标记
                    k1++;
                    k2--;
                }
            }
        }
        scanf("%d",&m);
        ll sum=0,ans=0;
        //矩阵S的m个位置元素的和
        while(m--)
        {
            scanf("%d%d",&r,&c);
            ans=S[(n-1)-(r+ans)%n][(n-1)+(c+ans)%n];
            sum+=ans;
        }
        printf("%I64d\n",sum);
    }
    return 0;
}

2、矩阵S=M*M的所有元素值不一定全求出来，只是求用得到的值。

如果S=M*M，那么S[x][y]=(矩阵M的第n-1-x行的元素值)*(矩阵M的第n-1+y列的元素值)。

列式表示为：

S[x][y]=t[(n-1-x)]*t[(n-1+y)]+t[(n-1-x)+1]*t[(n-1+y)-1]+……+t[(n-1-x)+(n-2)][(n-1+y)-(n-2)]+t[2*n-2-x][y]

代码如下：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <fstream>
#include <limits.h>
#define debug "output for debug\n"
#define pi (acos(-1.0))
#define eps (1e-6)
#define inf (1<<28)
#define sqr(x) (x) * (x)
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
#define MAX 1005
int n,m,t[2*MAX];
int ans(int x,int y)
{
    int s=0,i,j,k;
    i=n-1-x;
    j=n-1+y;
    for(k=0;k<n;k++)
    {
        s+=t[i]*t[j];
        i++;
        j--;
    }
    return s;
}
int main()
{
    int i,r,c;
    while(~scanf("%d",&n))
    {
        for(i=0;i<=2*n-2;i++)
            scanf("%d",&t[i]);
        ll cnt=0,s=0;
        scanf("%d",&m);
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&r,&c);
            s=ans((r+s)%n,(c+s)%n);
            cnt+=s;
        }
        printf("%I64d\n",cnt);
    }
    return 0;
}

HDU 5084 HeHe （觅规律）

HeHe

相关推荐