题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2232
直接进入正题，这题要求解的是一个条件极其宽松下的组合题，似乎在看见这题的时候，我们就能遇见这道题的答案会是多么的庞大，所以题中也才会有 % 9937 这样的提示。对于如此大的一个运算，只走一步的话还好办，有9种情况，（顺时针和逆时针旋转2次加上相邻两个交换位置（交换一对的4次，交换两对的2次）最后加上原地不动的1次），就1次就够麻烦的，计算结果表明，两步共有633种可能， 足以见得后面的情况是多么的复杂。
各种百度后，我接受了接下来说明的好的方法。保留一定量的信息，通过递推求得，再在这些信息上求解这个问题。保留的信息为每个机器人在第N次行走后到达各个位置的方案数。提出了这个初步的计划后，我们应该能想到，这个方法的目的就是使得四个人行走的方格变得更加的干净，我们先一个一个机器人来计算它的特性。
假设布局如下（上面依次站着A, B, C, D号机器人）：
"0" -a "1" -b
"2" -c "3" -d
那么对于刚开始位于 "0" 的 A 机器人来说，此时它位于 "0" 的方案数为 1， 位于其他三个区域的方案数为 0，这是显而易见的，那么下一时刻呢？是这样的，此时位于"0"的方案数就变成了 1，位于"1"的方案数为 1，位于"2"的方案数为 1， 位于"3"的方案数为 0。哦，原来是这样的，就是每次加上跟 "x" 位置相邻以及本身位置上一步的方案数。
有： dp[N][0] = dp[N-1][0] + dp[N-1][1] + dp[N-1][2]; // 原谅我变量名取了dp，它看起来确实比较顺眼
dp[N][1] = dp[N-1][0] + dp[N-1][1] + dp[N-1][3];
dp[N][2] = dp[N-1][0] + dp[N-1][2] + dp[N-1][3];
dp[N][3] = dp[N-1][1] + dp[N-1][2] + dp[N-1][3];
再对初始化位置为 "1", "2", "3" 的机器人进相同的步骤就能够计算出每个机器人在第N步时，在每一个区域的方案总数。
做好了上面的准备工作，我们就能够利用这些信息来进一步解决这个棘手的问题。那么我们还是来看最简单的只走一步来分析它，由于我们已经知道了走了1步后，各个机器人最后在四个位置的方案数有多少种。
好，我们开始来数，首先是顺时针旋转，此时 A 到达了 "1", B到达了 "3", C到达了 "0" , D到达了 "2"，恩，这个情况出现了，于是我们要去找了，到第 N = 1 步的数据中寻找A在"1"有多少种方案，依次 N = 1时 B在"3"，C在"0"，D在"2"的方案数。将他们相乘即得到这种终态下的方案数。接下来就是剩下8种状态对应的方案数了。在N = 1步中这些方案总数都是1种。
但是新的问题又出来了，难道我要把每一步的所有可能的情况都推算出来吗，其实这里有个蛮力的法子，就是把所有可能的终态都计算一遍，大不了就是多加几个零呗。我们可以推算出终态总数为24种，也即4！。
这样分析完之后，题目就有可解性了。动手吧。
代码如下：
View Code
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cmath>
4 #include <cstring>
5 #include <iostream>
6 #include <algorithm>
7 using namespace std;
8
9 struct Statu
10 {
11 int dp[105][4];
12 }A[4]; // 四个机器人的位置信息
13
14 void deal( void )
15 {
16 for( int i = 0; i < 4; ++i )
17 {
18 for( int j = 1; j <= 100; ++j )
19 {
20 A[i].dp[j][0] = ( A[i].dp[j-1][0] + A[i].dp[j-1][1] + A[i].dp[j-1][2] ) % 9937;
21 A[i].dp[j][1] = ( A[i].dp[j-1][0] + A[i].dp[j-1][1] + A[i].dp[j-1][3] ) % 9937;
22 A[i].dp[j][2] = ( A[i].dp[j-1][0] + A[i].dp[j-1][2] + A[i].dp[j-1][3] ) % 9937;
23 A[i].dp[j][3] = ( A[i].dp[j-1][1] + A[i].dp[j-1][2] + A[i].dp[j-1][3] ) % 9937;
24 }
25 }
26 }
27
28 int slove( int N )
29 {
30 int sum = 0, t, base[4] = { 0, 1, 2, 3 };
31 for( int i = 0; i < 24; ++i )
32 {
33 t = ( A[0].dp[N][ base[0] ] % 9937 ) * ( A[1].dp[N][ base[1] ] % 9937 );
34 t %= 9937;
35 t *= ( A[2].dp[N][ base[2] ] % 9937 );
36 t %= 9937;
37 t *= ( A[3].dp[N][ base[3] ] % 9937 );
38 sum = ( sum + t ) % 9937;
39 next_permutation( base, base + 4 );
40 }
41 return sum;
42 }
43
44 int main()
45 {
46 for( int i = 0; i < 4; ++i )
47 {
48 A[i].dp[0][i] = 1;
49 }
50
51 deal();
52
53 int N;
54 while( scanf( "%d", &N ) != EOF )
55 {
56 printf( "%d\n", slove( N ) );
57 }
58
59 return 0;
60 }