Problem Specification Value
Time Limit 10 Sec
Memory Limit 162 MB
Submit 1490
Solved 916

Description

有 n 个木块排成一行, 从左到右依次编号为 1~ n. 你有 k 种颜色的油漆, 其中第 i 种颜色的油漆足够涂 ci 个木块. 所有油漆刚好足够涂满所有木块, 即 c1+c2+...... +ck=n. 相邻两个木块涂相同色显得很难看, 所以你希望统计任意两个相邻木块颜色不同的着色方案.

Input

第一行为一个正整数 k, 第二行包含 k 个整数 c1, c2,. ...... , ck.

Output

输出一个整数, 即方案总数模 1, 000, 000, 007 的结果.

Sample Input

3
1 2 3

Sample Output

10

HINT

100% 的数据满足: 1 <=k <=15, 1 <=ci <=5

Source

直接集合 dp 肯定是不行的...... 考虑两种油漆如果当前都能涂 x 次, 那么他们本质是一样的.

所以用 F [a] [b] [c] [d] [e] [l] 表示当前有能涂 1 次的油漆 a 个, 能涂 2 次的 b 个…. 前一个颜色为 l, 再搞下转移就行了.

记忆化实现常数会小一些


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lld;
const int maxk = 16, maxc = 6;
const lld modr = 1000000007;

lld     dp_save[maxk][maxk][maxk][maxk][maxk][maxc];
bool    dp_used[maxk][maxk][maxk][maxk][maxk][maxc];
int     n, data[maxc];

lld dp(int a, int b, int c, int d, int e, int k)
{
    // a, b, c, d, e separately means the numbers of colours remaining, with the
    // respective remaining painting chances / counts to paint blocks, for 1, 2, 3,
    // 4, 5, respectively.
    // k means the last colour (count) used
    if (dp_used[a][b][c][d][e][k])
        return dp_save[a][b][c][d][e][k];
    if (a + b + c + d + e <= 0)
        return 1; // End of the line, about to recurse, say.
    lld sum = 0;
    if (a > 0) sum += (a - (k == 2)) * dp(a - 1, b, c, d, e, 1); // That was a trick.
    if (b > 0) sum += (b - (k == 3)) * dp(a + 1, b - 1, c, d, e, 2); // That was a trick.
    if (c > 0) sum += (c - (k == 4)) * dp(a, b + 1, c - 1, d, e, 3); // That was a trick.
    if (d > 0) sum += (d - (k == 5)) * dp(a, b, c + 1, d - 1, e, 4); // That was a trick.
    if (e > 0) sum += e * dp(a, b, c, d + 1, e - 1, 5); // That was a trick.
    // Updating saved changes...
    sum %= modr;
    dp_used[a][b][c][d][e][k] = true;
    dp_save[a][b][c][d][e][k] = sum;
    return sum;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int a, i = 1; i <= n; i++) {
        scanf("%d", &a);
        data[a]++;
    }
    lld res = dp(data[1], data[2], data[3], data[4], data[5], 0);
    printf("%lld\n", res);
    return 0;
}
from pydatagen import *
n = randrange(10, 16)
printf('%d\n' % n)
for i in range(0, n):
    printf('%d ' % randrange(1, 6))