CF1556F Sports Betting (状压枚举子集DP)

F

对于一张比赛图，经过缩点，会得到dag，且它一定是transitive的，因此我们能直接把比赛图缩成一个有向链。链头作为一个强连通分量，里面的所有点都是胜利的

定义F(win)表示win集合作为赢家的概率，我们有

\[ans=\sum_{win\in all} F(win)|win| \]

显然win集合内的点构成一个强连通分量，并作为链头。win集合内的点一定向集合外的每个点连边

考虑如何求解F(win)

我们定义H(win)表示在win集合内的点构成的子图中，win集合成为一个强连通分量的概率。

容易发现这个子图仍然满足比赛图的性质！

考虑去掉win不是一个强连通分量的情况，那么一定存在win的非空真子集sub，sub是子图链头，此时 sub内的所有点向 win/sub内的所有点连边。我们得到

\[H(win)=1-\sum_{sub\subset win,sub\ne \phi}H(sub)G(sub,win/sub) \]

其中\(G(x,y)\)表示x集合向y集合的点直接连边的概率

求出的H可以推F了，win想每个集合外的点连边

\[F(win)=G(win,all/win)H(win) \]

接下来考虑如何求出G

原题n=14，可以接受\(O(n3^{n})\)的做法，我们预处理出每个点连向一个集合的概率\(f(i,s)\)，那么每次调用G的时间是\(O(n)\)

题解提供了一个\(O(3^{n})\)的方法，让每次调用G是\(O(1)\)的

首先是预处理每个点连向集合的概率，我们处理出每个数最高位的1的位置，就可以在\(O(n2^{n})\)递推出\(f(i,s)\)

考虑把n分成大小不超过1的两个集合left,right

现在有一个询问\(G(x,y)\)，x,y分别在left和right集合内存在一部分lx,ly,rx,ry，答案是

\(G(x,y)=G(lx,ly)G(lx,ry)G(rx,ly)G(rx,ry)\)

这四部分贡献可以分别预处理，由于left和right的大小只有原来的一半，每个数组处理的时间只有\(O(n2^{n})\)

tips：经可可提醒，这个优化套路在[ctsc2017]吉夫特，有机会去做一下

#include

using namespace std;

#define r(x) read(x)
#define gc c=getchar()
#define ll long long
#define ffl fflush(stdout)
#define it set::iterator 

const int N1=(1<<14)+5, p=1e9+7, maxn=2e6;
const int M1=(1<<7)+5;
const ll inf=0x3f3f3f3f3f3f3fll;
template
inline void read(T &x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

int n,m,L,R;
int a[16],bcnt[N1],lg[N1];
ll F[N1],f[16][N1],H[N1],inv[maxn+5];
ll gl[M1][M1],gr[M1][M1],glr[M1][M1],grl[M1][M1];

ll G(int X,int Y){
    int lx=X&L, rx=(X&R)>>m, ly=Y&L, ry=(Y&R)>>m;
    return gl[lx][ly]*gr[rx][ry]%p*glr[lx][ry]%p*grl[rx][ly]%p;
}
// inline int lowbit(int x){ return x&(-x); }

int main(){
    // freopen("1.in","r",stdin);
    // freopen(".out","w",stdout);
    // int Te; read(Te);
    // while(Te--) printf("%lld\n",solve());
    read(n); 
    if(n==1){ puts("1"); return 0; }
    for(int i=0;i>1]+1;
    for(int s=1;s<(1<>1]+(s&1);
    // for(int s=0;s<(1<>m);rx++){
        int s=(R>>m)^rx;
        for(int t=s;;t=(t-1)&s){
            gr[rx][t]=1;
            for(int i=0;i>m);ry++){
            glr[lx][ry]=1;
            for(int i=0;i>m);rx++){
        for(int ly=0;ly<=L;ly++){
            grl[rx][ly]=1;
            for(int i=0;i


						
							

						
							
							
			OJCodeforces动态规划状压DP

CF1556F Sports Betting (状压枚举子集DP)

F

相关

标签