ARC093 F - Dark Horse

https://atcoder.jp/contests/arc093/tasks/arc093_d

题解

先钦定\(1\)号站在第一个位置上，那么他第一轮要和\((2)\)打，第二轮要和\((3,4)\)打，第三轮和\((5,6,7,8)\)打。

那么这些区间的最小值不能是给出的数。

考虑容斥。

我们把所有限制位置从大到小排序，设\(dp[i][s]\)表示前\(i\)个数，\(S\)集合中的区间已经被覆盖了的方案数。

那么我们每做到一个数，考虑把它放到一个没有被占用的区间，那么这个区间还能放的数的个数就是\((1<<n)-s-a[i]\)。

最后我们发现无论1站在哪都是一样的，所以乘上\(2^n\)就行了。

代码

#include<bits/stdc++.h>

#define N 17

using namespace std;

typedef long long ll;

const int mod=1e9+7;

int n,m,a[N];

ll jie[1<<N],ni[1<<N],dp[N][1<<N];

int cnt[1<<N];

inline ll rd(){

    ll x=0;char c=getchar();bool f=0;

    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    return f?-x:x;

}

inline void MOD(ll &x){x=x>=mod?x-mod:x;}

inline ll power(ll x,ll y){

    ll ans=1;

    while(y){if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}

    return ans;

}

inline ll C(int n,int m){return jie[n]*ni[m]%mod*ni[n-m]%mod;}

inline bool cmp(int a,int b){return a>b;}

int main(){

    n=rd();m=rd();

    for(int i=1;i<=m;++i)a[i]=rd();

    sort(a+1,a+m+1,cmp);

    int maxn=(1<<n);

    for(int i=1;i<=maxn;++i)cnt[i]=cnt[i-(i&-i)]+1;

    jie[0]=1;

    for(int i=1;i<=maxn;++i)jie[i]=jie[i-1]*i%mod;

    ni[maxn]=power(jie[maxn],mod-2);

    for(int i=maxn-1;i>=0;--i)ni[i]=ni[i+1]*(i+1)%mod;

    dp[0][0]=1;

    for(int i=1;i<=m;++i)

        for(int s=0;s<(1<<n);++s)if(dp[i-1][s]){

            MOD(dp[i][s]+=dp[i-1][s]);

            for(int j=0;j<n;++j)if(!(s&(1<<j))){

                MOD(dp[i][s|(1<<j)]+=dp[i-1][s]*jie[1<<j]%mod*C(maxn-a[i]-s,(1<<j)-1)%mod);

            }

        }

    ll ans=0;

    for(int s=0;s<(1<<n);++s){

        if(cnt[s]&1)MOD(ans=ans-dp[m][s]*jie[maxn-1-s]%mod+mod);

        else MOD(ans=ans+dp[m][s]*jie[maxn-1-s]%mod);

    }

    printf("%lld\n",ans*maxn%mod);

    return 0;

}

巴特西

ARC093 F - Dark Horse

题解

代码

最新文章

热门文章