题目链接:http://nyoj.top/problem/1273

  • 内存限制:64MB 时间限制:1000ms

题目描述

ALPHA 小镇风景美丽，道路整齐，干净，到此旅游的游客特别多。CBA 镇长准备在一条道路南 面 4*N 的墙上做一系列的宣传。为了统一规划，CBA 镇长要求每个宣传栏只能占相邻的两个方格 位置。但这条道路被另一条道路分割成左右两段。CBA 镇长想知道，若每个位置都贴上宣传栏， 左右两段各有有多少种不同的张贴方案。 例如： N=6，M=3, K=2, 左，右边各有 5 种不同的张贴方案 

输入描述

第一行： T 表示以下有 T 组测试数据 （ 1≤T ≤8 ）
接下来有T行， 每行三个正整数 N M K 分别表示道路的长度，另一条道路的起点和宽度
（1≤ N ,M ≤ 1 000 000, 1≤ K ≤ 100000）

输出描述

每组测试数据，输出占一行：两个整数，分别表示左右两段不同的张贴方案数。由于方案总数
可能很大，请输出对 997 取模后的结果。

样例输入

2
6 3 2
5 3 2

样例输出

5 5
5 1

解题思路

a[i]为长度i的方案总数;
q[i]为长度为i,并且不可被纵向分开的方案总数(不能由两种更小的长度拼接起来)
很容易得到:a[i]=SUM(q[j]*a[i-j]),j<i.
现在有两个问题，首先是如何求得q[i]，其次递推式的复杂度为O(n^2)，很明显是不满足这题的数据量的。
我们先考虑第一个问题，多次尝试画出不能分开的方案数(很好找规律),
我们可以总结出一个规律:
i=1,q[i]=1;
i=2,q[i]=4;
i>3,当i为奇数时,q[i]=2,当i为偶数时,q[i]=3,
故a[i]=a[i-1]+4a[i-2]+2a[i-3]+3a[i-4]+2a[i-5]+3a[i-6]......+xa[1];
则a[i-2]=a[i-3]+4a[i-4]+2a[i-5]+3a[i-6]......+xa[1];
两式相减可得到:a[i]=a[i-1]+5a[i-2]+a[i-3]-a[i-4];

#include <bits/stdc++.h>
using namespace std;
int a[1100000];
int main() {
    int t, m, n, k;
    a[0] = a[1] = 1;
    a[2] = 5, a[3] = 11;
    for (int i = 4; i <= 1000000; i++)
        a[i] = (a[i - 1] + 5 * a[i - 2] + a[i - 3] - a[i - 4]) % 997;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &m, &k);
        printf("%d %d\n", a[m - 1], a[n - k - m+1]);
    }
    return 0;
}