Submission #818366


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

const ll mod=1e9+7;

int N,X,Y,Z;
int S;

bool nx[1<<16][11];
ll dp[41][1<<16];

ll dfs(int now, int state)
{
    if(dp[now][state]>=0) return dp[now][state];
    if(now==N) return 1;

    ll ret=0;
    //次に選ぶ数
    for(int i=1; i<=10; ++i)
    {
        if(nx[state][i])
        {
            ret+=dfs(now+1, ((state<<i)+(1<<(i-1)))%(1<<S));
            ret%=mod;
        }
    }

    return dp[now][state]=ret;
}

int main()
{
    cin >>N >>X >>Y >>Z;
    S=X+Y+Z-1;

    //状態maskの時に,次の数iが来ていいかチェックしておく
    rep(mask,1<<S)
    {
        //直前の状態を復元
        vector<int> b;
        int st=0;
        rep(i,S)
        {
            if(mask>>i&1)
            {
                b.pb(i-st+1);
                st=i+1;
            }
        }

        int B=b.size();
        //jを次に選んだ時にXYZを含まないかチェック
        for(int i=1; i<=10; ++i)
        {
            bool ok=true;
            //直前から順番に見ていき貪欲に足していく
            int x=0,y=0,z=i;
            int bidx=0;
            while(bidx<B && z<Z) z+=b[bidx++];
            while(bidx<B && y<Y) y+=b[bidx++];
            while(bidx<B && x<X) x+=b[bidx++];
            if(x==X && y==Y && z==Z) ok=false;

            nx[mask][i]=ok;
        }
    }

    //全体は10^N通り
    ll p10=1;
    rep(i,N) p10=(p10*10)%mod;

    memset(dp,-1,sizeof(dp));
    //XYZを含まない数列の個数
    ll r=dfs(0,0);
    //全体から引く
    ll ans=(p10-r+mod)%mod;
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Iroha and Haiku
User imulan
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1986 Byte
Status AC
Exec Time 510 ms
Memory 21888 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 4
AC × 35
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_max1.txt, subtask1_max2.txt, subtask1_max3.txt, subtask1_min1.txt, subtask1_min2.txt, subtask1_min3.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 79 ms 21888 KB
subtask0_sample_02.txt AC 80 ms 21888 KB
subtask0_sample_03.txt AC 36 ms 21248 KB
subtask0_sample_04.txt AC 510 ms 21888 KB
subtask1_01.txt AC 35 ms 21248 KB
subtask1_02.txt AC 46 ms 21248 KB
subtask1_03.txt AC 37 ms 21248 KB
subtask1_04.txt AC 41 ms 21248 KB
subtask1_05.txt AC 37 ms 21248 KB
subtask1_06.txt AC 35 ms 21248 KB
subtask1_07.txt AC 39 ms 21248 KB
subtask1_08.txt AC 35 ms 21248 KB
subtask1_09.txt AC 37 ms 21248 KB
subtask1_10.txt AC 36 ms 21248 KB
subtask1_11.txt AC 39 ms 21248 KB
subtask1_12.txt AC 65 ms 21376 KB
subtask1_13.txt AC 45 ms 21248 KB
subtask1_14.txt AC 36 ms 21248 KB
subtask1_15.txt AC 62 ms 21248 KB
subtask1_16.txt AC 210 ms 21632 KB
subtask1_17.txt AC 76 ms 21376 KB
subtask1_18.txt AC 141 ms 21376 KB
subtask1_19.txt AC 88 ms 21376 KB
subtask1_20.txt AC 47 ms 21248 KB
subtask1_21.txt AC 133 ms 21376 KB
subtask1_22.txt AC 83 ms 21376 KB
subtask1_23.txt AC 76 ms 21376 KB
subtask1_24.txt AC 59 ms 21248 KB
subtask1_25.txt AC 83 ms 21376 KB
subtask1_max1.txt AC 508 ms 21888 KB
subtask1_max2.txt AC 479 ms 21888 KB
subtask1_max3.txt AC 257 ms 21632 KB
subtask1_min1.txt AC 35 ms 21248 KB
subtask1_min2.txt AC 35 ms 21248 KB
subtask1_min3.txt AC 78 ms 21888 KB