本文共 2183 字，大约阅读时间需要 7 分钟。
题意：中文...
思路：
话说这类题目做的真的很少，比赛时无从下手。首先我们不考虑组内之间的顺序问题，将其转化为组合。dp[i][j]表示第i组插入到队列中存在j个空，该空的左右两边是同一组的人，这样我们只要将第i + 1组的人查到该空的话，就是合法的。 这里用了一下滚动数组优化了一下。
dp[cur][i - k + x - j] += dp[pre][i]*c[x - 1][j - 1]%mod*c[i][k]%mod*c[sum - i][j - k]%mod;
pre表示前一状态，i表示枚举的前一状态下，存在i个满足上述条件的空。c[x - 1][j - 1]表示将当前组的x个人分成j组，然后往i个空里面插。 c[i][k]表示选择分成j组里面的k组i组里面插，c[sum - i][j - k]表示将插完剩下的人插入到不满足上述条件的孔里面。 i - k + x - j表示插入完成后所形成的的状态。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll __int64#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 307#define N 450using namespace std;const ll mod = 1000000007;ll a[48];ll dp[2][N];ll c[N][N];int pre,cur,sum;void init(){ int i,j; for (i = 0; i < N; ++i) c[i][i] = c[i][0] = 1; for (i = 2; i < N; ++i) { for (j = 1; j < i; ++j) { c[i][j] = c[i - 1][j] + c[i - 1][j - 1]; if (c[i][j] >= mod) c[i][j] -= mod; } } a[0] = 1; for (i = 1; i < 48; ++i) { a[i] = (a[i - 1]*i)%mod; }}int main(){// Read(); int i,j,k; int T,n,x; int cas = 1; scanf("%d",&T); init(); while (T--) { scanf("%d",&n); pre = 0; cur = 1; CL(dp,0); dp[pre][0] = 1; sum = 1; ll JC = 1; while (n--) { scanf("%d",&x); for (i = 0; i < N; ++i) dp[cur][i] = 0; for (i = 0; i < sum; ++i) { if (dp[pre][i]) { for (j = 0; j <= x; ++j) { for (k = 0; k <= j && k <= i; ++k) { dp[cur][i - k + x - j] += dp[pre][i]*c[x - 1][j - 1]%mod*c[i][k]%mod*c[sum - i][j - k]%mod; dp[cur][i - k + x - j] %= mod; } } } } swap(pre,cur); sum += x; JC = (JC*a[x])%mod; }// printf("%I64d %I64d\n",dp[pre][0],JC); ll ans = dp[pre][0]*JC%mod; printf("Case %d: %I64d\n",cas++,ans); } return 0;}
转载地址：http://ottbl.baihongyu.com/
View Code