HDU-6285

Posted on | Edited on | In | Views:

题意

在一个 $n$ 个点的完全图中，第 $i$ 个点的权值为 $2^i$，选择一些边，需要选择一些点使得所有边至少有一个端点被覆盖，同时权值之和最小。
在上述情况下，给出选择的点的权值和，问有多少种选择边的方案符合这种选点。

题解

对于每一个选定的点, 总有一条边连着它和权值比它大的未被选的点, 设数量为 $cnt1$, 权值比它小的点可取可不取, 设数量为 $cnt2$, 则该点的贡献为

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
string s;

ll f[N];
ll fun(int a,int b){
    ll qq=(f[a]-1+mod)%mod;
    return qq*f[b]%mod;
}

int main() {
#ifdef PerpEternal
    // freopen("/Users/perpeternal/Documents/Sketch/data/in.dat", "r", stdin);
    // freopen("/Users/perpeternal/Documents/Sketch/data/out.dat", "w", stdout);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,a,b;
    f[0]=1;
    for1(i,100005){
        f[i]=f[i-1]*2%mod;
    }
    while(cin>>n>>s){
        a=b=0;
        ll ans=1;
        for(int i=0;i<s.size();i++){
            if(s[i]=='1')a++;
        }
        n-=s.size();
        for(int i=s.size()-1,j=0;i>=0;i--,j++){
            if(s[i]=='1'){
                b++;
                ans=fun(n+i-a+b,j)*ans%mod;
                // cout<<n+i-a+b<<' '<<j<<endl;
            }
        }
        outln(ans);
    }
    return 0;
}