Vertex Cover 湘潭CCPC邀请赛 （递推）

链接：https://ac.nowcoder.com/acm/contest/1107/J 来源：牛客网  

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K Special Judge, 64bit IO Format: %lld

题目描述

Alice and Bobo are playing a game on a graph with n vertices numbered with 0,1,…,(n−1)0, 1, \dots, (n - 1)0,1,…,(n−1). The vertex numbered with i is associated with weight 2i2^i2i. The game is played as follows. Firstly, Alice chooses a (possibly empty) subset of the n(n−1)2\frac{n(n - 1)}{2}2n(n−1)​ edges. Subsequently Bobo chooses a (possibly empty) subset of the n vertices to *cover* the edges chosen by Alice. An edge is *covered* if one of its two ends is chosen by Bobo. As Bobo is smart, he will choose a subset of vertices whose sum of weights, denoted as S, is minimum. Alice would like to know the number of subsets of edges where Bobo will choose a subset whose sum of weights is exactly k (i.e. S = k), modulo (109+7)(10^9+7)(109+7).

输入描述:

The input consists of several test cases and is terminated by end-of-file. Each test case contains two integers n and k. For convenience, the number k is given in its binary notation.

输出描述:

For each test case, print an integer which denotes the result.

示例1

输入

复制

3 1 4 101 10 101010101

输出

复制

3 12 239344570

备注:

* 1≤n≤1051 \leq n \leq 10^51≤n≤105 * 0≤k<2n0 \leq k < 2^n0≤k<2n * The sum of n does not exceed 250,000.

 

          假设这个点是1，则他只能和所有之前不是1的点相连（否则就不满足最小化覆盖的要求了），如果他是0，则他能和所有之前是1的点相连（否则的话也不满足全覆盖的要求）。

#include<bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; #define ll long long ll sum[100010]; int main() { sum[0] = 1; int n; for (int i = 1; i < 100010; i++) sum[i] = (sum[i - 1] * 2) % mod; string m; while (cin >> n >> m) { ll res = 1; int len = m.length(); int pre = n - len, la = 0; for (int i = 0; i < len; i++, pre++) { if (m[i] == '1') { res = res * (sum[pre] - sum[la++] + mod) % mod; } else { res = res * sum[la] % mod; } } cout << res << "\n"; } return 0; } //1 2 3 4