funny function

$$F_{1,1}=F_{1,2}=1$$ $$F_{1,i}=F_{1,i-1}+2F_{1,i-2}, i geq 3$$ $$F_{i,j}= sum_{k=j}^{j+n-1} F_{i-1,k} (i geq 2, j geq 1)$$

输入$n$和$m$，计算$F_{m,1}.$对$1000000007$取模。

首先很容易可以用特征根计算出$F_{1,i}$的通项公式。

$$F_{1,i}= frac{1}{3} {2}^{i} - frac{1}{3} {(-1)}^{i}$$

然后无脑计算$F_{i,j}$,容易发现其实他也是等比数列。

$$F_{i,j} = sum_{k=j}^{j+n-1} F_{i-1,k}$$ $$F_{2,j}= sum_{k=j}^{j+n-1} frac{1}{3} {2}^{k-1} - sum_{k=j}^{j+n-1} frac{1}{3} {(-1)}^{k-1}$$ $$= (frac{1}{3} {2}^{n}) {2}^{j} - frac{1}{3} (1-{(-1)}^{n}) {(-1)}^{j}$$

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "