CCF2014年9月试题5 搭积木问题

试题信息：

限制和要求：

问题描述：

给出一个n×m的方格图，现在要用如下L型的积木拼到这个图中，使得方格图正好被拼满，请问总共有多少种拼法。其中，方格图的每一个方格正好能放积木中的一块。积木可以任意旋转。

输入格式

输入的第一行包含两个整数n, m，表示方格图的大小。
输出格式
　　输出一行，表示可以放的方案数，由于方案数可能很多，所以请输出方案数除以1,000,000,007的余数。
样例输入

6 2

样例输出

4

样例说明

四种拼法如下图所示：

评测用例规模与约定

在评测时将使用10个评测用例对你的程序进行评测。
　　评测用例1和2满足：1<=n<=30，m=2。
　　评测用例3和4满足：1<=n, m<=6。
　　评测用例5满足：1<=n<=100，1<=m<=6。
　　评测用例6和7满足：1<=n<=1000，1<=m<=6。
　　评测用例8、9和10满足：1<=n<=10^15，1<=m<=7。

解决方案

初步拿到这道题的时候，有点棘手，其实仔细想想可以将问题划分成两个部分，第一部分就是推测状态的转移，第二部分就是计算状态邻接矩阵。

状态转移

题目中实际上是一个状态转移的计算，我们将每个方格看成一个二进制的数的话，以7个方格为例说明，也就是状态0（0000000）到0x7F（1111111）之间的这些状态的相互转换，转换的规则如下：
　　
　　填完第一行后，line2达到状态复制给line1，然后line3的状态复制给line2，由于line3的状态肯定是全空（全新的一个状态，考虑到上面四种模型最多只能填充两行，因此下一行肯定是空的），就可以进行下一轮的迭代了。
　　
　　由此我们就可以首先计算任意两个状态line1，line2（line1是一个00-7F之间的一个随机状态，line2是line1经过四种填充后到达的一个状态），这里计算出任意两个状态之间进行一步转移的邻接矩阵设为A。

状态转移叠加

既然上述步骤计算出了状态转移矩阵A，下面就是计算A^(n-1)。
　　考虑到n有可能是很大的整数（10^15），因此使用普通的矩阵计算方法肯定会超时，这里使用快速幂的方法进行矩阵运算。

以上就是我的思路，下面附上我实现的代码，很可惜在小数据的时候通过了，在跑最后一个测试用例时，没通过，问题还没解决，所以下面的代码理论上还是有问题的，希望能与各位交流。

参考源码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define M 1000000007
//#define __DEBUG__
1
unsigned int matrix[128][128] = {0};
int Mval = 0;
int getposition(char a)
{
int index = 0;
for (index = 0; index < Mval; index++)
if ((a & (1 << index)) == 0)
return index;
return index;
}
void getnext(char nnn, char input, char output, int blocks)
{
int index = getposition(input);
if (index >= Mval)
{
//
printf("arrival%x %x %xn", nnn, input, output);
//
matrix[nnn][0]=1;
return;
}
switch (blocks)
{
case 1:
// xx
// x
if (index >= (Mval - 1) || (input & (1 << (index + 1))) || (output & (1 << index))) //unreachable
return ;
input += ((1 << index) + (1 << (index + 1)));
output += (1 << index);
if (input == ((1 << Mval) - 1)) //到达一个可行状态,删除一个可行状态，进行下一步迭代
{
#if __DEBUG__
printf("reachalbe from %x to %xn", nnn, output);
#endif
matrix[nnn][output] = (matrix[nnn][output] + 1) % M;
return ;
}
getnext(nnn, input, output, 1);
getnext(nnn, input, output, 2);
getnext(nnn, input, output, 3);
getnext(nnn, input, output, 4);
break;
case 2:
// xx
//
x
if (index >= (Mval - 1) || (input & (1 << (index + 1))) || (output & (1 << (index + 1)))) //unreachable
return ;
input += ((1 << index) + (1 << (index + 1)));
output += (1 << (index + 1));
if (input == ((1 << Mval) - 1)) //到达一个可行状态,删除一个可行状态，进行下一步迭代
{
#if __DEBUG__
printf("reachalbe from %x to %xn", nnn, output);
#endif
matrix[nnn][output] = (matrix[nnn][output] + 1) % M;
return ;
}
getnext(nnn, input, output, 1);
getnext(nnn, input, output, 2);
getnext(nnn, input, output, 3);
getnext(nnn, input, output, 4);
break;
case 3:
// x
// xx
if (index >= (Mval - 1) || (output & (1 << (index + 1))) || (output & (1 << index))) //unreachable
return ;
input += ((1 << index));
output += ((1 << index) + (1 << (index + 1)));
if (input == ((1 << Mval) - 1)) //到达一个可行状态,删除一个可行状态，进行下一步迭代
{
#if __DEBUG__
printf("reachalbe from %x to %xn", nnn, output);
#endif
matrix[nnn][output] = (matrix[nnn][output] + 1) % M;
return ;
}
getnext(nnn, input, output, 1);
getnext(nnn, input, output, 2);
getnext(nnn, input, output, 3);
getnext(nnn, input, output, 4);
break;
case 4:
// x
//xx
if (index == 0 || (output & (1 << (index - 1))) || (output & (1 << (index)))) //unreachable
return ;
input += (1 << index);
output += ((1 << index) + (1 << (index - 1)));
if (input == ((1 << Mval) - 1)) //到达一个可行状态,删除一个可行状态，进行下一步迭代
{
#if __DEBUG__
printf("reachalbe from %x to %xn", nnn, output);
#endif
matrix[nnn][output] = (matrix[nnn][output] + 1) % M;
return ;
}
getnext(nnn, input, output, 1);
getnext(nnn, input, output, 2);
getnext(nnn, input, output, 3);
getnext(nnn, input, output, 4);
break;
default:
break;
}
return ;
}
void initstates(void)
{
int index = 0;
int loops = (1 << Mval);
for (index = 0; index < loops; index++)
{
getnext(index, index, 0, 1);
getnext(index, index, 0, 2);
getnext(index, index, 0, 3);
getnext(index, index, 0, 4);
}
matrix[index - 1][0] = 1;
return ;
}
void printmatrix(unsigned int matrix[][128])
{
int ral, cow;
printf("
");
for (cow = 0; cow < (1 << Mval); cow++)
printf("|%.3x", cow);
printf("n");
for (ral = 0; ral < (1 << Mval); ral++)
{
printf("%.3x", ral);
for (cow = 0; cow < (1 << Mval); cow++)
if (matrix[ral][cow] == 0)
printf("|
");
else
printf("|%.3d", matrix[ral][cow]);
printf("n");
}
}
void FastExponentiation(unsigned int src[][128], unsigned int results[][128], long long times)
{
if (times == 0)return;
if (times == 1)
{
memcpy(results, src, sizeof(unsigned int) * 128 * 128);
return;
}
unsigned int sss[128][128] = {0};
long long temp = 0;
FastExponentiation(src, sss, times / 2);
int i, j, k;
for (i = 0; i < (1 << Mval); i++)
for (j = 0; j < (1 << Mval); j++)
for (k = 0; k < (1 << Mval); k++)
{
temp = (long long)sss[i][k] * sss[k][j];
results[i][j] += (temp % M) ;
results[i][j] %= M;
}
#if __DEBUG__
printf("
cccccc %dnnn", times);
printmatrix(sss);
printmatrix(results);
printf("
ccccccnnn");
#endif // __DEBUG__
if (times % 2)
{
memcpy(sss, results, sizeof(unsigned int) * 128 * 128);
memset(results, 0, sizeof(unsigned int) * 128 * 128);
for (i = 0; i < (1 << Mval); i++)
for (j = 0; j < (1 << Mval); j++)
for (k = 0; k < (1 << Mval); k++)
{
temp = (long long)sss[i][k] * src[k][j];
results[i][j] += (temp % M);
results[i][j] %= M;
}
}
#if __DEBUG__
printmatrix(sss);
printmatrix(results);
#endif // __DEBUG__
return ;
}
void FastExponentiation2(unsigned int src[][128], unsigned int results[][128], long long times)
{
unsigned int s1[128][128] = {0};
unsigned int s2[128][128] = {0};
unsigned int s3[128][128] = {0};
long long temp = 0;
int i, j, k;
for (i = 0; i < 128; i++)results[i][i] = 1;
//
printmatrix(results);
memcpy(s1, src, sizeof(unsigned int) * 128 * 128);
while (times)
{
//
printmatrix(s1);
memset(s2, 0, sizeof(unsigned int) * 128 * 128);
if (times & 1)
{
memcpy(s3, results, sizeof(unsigned int) * 128 * 128);
memset(results, 0, sizeof(unsigned int) * 128 * 128);
//
printmatrix(s3);
for (i = 0; i < (1 << Mval); i++)
for (j = 0; j < (1 << Mval); j++)
for (k = 0; k < (1 << Mval); k++)
{
temp = (long long)s3[i][k] * s1[k][j];
results[i][j] += (temp % M) ;
results[i][j] %= M;
}
}
//
printmatrix(results);
times = times >> 1;
for (i = 0; i < (1 << Mval); i++)
for (j = 0; j < (1 << Mval); j++)
for (k = 0; k < (1 << Mval); k++)
{
temp = (long long)s1[i][k] * s1[k][j];
s2[i][j] += (temp % M) ;
s2[i][j] %= M;
}
memcpy(s1, s2, sizeof(unsigned int) * 128 * 128);
}
return ;
}
//#define __DEBUG__ 1
int main(int argc, char* argv[])
{
//
freopen("out.txt", "w", stdout);
int m;
long long n;
unsigned int sss[128][128] = {0};
scanf("%lld%d", &n, &m);
Mval = m;
initstates();
#if __DEBUG__
printmatrix(matrix);
printf("nnn");
system("pause");
#endif
//
FastExponentiation(matrix,sss,n-1);
//
printf("%dn",sss[0][(1<<m)-1]);
memset(sss, 0, sizeof(unsigned int) * 128 * 128);
FastExponentiation2(matrix, sss, n - 1);
printf("%dn", sss[0][(1 << m) - 1]);
#if __DEBUG__
printmatrix(sss);
printf("nnn");
int j = 2;
for (j = 2; j <= n; j++)
{
memset(sss, 0, sizeof(unsigned int) * 128 * 128);
printf("nn%dn", j);
FastExponentiation(matrix, sss, j - 1);
printmatrix(sss);
}
#endif
return 0;
}

终于在网上找到正确的解法了，如下所示：

//ref:http://blog.csdn.net/vcvycy/article/details/78243162
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define MOD 1000000007
#define MM 7
int a[1 << MM][1 << MM];
long long n;
int m;
#define VACANT(S,u) (u>=0 && u<m && ((S&(1<<u))==0))
int SETADD(int S, int u1, int u2 = -1)
{
S |= 1 << u1;
if (u2 != -1) S |= 1 << u2;
return S;
}
int c[1 << MM][1 << MM];
void mat_mul(int a[][1 << MM], int b[][1 << MM], int sz = 1 << m)
{
memset(c, 0, sizeof(c));
for (int i = 0; i < sz; i++)
for (int j = 0; j < sz; j++)
for (int k = 0; k < sz; k++)
{
c[i][j] = (c[i][j] + 1ll * a[i][k] * b[k][j]) % MOD;
}
for (int i = 0; i < sz; i++)
for (int j = 0; j < sz; j++)
a[i][j] = c[i][j];
}
void search(int originS, int S1, int S2 = 0)
{
//printf("S1=%d,S2=%dn",S1,S2);
if (S1 == (1 << m) - 1)
{
//printf("%d->%d +1n",originS,S2);
a[originS][S2]++;
return ;
}
for (int i = 0; i < m; i++) //找到第一个没被占用的格子，然后继续搜索
if (VACANT(S1, i))
//格子i没有被占用
{
//(1) 2 1(down)
if (VACANT(S1, i + 1) && VACANT(S2, i + 1))
{
search(originS, SETADD(S1, i, i + 1), SETADD(S2, i + 1));
}
//(2) 2 1(up)
if (VACANT(S1, i + 1) && VACANT(S2, i))
search(originS, SETADD(S1, i, i + 1), SETADD(S2, i));
//(3) 1 2(up)
if (VACANT(S2, i) && VACANT(S2, i - 1))
search(originS, SETADD(S1, i), SETADD(S2, i - 1, i));
//(4) 1 2(down)
if (VACANT(S2, i) && VACANT(S2, i + 1))
search(originS, SETADD(S1, i), SETADD(S2, i, i + 1));
break;
}
}
#define FOR0(i,n) for (int i=0;i<n;i++)
int ans[1 << MM][1 << MM];
int main()
{
cin >> n >> m;
memset(a, 0, sizeof(a));
for (int S = 0; S < (1 << m); S++) search(S, S);
int matsz = (1 << m);
FOR0(i, matsz) FOR0(j, matsz) ans[i][j] = (i == j) ? 1 : 0;
//矩阵快速幂 ans=a^(n-1)
long long b = n - 1;
while (b)
{
if (b & 1) mat_mul(ans, a);
mat_mul(a, a);
b >>= 1;
}
printf("%dn", ans[0][matsz - 1]);
return 0;
}

最后

以上就是害怕大白为你收集整理的CCF2014年9月试题5 搭积木问题的全部内容，希望文章能够帮你解决CCF2014年9月试题5 搭积木问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。