Submission #373156

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
ll p3[13];
int To_int(string s){
	istringstream is(s);
	int ret;
	is>>ret;
	return ret;
}
vector<int> vs;
int al[11];
int cnt[11];
ll mod=1e9+7;
void add(ll &x,ll y){
	x+=y;
	x%=mod;
}
int ne[177147*3][11];
ll dp[177147*3],ndp[177147*3];
int main(){
	p3[0]=1;
	rep(i,12) p3[i+1]=p3[i]*3;
	int n,x,p,tso=0;
	cin>>n>>x>>p;
	cin.ignore();
	rep(i,n){
		string s;
		cin>>s;
		if(s[0]=='?') tso++;
		else vs.pb(To_int(s));
	}
	sort(all(vs));
	if(!vs.empty()&&vs[0]==0){
		puts("0");
		return 0;
	}
	al[0]=1;
	for(int v:vs){
		for(int j=x;j>=0;j--){
			if(j+v<=x) al[j+v]=min(al[j+v]+al[j],2);
		}
	}
//	rep(i,x+1) cout<<i<<" "<<al[i]<<endl;
	n=tso;
	dp[1]=1;
	rep(i,p3[x+1]){
		rep1(j,p){
			int a[11]={};
			int tmp=i;
			rep(k,x+1){
				a[k]=tmp%3;
				tmp/=3;
			}
			for(int k=x;k>=0;k--){
				if(k+j<=x) a[k+j]=min(a[k+j]+a[k],2);
			}
			int s=0;
			for(int k=x;k>=0;k--){
				s*=3;
				s+=a[k];
			}
			ne[i][j]=s;
		}
	}
	rep(i,n){
		for(int j=p3[x+1]-1;j>=0;j--){
			rep1(k,p){
				add(ndp[ne[j][k]],dp[j]);
			}
		}
		rep(j,p3[x+1]) dp[j]=ndp[j],ndp[j]=0;
	}
	ll ans=0;
	rep(i,p3[x+1]){
		int a[11]={};
		int tmp=i;
		rep(k,x+1){
			a[k]=tmp%3;
			tmp/=3;
		}
		int sum=0;
//		show(i);
		rep(j,x+1){
			sum+=a[j]*al[x-j];
		}
//		show(sum);
		if(sum==1) add(ans,dp[i]);
	}
	cout<<ans<<endl;
}

Submission Info

Judge Result