题目描述
Gzh一觉醒来，发现自己穿越到了15年之前，摆在他面前的有一堆积木，于是他就兴致勃勃的开始玩起了积木。
积木只有两种样式，分别是长6厘米宽3厘米的和长6厘米宽6厘米的。
无聊的Gzh想把积木一直拼下去，假设最后的长度为n，那么Gzh会把积木拼成一个形状为6*n的长条。
那么请问，当积木的长度为n时，共有多少种拼法呢？
输入
多组输入数据
每组输入一个数n（0<n<751），保证n为3的倍数。
输出
对于每组数据，输出一行，拼法的数量
输入样例
6输出样例
3算法分析
首先，根据题意写出递推公式。对于长度为n的矩形，先要看大体上n是怎么分的，即先不考虑两个6*3可以组成一个6*6的情况。因此有二元一次方程n=3x+6y，其中x代表需要的6*3的矩形个数，y代表需要的6*6的矩形的个数。那么可以求出该方程的非负整数解，例如n=18的时候，根据二元一次方程可以解得，(6,0)、(4,1)、(2,2)、(0,3)为方程的解。然后从两个维度来考虑问题。称6*3的矩形为小矩形，6*6的矩形为大矩形。首先，考虑摆放顺序的问题。对于x个大矩形和y个小矩形的情况，有多少种摆放方式：把x个大矩形放在桌子上，那么它有x+1个空位供y个小矩形来选择，那么情况数量为：C(x+y, y)种情况（C为组合数），。其次，再考虑一个大矩形可以分成两个小矩形，对于某种拥有y个大矩形的情况，每个大矩形都可以分成两个小矩形，因此每个大矩形都有两种选择：分成两个小矩形和不分维持大矩形的状态，那么有2^y种分法。即对于n=3x+6y的每一个解(x,y)的情况数量为：C(x+y, y)* 2^y，再根据x和y的函数关系可整理为：C((n-3*y)/3, y)*(2^y)。而对于每一个n，其y的取值可从为0到n/2的每一个整数。则给出一个n可以通过遍历y每个可能的取值，累加每个y对应的情况个数，递推公式可写成sum[y]=sum[y-1]+C((n-3*y)/3, y)*(2^y)。然后信心满满地提交了，然后WA了。
算法肯定没问题，结果也没问题。然后我检查最大可能的n值，也就是n=750的时候，炸了，超过了unsigned long long的范围，所以这道题是一个高精度输出问题。
对于高精度输出，我的想法是使用结构体数组，每个结构体situ[i]代表n为i时的情况，那么每个结构体中又有一个数组num[]，num[i]代表第i+1位的数字是多少，还有一个int类型的变量digit，代表这个数有多少位。
然而高精度的运算能进行普通的四则运算就已经不错了，而我的递推公式有组合数和乘方的运算，基本上很难用上述提到的结构体来实现，所以要更改递推公式，而且这个递推公式不能有太复杂的运算。通过前面的公式，基本上n=210之前的数都可以算出来，所以我就算了一些数开始找规律。那么对于数对(n, f[n])（这里f[n]是n对应的情况数量）有如下数对符合要求：(3,1), (6,3), (9,5), (12,11), (15,21), (18,43), (21,85), (24,171), (27, 341), (30,683)…
从中不难发现规律（的确不难……）f[n]=2*f[n-6]+f[n-3]，这就是新的递推公式，而且仅用到了乘法和加法。当然也可以这么解释这个递推公式：对于某种情况，假设为f[i]，那么要分两种情况讨论：首先，因为f[i-3]长度和f[i]差了3，所以在f[i-3]的情况后面续一个6*3的小矩形，所以所有f[i-3]的情况都可以变成f[i]的情况，所以是1倍的f[i-3]；其次对于f[i-6]的情况，f[i-6]长度和f[i]差了6，就是在后面续一个大矩形（6*6），大矩形可以有三种分法：一种是直接摆大矩形，另一种是两个6*3横着放。不能算上两个6*3竖着放的，因为本身在f[i-3]后面续小矩形中就包括了竖着放的情况了，再算就重复了，所以是2倍的f[i-6]。因此递推公式是f[n]=2*f[n-6]+f[n-3]，易得f[3]=1，f[6]=3。
接下来就可以构造运算的函数了，首先是乘，其实这里就是加倍，那么可以从digit=0即第一位开始每一位都乘二，结果mod 10作为所求的对应位的值，如果某一位乘2大于10了，那么要进位，即前一位的值自增1，循环往复。要注意最后一位，如果进位了的话，digit还要自增1，否则其实digit少加了一次。加法其实类似，也是注意进位就可以了。最后输出的时候，要从高位向低位输出。
易错点
首先找递推公式是一个难点，其次要意识到WA是高精度的缘故而不是算法的问题。解决这两点，这道题就可以解出来了。然后写运算函数的时候要关注进位。
1 #include <stdio.h>
2 #include <algorithm>
3 #include <string.h>
4 using namespace std;
5 struct matrix
6 {
7 int num[300];
8 int digit=-1;
9 }situ[751];
10
11 struct matrix MultiDouble(struct matrix a)
12 {
13 struct matrix b;
14 memset(b.num,0,300);
15 b.digit=-1;
16 for(int i=0;i<=a.digit;i++){
17 b.num[i]+=(a.num[i]*2)%10;
18 b.digit++;
19 if(a.num[i]*2>=10) b.num[i+1]++;
20 }
21 if(2*a.num[a.digit]>=10) b.digit++;
22 return b;
23 }
24
25 struct matrix Sum(struct matrix a,struct matrix b)
26 {
27 struct matrix c;
28 memset(c.num,0,300);
29 c.digit=-1;
30 for(int i=0;i<=max(a.digit,b.digit);i++){
31 c.num[i]+=(a.num[i]+b.num[i])%10;
32 c.digit++;
33 if(a.num[i]+b.num[i]>=10) c.num[i+1]++;
34 }
35 if(a.num[max(a.digit,b.digit)]+b.num[max(a.digit,b.digit)]>=10)
36 c.digit++;
37 return c;
38 }
39
40 int main()
41 {
42 situ[3].num[0]=1;
43 situ[3].digit=0;
44 situ[6].num[0]=3;
45 situ[6].digit=0;
46 int n;
47 while(~scanf("%d",&n)){
48 for(int i=9;i<=n;i+=3){
49 situ[i]=Sum(MultiDouble(situ[i-6]),situ[i-3]);
50 }
51 int flag=0;
52 for(int i=situ[n].digit;i>=0;i--){
53 printf("%d",situ[n].num[i]);
54 }printf("\n");
55 }
56 }