[SCOI2008] coloring scheme” (to be continued)

Subject matter：A row;Row 1\(n\)A piece of wood,\(k\)Kinds of paint, each paint.\(c_i\)The barrel requires that the color of two adjacent blocks cannot be the same.\(\pmod{1e9+7}\)

Solution.1

• state：set up\(f[i][j]\)For the former\(i\)The block is painted, and the last piece is\(j\)colour
• transfer：$f[i][j] = \sum_{h=1,h \ne j } ^ {k}f[i-1][h] $

OK, I can’t record how much each barrel is used, hang up.

Eh, this is this\(c[i]\)It’s a little small, and if two kinds of paint remain the same number of barrels, explain.

• state：set up\(f[a][b][c][d][e][last]\)To be left\(1\)Bucket\(a\)Seed, left\(2\)Bucket\(b\)species\(\dots\),Still left\(5\)Bucket\(e\)The last one was last time.\(k​\)The number of paints for barrels.
• transfer：See the code in detail

Code.1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

typedef long long ll;

const int Mod = 1e9 + 7;

int x[6];
ll f[16][16][16][16][16][6];

ll dp(int a, int b, int c, int d, int e, int k){
    if(a + b + c + d + e == 0) return 1;
    if(f[a][b][c][d][e][k]) return f[a][b][c][d][e][k] % Mod;
    ll t = 0;
    if(a)
        t = (t + 1LL * (a - (k == 2)) * dp(a - 1, b, c, d, e, 1)) % Mod;
    if(b)
        t = (t + 1LL * (b - (k == 3)) * dp(a + 1, b - 1, c, d, e, 2)) % Mod;
    if(c)
        t = (t + 1LL * (c - (k == 4)) * dp(a, b + 1, c - 1, d, e, 3)) % Mod;
    if(d)
        t = (t + 1LL * (d - (k == 5)) * dp(a, b, c + 1, d - 1, e, 4)) % Mod;
    if(e)
        t = (t + 1LL * e * dp(a, b, c, d + 1, e - 1, 5)) % Mod;
    f[a][b][c][d][e][k] = t % Mod;
    return t % Mod;
}

int main(){
    int k;
    scanf("%d", &k);
    for(int i = 1, la; i <= k; ++i){
        scanf("%d", &la);
        x[la] ++;
    }
    printf("%lld\n", dp(x[1], x[2], x[3], x[4], x[5], 0) % Mod);
    return 0;
}

Solution.2

Permutation and combination make DP