题目大意：

有来自三个地区的人各a,b,c位，他们排成了一排。请问有多少种不同类型的排法，使得相邻的人都来自不同的地区

\(a,b,c<=200\)

答案取模

题解

弱弱的标程解法

设\(f[i][j][k][l]\)表示三种人各排了\(i\)、\(j\)、\(k\)个，最后一个人是l类

那么转移就很显然了，枚举下一个非\(l\)人即可

#include
    
     #include
     
      #include
      
       using namespace std;const int maxn = 205,P = 2001611;int f[maxn][maxn][maxn][3],a,b,c;int main(){    scanf("%d%d%d",&a,&b,&c);    f[1][0][0][0] = f[0][1][0][1] = f[0][0][1][2] = 1;    for (int i = 0; i <= a; i++)        for (int j = 0; j <= b; j++)            for (int k = 0; k <= c; k++)                for (int l = 0; l <= 2; l++){                    if (i < a && l != 0)                        f[i + 1][j][k][0] = (f[i + 1][j][k][0] + f[i][j][k][l] * (i + 1) % P) % P;                    if (j < b && l != 1)                        f[i][j + 1][k][1] = (f[i][j + 1][k][1] + f[i][j][k][l] * (j + 1) % P) % P;                    if (k < c && l != 2)                        f[i][j][k + 1][2] = (f[i][j][k + 1][2] + f[i][j][k][l] * (k + 1) % P) % P;                }    printf("%d\n",(f[a][b][c][0] + f[a][b][c][1] + f[a][b][c][2]) % P);    return 0;}
      
     
    

更优秀的解法

std解法考虑往队尾插人，需要设置四维状态

我们考虑只设置三维状态，运用记忆化搜索

同样设\(f[i][j][k]\)表示三种人各排了\(i\)、\(j\)、\(k\)个

可以发现三种人是等价的，人数互换不影响结果

所以我们只考虑\(i <= j <= k\)

转移时，为使状态最终能转移至初始状态，我们考虑人数最多的\(k\)

我们在最后合法的队形中抽出\(k\)中的一个人，会出现两种情况：

①最后的队列还是一个合法队列

②最后的队列不合法，而且仅有原来抽出的位置有两个相同的人相邻

那么就可以转移了

①如果合法，就有\(f[i][j][k - 1]\)中队形，其中有\(i + j - k + 2\)个可插入位置，总共有\(f[i][j][k - 1] * (i + j - k + 2)\)种方案

②如果不合法，要么是\(i\)相邻，要么是\(j\)相邻，

以\(i\)相邻为例，我们如果把相邻的两个人看做一个人，那么这个状态就又是合法的了，有\(f[i - 1][j][k]\)种方案，而\(i\)中任意选两个人有序组合，有\(P_{i}^{2}\)中方案，故对\(i\)总共有\(f[i - 1][j][k - 1] * P_{i}^{2}\)中方案

\(j\)类似

考虑边界，当出现0时，

①两个0，即只剩一种人了，当且仅当人数为1时方案数为1，否则为0

②一个0，即剩余两种人，如果两种人人数只差超过了1，方案数为0，否则两种人之间的位置关系一定是交替的，用排列数计算即可

具体实现参考代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define LL long long int#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<
         
          <<' '; puts("");using namespace std;const int maxn = 205,maxm = 100005,INF = 1000000000,P = 2001611;LL f[maxn][maxn][maxn],fac[maxn];bool vis[maxn][maxn][maxn];void order(LL& x,LL& y,LL& z){ if (x > y) swap(x,y); if (x > z) swap(x,z); if (y > z) swap(y,z);}LL F(LL x,LL y,LL z){ order(x,y,z); if (vis[x][y][z]) return f[x][y][z]; //记忆化 vis[x][y][z] = true; LL& ff = f[x][y][z]; if (y == 0) return ff = (z == 1); //边界 if (x == 0){ if (z == y) return ff = fac[z] * fac[y] % P * 2 % P; if (abs(z - y) == 1) return ff = fac[z] * fac[y] % P; return 0; } return ff = (F(x,y,z - 1) * (x + y - z + 2) % P + x * (x - 1) % P * F(x - 1,y,z - 1) % P + y * (y - 1) % P * F(x,y - 1,z - 1) % P) % P;}int main(){ fac[0] = 1; for (int i = 1; i <= 200; i++) fac[i] = fac[i - 1] * i % P; //预处理阶乘 LL a,b,c; scanf("%lld%lld%lld",&a,&b,&c); printf("%lld\n",F(a,b,c)); return 0;}