Submission #2749187


Source Code Expand

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

ll mod_pow(ll a,ll n){
  ll res=1;
  while(n>0){
    if(n&1)res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll fac[100010],finv[100010];

ll comb(ll n,ll r){
  if(n<0||r<0||n<r)return 0;
  return (fac[n]*finv[r]%mod)*finv[n-r]%mod;
}

ll n,m;
ll a[22];
ll dp[20][1<<16];

int main(){
  fac[0]=1;
  rep(i,100000)fac[i+1]=fac[i]*(i+1)%mod;
  rep(i,100001)finv[i]=mod_pow(fac[i],mod-2);

  cin>>n>>m;
  ll tot=1<<n;
  rep(i,m)cin>>a[i];
  sort(a,a+m);
  reverse(a,a+m);
  dp[0][0]=1;
  rep(i,m){
    rep(S,1<<n){
      ll sz=0;
      rep(j,n)if((S>>j)&1)sz+=(1<<j);
      rep(j,n){
        if((S>>j)&1)continue;
        (dp[i+1][S|(1<<j)]+=((dp[i][S]*comb(tot-a[i]-sz,(1<<j)-1))%mod)*fac[(1<<j)]%mod)%=mod;
      }
      (dp[i+1][S]+=dp[i][S])%=mod;
    }
  }
  ll res=0;
  rep(S,1<<n){
    ll sgn=(bcnt(S)%2==0?+1:-1);
    ll sz=0;
    rep(i,n){
      if((S>>i)&1)continue;
      sz+=(1<<i);
    }
    (dp[m][S]*=fac[sz])%=mod;
    (res+=sgn*dp[m][S]+mod)%=mod;
  }
  cout<<res*mod_pow(2,n)%mod<<endl;
  return 0;
}

Submission Info

Submission Time
Task F - Dark Horse
User yamad
Language C++14 (GCC 5.4.1)
Score 1100
Code Size 1708 Byte
Status
Exec Time 224 ms
Memory 11520 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.txt
All 1100 / 1100 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.txt
Case Name Status Exec Time Memory
01.txt 35 ms 8192 KB
02.txt 184 ms 9472 KB
03.txt 191 ms 11520 KB
04.txt 194 ms 11520 KB
05.txt 133 ms 7424 KB
06.txt 158 ms 9472 KB
07.txt 179 ms 9472 KB
08.txt 202 ms 11520 KB
09.txt 211 ms 11520 KB
10.txt 202 ms 11520 KB
11.txt 21 ms 2304 KB
12.txt 34 ms 2304 KB
13.txt 55 ms 5376 KB
14.txt 72 ms 5376 KB
15.txt 17 ms 1792 KB
16.txt 18 ms 3840 KB
17.txt 18 ms 3840 KB
18.txt 18 ms 5888 KB
19.txt 18 ms 3840 KB
20.txt 19 ms 9984 KB
21.txt 218 ms 11520 KB
22.txt 206 ms 11520 KB
23.txt 190 ms 11520 KB
24.txt 169 ms 11520 KB
25.txt 146 ms 7424 KB
26.txt 88 ms 5376 KB
27.txt 19 ms 5888 KB
28.txt 17 ms 1792 KB
29.txt 18 ms 5888 KB
30.txt 18 ms 3840 KB
31.txt 19 ms 7936 KB
32.txt 224 ms 11520 KB
33.txt 17 ms 1792 KB
34.txt 18 ms 3840 KB
35.txt 18 ms 5888 KB
36.txt 18 ms 7936 KB
sample-01.txt 17 ms 1792 KB
sample-02.txt 17 ms 1792 KB
sample-03.txt 17 ms 1792 KB
sample-04.txt 17 ms 1792 KB
sample-05.txt 221 ms 11520 KB