危险的组合

639 词

题目描述

有一些装有铀(用U表示)和铅(用L表示)的盒子,数量均足够多。要求把N个盒子放成一行,但至少有3个U放在一起,有多少种方法?

输入

第一行包含一个整数N $(3<=N<=1000000)$。

输出

输出一个整数表示方法数(结果模 $1000000007$ )。

样例输入

1
4

样例输出

1
3

提示

$$3<=N<=30$$

输入:4 输出:3

样例解释:UUUL、LUUU、UUUU

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
int main() {
long long dp[1000001][4];
int mod = 1000000007;
int n;
while (cin >> n) {
dp[0][0] = dp[0][1] = 1;
dp[0][2] = dp[0][3] = 0;
for (int i = 1; i < n; i++) {
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod;
dp[i][1] = dp[i - 1][0] % mod;
dp[i][2] = dp[i - 1][1] % mod;
dp[i][3] = (dp[i - 1][3] * 2 + dp[i - 1][2]) % mod;
}
cout << dp[n - 1][3] % mod << endl;
}
return 0;
}