`Algorithm-Solution` `AcWing` 4727. 摆放棋子

link

Solution

Let Dp[ i][ j][ z] denotes that, a sequence with length i, contains j blacks (also indicates i - j whites), the suffix consists of blacks with the length z.
B W B W B B corresponds to Dp[ 6][ 4][ 2]
Let Dp1[ i][ j][ z] denotes the same meaning as Dp but for whites.

A[ i][ j][ z] where A represents $Dp$ or $Dp1$
+ If z > 1, it derives from [ i - 1][ j - 1][ z - 1]
+ Otherwise z = 1, it derives from B[ i - 1][ i - j][ 1,2,3,...] (B is the alternative of A)

Code

void __Solve( int _test_id){
    ( void)_test_id;
    //--
    int n1, n2, k1, k2;
    cin >> n1 >>n2 >> k1 >> k2;
    memset( Dp, 0, sizeof( Dp));
    memset( Dp1, 0, sizeof( Dp1));
    Modulo< int> M( int(1e8));
    Dp[ 1][ 1][ 1] = 1;
    Dp1[ 1][ 1][ 1] = 1;
    for( int i = 2; i <= (n1 + n2); ++i){
        for( int j = 1; j <= n1; ++j){
            for( int z = 1; z <= k1; ++z){
                auto & cur = Dp[ i][ j][ z];
                if( z == 1){
                    int re = i - j;
                    for( int zz = 1; zz <= k2; ++zz){
                        cur = M.Add( cur, Dp1[ i - 1][ re][ zz]);
                    }
                }
                else{
                    cur = M.Add( cur, Dp[ i - 1][ j - 1][ z - 1]);
                }
            }
        }
        //--
        for( int j = 1; j <= n2; ++j){
            for( int z = 1; z <= k2; ++z){
                auto & cur = Dp1[ i][ j][ z];
                if( z == 1){
                    int re = i - j;
                    for( int zz = 1; zz <= k1; ++zz){
                        cur = M.Add( cur, Dp[ i - 1][ re][ zz]);
                    }
                }
                else{
                    cur = M.Add( cur, Dp1[ i - 1][ j - 1][ z - 1]);
                }
            }
        }
    }
    int ans = 0;
    for( int i = 1; i <= k1; ++i){
        ans = M.Add( ans, Dp[ n1 + n2][ n1][ i]);
    }
    for( int i = 1; i <= k2; ++i){
        ans = M.Add( ans, Dp1[ n1 + n2][ n2][ i]);
    }
    cout << ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50