合肥做网站域名的公司企业管理培训

题目链接

  本题是2007年icpc亚洲区域赛达卡（Dhaka）赛区的D题

题意

  输入n（1≤n≤2 000），用下图的22种图形铺满一个3行n列的网格有多少种方法？输入答案除以$10^{12}$的余数。

分析

  把这22种图当‌插座可以分成以下9类：

  每类插座只能接入22种插头中特定的几种并转换成新的插座，提前分析好转换关系，打表递推结果。最后根据实际输入，输出相应答案即可。

AC 代码

#include <iostream>
using namespace std;#define M 1000000000000
#define N 2001
const int t[][7][3] = {{{0, 0, 1}, {1, 5, 2}, {5, 8, 2}, {11, 1, 2}, {13, 3, 2}, {17, 4, 2}, {21, 2, 2}},{{18, 0, 1}, {20, 4, 2}},{{14, 0, 1}, {19, 3, 2}},{{3, 0, 1}, {9, 1, 1}, {15, 6, 2}},{{10, 2, 1}, {12, 0, 1}, {16, 7, 2}},{{2, 0, 1}},{{7, 1, 1}},{{8, 2, 1}},{{4, 5, 2}, {6, 0, 1}}
}, c[] = {7, 2, 2, 3, 3, 1, 1, 1, 2};
long long e[N][9] = {0}; int n, kase = 0;int main() {e[0][0] = 1;for (int i=0; i<N; ++i) for (int j=0; j<9; ++j) if (e[i][j]) for (int k=0; k<c[j]; ++k) if (i+t[j][k][2] < N) {int ii = i+t[j][k][2], jj = t[j][k][1];e[ii][jj] = (e[ii][jj] + e[i][j]) % M;}while (cin >> n && n) cout << "Case " << ++kase << ": " << e[n][0] << endl;return 0;
}