| 题目名称 | 813. 小D的背包问题 |
|---|---|
| 输入输出 | baga.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2012-06-14加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：15， 提交：76， 通过率：19.74% | ||||
 LGLJ |
100 | 0.000 s | 0.00 MiB | C++ |
 实力演员阵容 |
100 | 0.002 s | 0.31 MiB | C++ |
 Arrow |
100 | 0.002 s | 0.31 MiB | C++ |
 QhelDIV |
100 | 0.002 s | 0.31 MiB | C++ |
 KZNS |
100 | 0.006 s | 0.29 MiB | C++ |
 Shirry |
100 | 0.006 s | 0.29 MiB | C++ |
|
Shirry |
100 | 0.006 s | 0.29 MiB | C++ |
 Asm.Def |
100 | 0.007 s | 0.26 MiB | C++ |
|
Asm.Def |
100 | 0.007 s | 0.29 MiB | C++ |
 乌龙猹 |
100 | 0.007 s | 0.30 MiB | C++ |
| 本题关联比赛 | |||
| 20120614 | |||
| 关于 小D的背包问题 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
矩阵乘法这样写似乎很慢啊=_=||我都提前把转移矩阵打成表了啊OMG= =
| ||||
|
| ||||
天一阁【问题描述】
放寒假了，小D终于可以回家了。一个学期之后他有太多的东西想带回家。
小D的背包可以被看作一个4行N列的矩阵，每个物品放入背包的物品恰好需要占据两个相邻的方格，任意两个物品不能占据相同的方格。为了充分的利用自己的背包，小D希望背包的所有空间都放置了物品，也就是说，背包中恰好放入了2N个物品。
现在小D想知道，不同的放置方案数有多少种。
【输入文件】
输入文件只有一行，包含一个正整数描述N。
【输出文件】
输出一行，一个整数表示不同的方案数。因为答案可能很大，你只需要输出结果对997取模后的结果。
【样例输入】
2
【样例输出】
5
【样例说明】
五种不同的放置方案如下：
【评分标准】
本题包含10个测试点，对于每个测试点，如果你的输出和标准输出完全一样则得到该测试点的全部分数，否则得0分。
【数据规模】
对于40%的测试数据，N ≤ 1 000
对于70%的测试数据，N ≤ 1 000 000
对于100%的测试数据，N ≤ 1 000 000 000