Submission

Score: 80

User: foldnut

Problemset: กองไฟ

Language: cpp

Time: 0.114 second

Submitted On: 2025-12-01 19:27:45

#include <bits/stdc++.h>
using namespace std;
const int MD = 1e9 + 7;
int n, A, B, C, ans, dp[2][55][55][55][4];
void clean(int x){
    for(int a = 0;a<=A;a++){
        for(int b = 0;b<=B;b++){
            for(int c = 0;c<=C;c++){
                dp[x][a][b][c][0] = dp[x][a][b][c][1] = dp[x][a][b][c][2] = dp[x][a][b][c][3] = 0;
            }
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> A >> B >> C;
    if(A != 0){
        dp[1][0][1][0][2] = 1;
        dp[1][0][0][1][3] = 1;
        for(int i = 2;i<=n - 1;i++){
            clean(i%2);
            for(int a = 0;a<=A - 1;a++){
                for(int b = 0;b<=B;b++){
                    for(int c = 0;c<=C;c++){
                        if(a - 1 >= 0){
                            dp[i%2][a][b][c][1] = (dp[(i - 1) % 2][a - 1][b][c][0] + dp[(i - 1) % 2][a - 1][b][c][2] + dp[(i - 1) % 2][a - 1][b][c][3]) % MD;
                        }
                        if(b - 1 >= 0){
                            dp[i%2][a][b][c][2] = (dp[(i - 1) % 2][a][b - 1][c][0] + dp[(i - 1) % 2][a][b - 1][c][1] + dp[(i - 1) % 2][a][b - 1][c][3]) % MD;
                        }
                        if(c - 1 >= 0){
                            dp[i%2][a][b][c][3] = (dp[(i - 1) % 2][a][b][c - 1][0] + dp[(i - 1) % 2][a][b][c - 1][1] + dp[(i - 1) % 2][a][b][c - 1][2]) % MD;
                        }
                    }
                }
            }
        }
        ans += (dp[(n - 1) % 2][A - 1][B][C][0] + dp[(n - 1) % 2][A - 1][B][C][2] + dp[(n - 1) % 2][A - 1][B][C][3]) % MD;
        memset(dp, 0, sizeof dp);
    }
    if(B != 0){
        dp[1][1][0][0][1] = 1;
        dp[1][0][0][1][3] = 1;
        for(int i = 2;i<=n - 1;i++){
            clean(i%2);
            for(int a = 0;a<=A;a++){
                for(int b = 0;b<=B - 1;b++){
                    for(int c = 0;c<=C;c++){
                        if(a - 1 >= 0){
                            dp[i%2][a][b][c][1] = (dp[(i - 1) % 2][a - 1][b][c][0] + dp[(i - 1) % 2][a - 1][b][c][2] + dp[(i - 1) % 2][a - 1][b][c][3]) % MD;
                        }
                        if(b - 1 >= 0){
                            dp[i%2][a][b][c][2] = (dp[(i - 1) % 2][a][b - 1][c][0] + dp[(i - 1) % 2][a][b - 1][c][1] + dp[(i - 1) % 2][a][b - 1][c][3]) % MD;
                        }
                        if(c - 1 >= 0){
                            dp[i%2][a][b][c][3] = (dp[(i - 1) % 2][a][b][c - 1][0] + dp[(i - 1) % 2][a][b][c - 1][1] + dp[(i - 1) % 2][a][b][c - 1][2]) % MD;
                        }
                    }
                }
            }
        }
        ans += (dp[(n - 1) % 2][A][B - 1][C][0] + dp[(n - 1) % 2][A][B - 1][C][1] + dp[(n - 1) % 2][A][B - 1][C][3]) % MD;
        memset(dp, 0, sizeof dp);
    }
    if(C != 0){
        dp[1][1][0][0][1] = 1;
        dp[1][0][1][0][2] = 1;
        for(int i = 2;i<=n - 1;i++){
            clean(i%2);
            for(int a = 0;a<=A;a++){
                for(int b = 0;b<=B;b++){
                    for(int c = 0;c<=C - 1;c++){
                        if(a - 1 >= 0){
                            dp[i%2][a][b][c][1] = (dp[(i - 1) % 2][a - 1][b][c][0] + dp[(i - 1) % 2][a - 1][b][c][2] + dp[(i - 1) % 2][a - 1][b][c][3]) % MD;
                        }
                        if(b - 1 >= 0){
                            dp[i%2][a][b][c][2] = (dp[(i - 1) % 2][a][b - 1][c][0] + dp[(i - 1) % 2][a][b - 1][c][1] + dp[(i - 1) % 2][a][b - 1][c][3]) % MD;
                        }
                        if(c - 1 >= 0){
                            dp[i%2][a][b][c][3] = (dp[(i - 1) % 2][a][b][c - 1][0] + dp[(i - 1) % 2][a][b][c - 1][1] + dp[(i - 1) % 2][a][b][c - 1][2]) % MD;
                        }
                    }
                }
            }
        }
        ans += (dp[(n - 1) % 2][A][B][C - 1][0] + dp[(n - 1) % 2][A][B][C - 1][1] + dp[(n - 1) % 2][A][B][C - 1][2]) % MD;
    }
    cout << ans;
}