Submission

Score: 100

User: erng

Problemset: กองไฟ

Language: cpp

Time: 0.012 second

Submitted On: 2026-03-11 22:30:29

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll n, a, b, c, dp[155][55][55][3][3], ans, mod=1e9+7;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>a>>b>>c;
    if (a) dp[1][1][0][0][0]=1;
    dp[1][0][1][1][1]=1;
    dp[1][0][0][2][2]=1;
    for (int i=2; i<=n; i++)
    {
        for (int j=0; j<=a; j++)
        {
            for (int k=0; k<=b; k++)
            {
                int ca=j, cb=k, cc=i-j-k;
                if (cc>c || cc<0) continue;
                for (int cur=0; cur<3; cur++)
                {
                    for (int f=0; f<3; f++)
                    {
                        if (cur==0)
                        {
                            if (!ca) continue;
                            for (int pv=0; pv<3; pv++)
                            {
                                if (pv!=cur) dp[i][ca][cb][cur][f]=(dp[i][ca][cb][cur][f]+dp[i-1][ca-1][cb][pv][f])%mod;
                            }
                        }
                        if (cur==1)
                        {
                            if (!cb) continue;
                            for (int pv=0; pv<3; pv++)
                            {
                                if (pv!=cur) dp[i][ca][cb][cur][f]=(dp[i][ca][cb][cur][f]+dp[i-1][ca][cb-1][pv][f])%mod;
                            }
                        }
                        if (cur==2)
                        {
                            if (!cc) continue;
                            for (int pv=0; pv<3; pv++)
                            {
                                if (pv!=cur) dp[i][ca][cb][cur][f]=(dp[i][ca][cb][cur][f]+dp[i-1][ca][cb][pv][f])%mod;
                            }
                        }
                    }
                }
            }
        }
    }
    for (int i=0; i<3; i++)
    {
        for (int j=0; j<3; j++)
        {
            if (i==j) continue;
            ans=(ans+dp[n][a][b][i][j])%mod;
        }
    }
    cout<<ans;
}