相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/03/20170301145817_34363.png
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/03/20170301150237_94661.png
一句话题意
给$n_1$个$A$,$n_2$个$B$,$n_3$个$C$,$n_4$个$D$
问有多少种排列方式,使得相邻两项全部不同
$n_1,n_2,n_3,n_4 \le 10^3$
吐槽
因为做过魔法的碰撞
所以这题卡在$O(n^3)$的复杂度上卡了三个半小时 QwQ
最后暴力还$MLE$了 QwQ
解题报告
假设我们知道了将$A,B$分成$i$段、每一段中相邻两项不同的方案数为$f_i$
知道了将$C,D$分成$i$段、每一段中相邻两项不同的方案数为$g_i$
那么答案显然为$\sum\limits_{i=1}^{n_1+n_2}{f_i \cdot (g_{i-1}+2g_i+g_{i+1})}$
至于中间那一项为什么要乘以2? 因为多出来那一段我们既可以放段首,也可以放段尾
现在唯一的问题就是如何求出$f_i,g_i$了
考虑仅由$A,B$组成的字符串,一定为以下四种情况之一
[1]ABAB…A
[2]BABA…B
[3]ABAB…B
[4]BABA…A
假如我们枚举第一种情况出现了$i$次
那么第二种情况的出现次数$j=i-(a-b)$
那剩下的$k$次,就是第三种和第四种了,不难发现我们乘上$2^k$之后他们就可以视为等价
于是我们先在第一种情况的位置上插入$A$,第二种情况插入$B$,第三、四种情况插入$AB(BA)$
之后我们相当于把剩下的$A,B$两两配对,然后分成$x$组,允许空集
那么这就是插板法的板题了
于是我们就用上述算法处理出$f_i,g_i$即可
时间复杂度:$O(n^2)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int MOD = 1000000007; const int N = 2009; int vout,f[N],g[N],C[N][N],PW2[N]; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline int solve(int a, int b, int c) { if (a < b) swap(a, b); if (!a && b) return b == c; int ret = 0; for (int i=a-b,j,k;i<=c;++i) { j = i - a + b; k = c - i - j; if (j >= 0 && k >= 0 && a >= i + k ) { (ret += (((LL)C[i] * C[j][c-i] % MOD) * PW2[k] % MOD) * C[c-1][a-i-k+c-1] % MOD) %= MOD; } } return ret; } int main() { PW2[0] = 1; for (int i=1;i<N;i++) PW2[i] = (PW2[i-1] << 1) % MOD; C[0][0] = 1; for (int i=1;i<N;i++) { C[0][i] = 1; for (int j=1;j<=i;j++) { C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD; } } int a=read(),b=read(),c=read(),d=read(); if (a + b == 0) f[1] = 1; else for (int i=1;i<=a+b;i++) f[i] = solve(a, b, i); if (c + d == 0) g[1] = 1; else for (int i=1;i<=c+d;i++) g[i] = solve(c, d, i); for (int i=1;i<=a+b;i++) (vout += f[i] * (g[i-1] + 2ll * g[i] + g[i+1]) % MOD) %= MOD; printf("%d\n",vout); return 0; }