网站建设吴江,服务器 空间 虚拟主机 网站需要备案吗,做网站 视频,厦门网络营销顾问试题编号#xff1a; 201409-5 试题名称#xff1a; 拼图 时间限制#xff1a; 3.0s 内存限制#xff1a; 256.0MB 问题描述#xff1a; 问题描述给出一个nm的方格图#xff0c;现在要用如下L型的积木拼到这个图中#xff0c;使得方格图正好被拼满#xff0c;请问总共有… 试题编号 201409-5 试题名称 拼图 时间限制 3.0s 内存限制 256.0MB 问题描述 问题描述 给出一个n×m的方格图现在要用如下L型的积木拼到这个图中使得方格图正好被拼满请问总共有多少种拼法。其中方格图的每一个方格正好能放积木中的一块。积木可以任意旋转。 输入格式 输入的第一行包含两个整数n, m表示方格图的大小。 输出格式 输出一行表示可以放的方案数由于方案数可能很多所以请输出方案数除以1,000,000,007的余数。 样例输入 6 2 样例输出 4 样例说明 四种拼法如下图所示 评测用例规模与约定 在评测时将使用10个评测用例对你的程序进行评测。 评测用例1和2满足1n30m2。 评测用例3和4满足1n, m6。 评测用例5满足1n1001m6。 评测用例6和7满足1n10001m6。 评测用例8、9和10满足1n10^151m7。 问题链接CCF201409试题。 问题描述参见上文。 问题分析也许从数学上先推演一下比较好这有点难。 看似可以用递归函数来实现实际做起来没有那么容易。只得了30分有胜于无而已。 对于输入的n和m若n*m不是3的倍数则肯定无法完全覆盖。同时如果不是6的倍数则不能完全覆盖。 n和m哪个更大是不知道的假设nm的情况下进行计算即可若nm将n和m交换即可。题意中则相反是mn实际上是一样的。 以下给出若各种拼图组合可以在其基础上找出递归函数关系 程序说明程序有待改进或者需要新的思路。 提交后得30分的C语言程序如下 /* CCF201409-5 拼图 */#include iostreamusing namespace std;const long long MOD 1000000007;// 模幂计算函数
inline long long powermod(int x, int y, long long mod)
{long long ans 1;while(y) {if(y 1) {ans * x;ans % mod;}x * x;x % mod;y 1;}return ans;
}long long puzzle(int n, int m)
{long long b1, b2;if(n 1 || m 1)return 0;// 面积不是3的倍数则不可能if((n * m) % 3 ! 0)return 0;// 让nmif(n m) {int temp n;n m;m temp;}if(n 2) { // 2 * 3 * k, k m / 3// n2时m必须是3的倍数if(m % 3 ! 0)return 0;return powermod(2, m / 3, MOD);} else if(n 3) { // 3 * 2 * k, k m / 2// n3时m必须是2的倍数if(m % 2 ! 0)return 0;return powermod(2, m / 2, MOD);} else if(n 4 m 6) { // 4 * 6b1 puzzle(2, m); // 分为两半b2 puzzle(2, 3); // 4*6异形数量return (b1 * b1 b2) % MOD;} else if(n 4) { // 4 * 3 * 2 * k, k m / 6 或 4 * 3 * 2 * k 4 * 3, k m / 6b1 powermod(puzzle(4, 6), m / 6, MOD);if(m % 6 0) {return b1;} else if(m % 6 3) {// 除了组合还需要考虑排列b2 puzzle(3, 4);return b1 * b2 * (m / 6 1) % MOD;} elsereturn 0;} else if(n 5 m 6) {long long b1, b2;b1 puzzle(3, m);b2 puzzle(2, m);return b1 * b2 * 2 % MOD; // 64} else if(n 5) {if(m % 6 ! 0)return 0;return powermod(puzzle(5, 6), m / 6, MOD);} else if(n 6 m 6) {// 上下分左右分异形与拼接异形种b1 puzzle(3, m); // 上下分或左右分b2 puzzle(2, 3); // 4*6异形数量return (b1 * b2 * 2 b2 * puzzle(2, 6) * 4 2) % MOD;} else if(n 6) {// 不正确这个计算就没有意义了return 0;} else {// 其他情况不考虑return 0;}
}int main()
{int n, m;long long ans;cin n m;ans puzzle(n, m);cout ans endl;return 0;
}改进上述程序提交后只得30分所以进行了进一步的分析与改进 1.使得方格图正好被拼满需要m*n是6的倍数因为积木块面积为3。程序中35-37行代码改为 // 方格图被完全拼满面积不是6的倍数则不可能if((n * m) % 6 ! 0)return 0;2.根据题意m最大为7即只需要考虑m2,3,4,5,6,7的情况。这也是得100分的希望所在。 所以程序中只需要考虑n2,3,4,5,6,7的情况程序中与题意相比n和m互换。 3.程序中增加n7的代码需要考虑6*7和7*m的情况。对于6*7的方格图可以由6*2和6*5的方格图组成也可以由6*3和6*4的方格图组成。 改进后提交得30分的C语言程序如下 /* CCF201409-5 拼图 */#include iostreamusing namespace std;const long long MOD 1000000007;// 模幂计算函数
inline long long powermod(int x, int y, long long mod)
{long long ans 1;while(y) {if(y 1) {ans * x;ans % mod;}x * x;x % mod;y 1;}return ans;
}long long puzzle(int n, int m)
{long long b1, b2;if(n 1 || m 1)return 0;// 方格图被完全拼满面积不是6的倍数则不可能if((n * m) % 6 ! 0)return 0;// 让nmif(n m) {int temp n;n m;m temp;}if(n 2) { // 2 * 3 * k, k m / 3// n2时m必须是3的倍数if(m % 3 ! 0)return 0;return powermod(2, m / 3, MOD);} else if(n 3) { // 3 * 2 * k, k m / 2// n3时m必须是2的倍数if(m % 2 ! 0)return 0;return powermod(2, m / 2, MOD);} else if(n 4 m 6) { // 4 * 6b1 puzzle(2, m); // 分为两半b2 puzzle(2, 3); // 4*6异形数量return (b1 * b1 b2) % MOD;} else if(n 4) { // 4 * 3 * 2 * k, k m / 6 或 4 * 3 * 2 * k 4 * 3, k m / 6b1 powermod(puzzle(4, 6), m / 6, MOD);if(m % 6 0) {return b1;} else if(m % 6 3) {// 除了组合还需要考虑排列b2 puzzle(3, 4);return b1 * b2 * (m / 6 1) % MOD;} elsereturn 0;} else if(n 5 m 6) {long long b1, b2;b1 puzzle(3, m);b2 puzzle(2, m);return b1 * b2 * 2 % MOD; // 64} else if(n 5) {if(m % 6 ! 0)return 0;return powermod(puzzle(5, 6), m / 6, MOD);} else if(n 6 m 6) {// 上下分左右分异形与拼接异形种b1 puzzle(3, m); // 上下分或左右分b2 puzzle(2, 3); // 4*6异形数量return (b1 * b2 * 2 b2 * puzzle(2, 6) * 4 2) % MOD;} else if(n 6 m 7) {b1 puzzle(2, 6) * puzzle(5, 6);b2 puzzle(3, 6) * puzzle(4, 6);return (b1 b2) % MOD;} else if(n 6) {// 不正确这个计算就没有意义了return 0;} else if(n 7) {return powermod(puzzle(6, 7), m / 6, MOD);} else {// 其他情况不考虑return 0;}
}int main()
{int n, m;long long ans;cin n m;ans puzzle(n, m);cout ans endl;return 0;
}经过改进的程序仍然的30分增加的有关7*m的代码完全不得分。 由于6*7的方格图可以由6*2和6*5的方格图组成也可以由6*3和6*4的方格图组成那应该是以下几种方格图的组合数计算有错误 6*2 6*5 6*3 6*4 经过仔细考察和梳理终于发现4*6至少漏算了一个情况至少应该如下图所示 上述程序的56-50行改为异形数量*2 } else if(n 4 m 6) { // 4 * 6b1 puzzle(2, m); // 分为两半b2 puzzle(2, 3) * 2; // 4*6异形数量return (b1 * b1 b2) % MOD;改进后提交只得20分分数更少了怀疑测试数据有BUG。 下一步只能考虑先改进6*6的情形了。 转载于:https://www.cnblogs.com/tigerisland/p/7564111.html
