频道栏目
首页 > 考试 > 其他 > 正文

[容斥 状压DP] Atcoder ARC093 F - Dark Horse

2018-03-26 11:22:19         来源:CE玩家  
收藏   我要投稿

[容斥 状压DP] Atcoder ARC093 F - Dark Horse。

假设我们确定的1的位置,那么接下来的每一轮,1都会和一段长度为2的幂的区间里,标号最小的人pk。

把1固定在1位置(求出最终方案数后乘上 2n" role="presentation">2n 就是答案),那么就相当于区间 [2,2]" role="presentation">[2,2][3,4]" role="presentation">[3,4][5,8]" role="presentation">[5,8][2n1+1,2n]" role="presentation">[2n?1+1,2n] 里的最小值不在给出的集合中

考虑容斥,那么就只要求出标号在集合 S" role="presentation">S 中的区间的最小值在给出的集合中,其他区间随便放的方案数就可以了

ai" role="presentation">ai 从大到小排序,令 fi,S" role="presentation">fi,S 表示前 i" role="presentation">i 个人,集合 S" role="presentation">S 中的区间的最小值在 a" role="presentation">a 中的最小值

因为把 ai" role="presentation">ai 从大到小排序了,所以每次转移只要算出之前用了多少人,乘个组合数就可以了

#include 
#include 
#include 

using namespace std;

const int N=20,P=1e9+7;

int n,m,p,a[N],f[N][1<<16|5],fac[1<<16|5],inv[1<<16|5];

inline int C(int x,int y){
  if(x>(j-1)&1) cnt+=pw[j-1];
      int rst=p-a[i]-cnt;
      for(int j=1;j<=n;j++)
    if(S>>(j-1)&1);else{
      if(pw[j-1]-1>rst) continue;
      add(f[i][S|(1<>(j-1))&1) cnt+=pw[j-1],tot++;
    cur=1LL*cur*fac[p-cnt-1]%P;
    if(tot&1) ans=(ans-cur)%P;
    else ans=(ans+cur)%P;
  }
  ans=1LL*ans*p%P;
  printf("%d\n",(ans+P)%P);
  return 0;
}
上一篇:Convert Sorted List to Binary Search Tree
下一篇:编程开发习题 -- 分巧克力
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站