hdu 6146 Pokémon GO (计数)

Problem Description

众所周知，度度熊最近沉迷于 Pokémon GO。

今天它决定要抓住所有的精灵球！
为了不让度度熊失望，精灵球已经被事先放置在一个2*N的格子上，每一个格子上都有一个精灵球。度度熊可以选择任意一个格子开始游戏，抓捕格子上的精灵球，然后移动到一个相邻的至少有一个公共点的格子上继续抓捕。

例如，(2, 2) 的相邻格子有(1, 1), (2, 1) 和 (1, 2) 等等。
现在度度熊希望知道将所有精灵球都抓到并且步数最少的方案数目。

两个方案被认为是不同，当且仅当两个方案至少有一步所在的格子是不同的。

Input

第一行为T，表示输入数据组数。

每组数据包含一个数N。
●1≤T≤100
●1≤N≤10000

Output

对每组数据输出方案数目，结果对 1 000 000 007 取模。

Sample Input

Sample Output

一道计数问题,重点就是要做到不重不漏.

怎样步数最短呢?当然是每个格子都只经过1次啦.

然后我们注意到如果这个起点选在中间的第i列,我们就把这个格子划分成了左右两个部分

感觉就是对于某个起点然后左右两部分是之前求过的答案直接相乘,不同起点再相加就可以了,但是关键问题是我们怎样计数呢?

我们设

$B _{1}=1$

$B _{n}=2*B_{n-1}=2^{n-1}$

同样，我们设

$A _{n}=B_{n}+2*A_{n-1}+4*A_{n-2}$

下面我们来解释这个式子

第一项 $B_{n}$ 表示从某个角开始最后回到起点的同一列的那个角

第二项 $2*A_{n-1}$ 表示从某个角开始,第二步走与起点相同列的那个角,第三步我们向第二列走的时候就有两种走法了(选择直接向右或者走对角线,乘的那个2)

从第四步开始我们现在面对的问题就是 $A_{n-1}$ 了

第三项 $4*A_{n-2}$ 中4可以看成2*2,

我们把前两列写成这个样子

1	2
3	4

第一个2代表走一个(1 2 3 4)和(1 4 3 2)有两种走法起点在第一列而终点在第二列

第二个2代表对于每一个到达第二列后第五步向第三列走的时候都有两种走法(向右或者走对角线)

从第六步开始时我们面对的问题就是 $A_{n-2}$ 了

我们现在来考虑下正经问题

首先有4个角,那么ans先加上 $4*A_{n}$

但是如果我们起点选在中间呢?

假设我们选在了第i列,首先这一列有两个格子所以先乘个2

现在我们可以选择先往左跑,我们可以直接向左,也可以走一个向左的对角线.再乘个2

注意往左跑完1~i-1列以后一点要跑到第i列那个"不是起点的点"否则没法往右跑,所以乘的是 $B_{i-1}$

现在我们又回到了第i列,现在我们向右跑,又有两种情况,直接向右,向右的对角线再乘个2

现在我们到了i+1列对于右半部分(i+1~n)我们只要跑完就行了,我们不关心终点所以乘 $A_{n-i}$

这样一开始向左跑就是 $2*(2*B_{i-1}*2*A_{n-i})$ ,一开始向右跑自然是 $2*(2*A_{i-1}*2*B_{n-i})$

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn = 11000;
 6 const ll mod = 1e9+7;
 7 ll a[maxn],b[maxn];
 8 void init()
 9 {
10     b[1]=1;
11     for (int i=2;i<maxn;++i){
12         b[i] = (b[i-1]*2)%mod;
13     }
14     a[1] = 1;
15     a[2] = 6;
16     for (int i=3;i<maxn;++i)
17         a[i] = (b[i]%mod+(2*a[i-1]%mod)+(4*a[i-2])%mod)%mod;
18 }
19 int n;
20 int main()
21 {
22     init();
23     int T;
24     scanf("%d",&T);
25     while (T--){
26         scanf("%d",&n);
27         if (n==1){
28             printf("%d
",2);
29         }
30         else{
31             ll ans = 0;
32             ans = (a[n]*4)%mod;
33             for (int i=2;i<n;++i){
34                 ans = (ans+2*( ( ( (2*b[i-1])%mod) *( (2*a[n-i])%mod ) +  ( (2*a[i-1])%mod) *( (2*b[n-i])%mod ) )%mod )%mod)%mod;
35             }
36             printf("%lld
",ans);
37         }
38     }
39     return 0;
40 }