3613: 背包问题 -训练套题T6T2
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：1
Description
2. 背包问题 (bag.pas/c/cpp)
【问题描述】
放寒假了，小D终于可以回家了。一个学期之后他有太多的东西想带回家。
小D的背包可以被看作一个4行N列的矩阵，每个物品放入背包的物品恰好需要占据两个相邻的方格，任意两个物品不能占据相同的方格。为了充分的利用自己的背包，小D希望背包的所有空间都放置了物品，也就是说，背包中恰好放入了2N个物品。
现在小D想知道，不同的放置方案数有多少种。
【输入】
输入文件只有一行，包含一个正整数描述N。
【输出】
输出一行，一个整数表示不同的方案数。因为答案可能很大，你只需要输出结果对997取模后的结果。
【输入输出样例】
|
bag.in |
bag.out |
|
2 |
5 |
【输入输出样例说明】
五种不同的放置方案如下：
【数据规模】
对于40%的测试数据，N ≤ 1 000
对于70%的测试数据，N ≤ 1 000 000
对于100%的测试数据，N ≤ 1 000 000 000
HINT
第一题【提示】
矩阵(Matrix)是一个n*m的数组。例如[1 2]就是一个l*2的矩阵。
矩阵乘法这样定义：
如果A是n*m的矩阵，B是m*t的矩阵，设矩阵．C=A*B，则
其中C是一个n*t的矩阵。
例如，对于斐波那契数可以列出这个递推公式：
矩阵乘法不满足交换律，但满足结合律。
本题是数学问题。
前50分用于送分，考查大家的模拟能力。
由于数据规模较大，因此需要矩阵优化。
然而题目已经提示了优化方法，因此本题考查分析、推广、类比的能力。
【hjf补充】构造矩阵
已知f0=1 f1=2 f2=3
对于这个3阶的递推式
构造3*3的矩阵：
矩阵的第3列为各项系数，分别是1，10，3
矩阵左下角2*2的矩阵的主对角线（左上到右下）上为1，其余为0
若求第k项
由于矩阵满足结合律，故可以使用二分求解
例如A*B^6=A*B*B*B*B*B*B=A*B^3*B^3=A*(B^2*B)^2
function multiply(a,b:matrix):matrix; //矩阵乘法
var c:matrix;
i,j,k:longint;
begin
for i:=1 to n do
for j:=1 to n do
for k:=1 to n do
c[i,j]:=(c[i,j]+a[i,k]*b[k,j]) mod m;
exit(c);
end;
function pow(i:int64):matrix;
var t:matrix;
begin
if i=1 then exit(a);
t:=pow(i div 2);
t:=multiply(t,t);
if odd(i) then t:=multiply(t,a);
exit(t);
end;
矩阵(Matrix)是一个n*m的数组。例如[1 2]就是一个l*2的矩阵。
矩阵乘法这样定义：
如果A是n*m的矩阵，B是m*t的矩阵，设矩阵．C=A*B，则
其中C是一个n*t的矩阵。
例如，对于斐波那契数可以列出这个递推公式：
矩阵乘法不满足交换律，但满足结合律。
本题是数学问题。
前50分用于送分，考查大家的模拟能力。
由于数据规模较大，因此需要矩阵优化。
然而题目已经提示了优化方法，因此本题考查分析、推广、类比的能力。
【hjf补充】构造矩阵
已知f0=1 f1=2 f2=3
对于这个3阶的递推式
构造3*3的矩阵：
矩阵的第3列为各项系数，分别是1，10，3
矩阵左下角2*2的矩阵的主对角线（左上到右下）上为1，其余为0
f3=1+10*2+3*3=30 得到验证
若求第k项
由于矩阵满足结合律，故可以使用二分求解
例如A*B^6=A*B*B*B*B*B*B=A*B^3*B^3=A*(B^2*B)^2
function multiply(a,b:matrix):matrix; //矩阵乘法
var c:matrix;
i,j,k:longint;
begin
for i:=1 to n do
for j:=1 to n do
for k:=1 to n do
c[i,j]:=(c[i,j]+a[i,k]*b[k,j]) mod m;
exit(c);
end;
function pow(i:int64):matrix;
var t:matrix;
begin
if i=1 then exit(a);
t:=pow(i div 2);
t:=multiply(t,t);
if odd(i) then t:=multiply(t,a);
exit(t);
end;