盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 5084 HeHe(矩阵+强行找规律)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5084

题意

给定一个矩阵,矩阵的形式如下:
M = |tn, tn+1, …, t2n-1|
|tn-1, tn, …, t2
n-2|
|. |
|t1, t2, …, tn |
有Q组询问,每次询问A(x,y) 其中A = M * M

思路

由于n是1000级别的,所以常规的矩阵乘无法满足条件。
观察发现ans[x][y]就是 a[y]a[2n-x] + …. + a[y+n-1]a[n-x+1] 乘的这部分 a[i]a[j] i+j是定值 所以 对于i+j等于某个数的,求个前缀和 最后每个值就O(1)得到了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define debug puts("=====================");
typedef long long ll;
using namespace std;
const int N = 1010;
ll t[2 * N], f[3 * N][2 * N];
int n;
void init() {
for (int i = n + 1; i <= 3 * n - 1; i++) {
f[i][0] = 0;
for (int j = 1; j < 2 * n; j++) {
if (i > j && (i - j) <= 2 * n - 1) f[i][j] = t[j] * t[i - j] + f[i][j - 1];
}
}
}
int main () {
while(~scanf("%d", &n)) {
for (int i = 1; i < 2 * n; i++) scanf("%d", t + i);
init();
ll ans = 0, ret = 0;
int r, c, m;
scanf("%d", &m);
while(m--) {
scanf("%d%d", &r, &c);
r = (r + ret) % n + 1;
c = (c + ret) % n + 1;
ret = f[2 * n - r + c][2 * n - r] - f[2 * n - r + c][n - r];
ans += ret;
}
printf("%I64d\n", ans);
}
return 0;
}