https://codeforc.es/contest/1185/problem/G1
不难想到用二进制表示第i首歌选还是不选，d[s][t]表示当状态为s且最后一首歌的类型为t的方案数。
1 #define bug(x) cout<<#x<<" is "<<x<<endl 2 #define IO std::ios::sync_with_stdio(0) 3 #include <bits/stdc++.h> 4 #define iter ::iterator 5 //#define pa pair<int,int> 6 using namespace std; 7 #define ll long long 8 #define mk make_pair 9 #define pb push_back 10 #define se second 11 #define fi first 12 #define ls o<<1 13 #define rs o<<1|1 14 ll mod=1e9+7; 15 const int inf=2e9+10; 16 const int N=(1<<15)+5; 17 int n,T; 18 ll d[N][4]; 19 int t[20],g[20]; 20 ll cal(ll x,ll y){ 21 ll res=1; 22 while(y){ 23 if(y&1)res=res*x%mod; 24 x=x*x%mod; 25 y>>=1; 26 } 27 return res; 28 } 29 int main(){ 30 IO; 31 cin>>n>>T; 32 for(int i=0;i<n;i++){ 33 cin>>t[i]>>g[i]; 34 } 35 int mx=(1<<n); 36 //d[0][1]=d[0][2]=d[0][3]=1; 37 d[0][0]=1; 38 for(int s=0;s<mx;s++){ 39 for(int i=0;i<=3;i++){ 40 for(int j=0;j<n;j++){ 41 if(!((s>>j)&1)){ 42 if(g[j]!=i){ 43 int ns=s^(1<<j); 44 d[ns][g[j]]=(d[ns][g[j]]+d[s][i])%mod; 45 //printf("ns=%d d=%d\n",ns,d[ns][g[j]]); 46 } 47 } 48 } 49 } 50 } 51 ll ans=0; 52 for(int s=0;s<mx;s++){ 53 int x=s; 54 int h=0; 55 int res=0; 56 while(x){ 57 if(x&1)res+=t[h]; 58 x>>=1; 59 h++; 60 } 61 if(res==T){ 62 for(int j=1;j<=3;j++){ 63 //printf("s=%d d=%d\n",s,d[s][j]); 64 ans=(ans+d[s][j])%mod; 65 } 66 } 67 } 68 cout<<ans<<endl; 69 }