Submission #4648810

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=1e9+7;

void array_show(int *a,int n){
	for(int i=0;i<n;i++)printf("%d%c",a[i],(i!=n-1?' ':'\n'));
}
void array_show(LL *a,int n){
	for(int i=0;i<n;i++)printf("%lld%c",a[i],(i!=n-1?' ':'\n'));
}

long long int pow_mod(long long int p_a,long long int p_n,long long int p_p=1e9+7){
	//p_a^p_n mod p_p
	long long int p_b=1,p_t=1;
	for(;p_b<=p_n;p_b<<=1);
	for(p_b>>=1;p_b>0;p_b>>=1){
		p_t*=p_t;
		if(p_t>=p_p)p_t%=p_p;
		if(p_n&p_b)p_t*=p_a;
		if(p_t>=p_p)p_t%=p_p;
	}
	return p_t;
}

LL dp[45][1<<16];

int main(){
	int n,m;
	int x,y,z;
	LL a,b,c;
	int i,j,k;
	cin>>n>>x>>y>>z;
	m=x+y+z-1;
	dp[0][0]=1;
	for(i=0;i<n;i++){
		for(j=0;j<(1<<m);j++){
			for(k=0;k<10;k++){
				a=((j<<1)+1)<<k;
				b=a&((1<<m)-1);
				if((a&(1<<m))&&(a&(1<<(m-x)))&&(a&(1<<(m-x-y))))continue;
				dp[i+1][b]+=dp[i][j];
				if(dp[i+1][b]>=MAX)dp[i+1][b]%=MAX;
			}
		}
	}
	for(i=0,a=0;i<(1<<m);i++){
		a+=dp[n][i];
		if(a>=MAX)a%=MAX;
	}
	LL s=pow_mod(10,n,MAX);
	s-=a;
	if(s<0)s+=MAX;
	cout<<s<<endl;
	return 0;
}

Submission Info

Judge Result