题目大意：
有来自三个地区的人各a,b,c位，他们排成了一排。请问有多少种不同类型的排法，使得相邻的人都来自不同的地区
(a,b,c<=200)
答案取模
题解##
弱弱的标程解法##
设(f[i][j][k][l])表示三种人各排了(i)、(j)、(k)个，最后一个人是l类
那么转移就很显然了，枚举下一个非(l)人即可
#include<iostream>
#include<cstdio>
#include<algorithm>
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
",(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<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#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<<s[i]<<' '; 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
",F(a,b,c));
return 0;
}