首页 > ACM题库 > HDU-杭电 > hdu 3735 Recursive Sequence[解题报告]C++
2015
02-22

hdu 3735 Recursive Sequence[解题报告]C++

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