UTPC 2014 G 唯一の組み合わせ

最後の200点問題
解説スライドを見て，回答．

問題文
http://utpc2014.contest.atcoder.jp/tasks/utpc2014_g

解法
dp[何番目][0~Xが何通りか]=選び方
0~Xが何通りかは0,1,2以上の3状態を保っておけばよい．あとは，0が0通りは存在しないので除外している．
この方針でdpをしていくのだがTLEする可能性があるので，状態遷移はあらかじめ前計算しておく．

計算量は 遷移先の前処理計算部分で O(PX3^X) DP部分で O(NP3^X)

ソースコードは以下の通り

const int magic=59049*2;

int nexts[magic][11];
vi ans[11];

void prepro(){
	rep(mask,magic){
		int state[11]; state[0]=1;
		int cur=mask;
		if(cur%2==1) state[0]++;
		cur/=2;
		for(int i=1;i<=10;++i) state[i]=cur%3,cur/=3;
		for(int i=1;i<=10;++i) if(state[i]==1) ans[i].pb(mask);
		rep(i,11){
			int nstate[11];
			rep(j,11) nstate[j]=state[j];
			rep(j,11) if(j+i<=10) nstate[j+i]+=state[j];
			rep(j,11) nstate[j]=min(nstate[j],2);
			int encode=0;
			rep(j,10) encode+=nstate[j+1]*pow(3,j)*2;
			encode+=nstate[0]-1;
			nexts[mask][i]=encode;
		}
	}
	return;
}

ll dp[55][magic];
const ll mod=1000000007;

int a[55];

int main(void){
	int n,x,p;
	cin >> n >> x >> p;
	dp[0][0]=1LL;
	rep(i,n){
		string in;
		cin >> in;
		if(in=="?")
			a[i]=-1;
		else
			a[i]=stoi(in);
	}
	prepro();
	rep(i,n)rep(j,magic){
		if(a[i]==-1){
			rep(k,p+1){
				dp[i+1][nexts[j][k]]+=dp[i][j];
				dp[i+1][nexts[j][k]]%=mod;
			}
		}else{
			int cur=a[i];
			dp[i+1][nexts[j][cur]]+=dp[i][j];
			dp[i+1][nexts[j][cur]]%=mod;
		}
	}
	ll res=0;
	for(auto &i:ans[x]) res+=dp[n][i],res%=mod;
	cout << res << endl;
	return 0;
}