2015
02-22

# Recursive Sequence

Given two integers N and M, we define a recursive sequence g[i] (indexed from 0) as follows:
(1) If 0 <= i < M, then g[i] = a[i]
(2) If i >= M, then g[i] = b[0]*g[i-M] + b[1]*g[i-M+1] + … + b[M-1]*g[i-1]
Now your task is very simple: Try to find g[N] mod 1,000,000,003.

The first line of input is an integer T (1 <= T <= 10), which is the number of test cases. T cases follow.
For each case, the first line are two integers M(1 <= M <= 1000) and N(M <= N <= 1,000,000,000). Two lines followed, each of which contains exactly M integers. The first M integers are a[0], a[1], …, a[M-1], and the last M integers are b[0], b[1], …, b[M-1], where 0 <= a[i], b[i] < 1,000,000,003.

The first line of input is an integer T (1 <= T <= 10), which is the number of test cases. T cases follow.
For each case, the first line are two integers M(1 <= M <= 1000) and N(M <= N <= 1,000,000,000). Two lines followed, each of which contains exactly M integers. The first M integers are a[0], a[1], …, a[M-1], and the last M integers are b[0], b[1], …, b[M-1], where 0 <= a[i], b[i] < 1,000,000,003.

2

1 5
1
2

2 7
0 1
1 1

32
13

Hint
Sample #0: You can easily find that g[i] = 2^i, so g[5] = 32
Sample #1: g[i] is the i-th fibonacci number, so g[6] = 13

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#define MOD 1000000003
#define MAXN 2010
using namespace std;

using namespace std;

long long n, m, b[MAXN], e[MAXN] = {0}, zero[MAXN] = {0};//b为递推系数

struct poly {
long long a[MAXN];

poly(long long ta[]) {
for (int i = 0; i < 2 * m; i++) a[i] = ta[i];
}

poly operator*(const poly & po) {
poly re(zero);
for (int i = 0; i < m; i++) {
if (po.a[i])
for (int j = 0; j < m; j++) {
re.a[i + j] += a[j] * po.a[i];
re.a[i + j] %= MOD;
}
}
for (int i = 2 * m - 1; i >= m; i--) {
if (re.a[i])
for (int j = 0; j < m; j++) {
re.a[i + j - m] += b[j] * re.a[i];
re.a[i + j - m] %= MOD;
}
a[i] = 0;
}
return re;
}

void left() {
for (int i = m - 1; i >= 0; i--) a[i + 1] = a[i];
a[0] = 0;
for (int j = 0; j < m; j++) {
a[j] += b[j] * a[m];
a[j] %= MOD;
}
a[m] = 0;
}

void square() {
long long ans[MAXN] = {0};
for (int i = 0; i < m; i++) {
if (a[i])
for (int j = 0; j < m; j++) {
ans[i + j] += a[j] * a[i];
ans[i + j] %= MOD;
}
}
for (int i = 2 * m - 1; i >= m; i--) {
if (ans[i])
for (int j = 0; j < m; j++) {
ans[i + j - m] += b[j] * ans[i];
ans[i + j - m] %= MOD;
}
ans[i] = 0;
}
for (int i = 0; i < 2 * m; i++) a[i] = ans[i];
}

poly operator^(long long power) {
poly re(e), tem(e);
if (power <= 0) return re;
tem.left();
while (power) {
if (power & 1) re = re * tem;
power >>= 1;
tem.square();
}
return re;
}
};
long long ai[MAXN];

int main() {
int cc;
cin >> cc;
e[0] = 1;
while (cc--) {
cin >> m >> n;
memset(ai, 0, sizeof (ai));
memset(b, 0, sizeof (b));
for (int i = 0; i < m; i++) scanf(" %I64d", ai + i);
for (int i = 0; i < m; i++) scanf(" %I64d", b + i);
poly tem(b), ta(ai);
tem = tem^n;
long long ans = 0;
for (int i = 0; i < m; i++)
ans = (ans + tem.a[i] * ta.a[i]) % MOD;
cout << ans << endl;
}
}

1. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

2. 第23行：
hash = -1是否应该改成hash[s ] = -1

因为是要把从字符串s的start位到当前位在hash中重置

修改提交后能accept，但是不修改居然也能accept