Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define Gene template< class
- #define Rics printer& operator,
- Gene c> struct rge{c b, e;};
- Gene c> rge<c> range(c i, c j){ return {i, j};}
- struct printer{
- ~printer(){cerr<<endl;}
- Gene c >Rics(c x){ cerr<<boolalpha<<x; return *this;}
- Rics(string x){cerr<<x;return *this;}
- Gene c, class d >Rics(pair<c, d> x){ return *this,"(",x.first,", ",x.second,")";}
- Gene ... d, Gene ...> class c >Rics(c<d...> x){ return *this, range(begin(x), end(x));}
- Gene c >Rics(rge<c> x){
- *this,"["; for(auto it = x.b; it != x.e; ++it)
- *this,(it==x.b?"":", "),*it; return *this,"]";}
- };
- #define debug() cerr<<"LINE "<<__LINE__<<" >> ", printer()
- #define dbg(x) "[",#x,": ",(x),"] "
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- int my_rand(int l, int r) {
- return uniform_int_distribution<int>(l, r) (rng);
- }
- const int N = 5e6+10, M = 20;
- const int mod = 1e9+7;
- int C[M][M];
- int dp[N][2][11];
- int main() {
- // freopen("in.txt", "r", stdin);
- ios::sync_with_stdio(0);
- cin.tie(0);
- int n, m;
- cin >> n >> m;
- string s;
- cin >> s;
- s = "$" + s;
- vector<int> sub(n+1);
- for(int u = n; u >= 1; u--) {
- vector<int> ways(m+1);
- dp[u][0][0] = 1;
- if(s[u] == '0') dp[u][1][1] = 1;
- sub[u] = 1;
- for(int v : {2*u, 2*u+1}) {
- if(v > n) continue;
- vector<int> newDp0(m+1), newDp1(m+1);
- for(int x = 0; x <= m && x <= sub[u]; x++) {
- for(int y = 0; x+y <= m && y <= sub[v]; y++) {
- newDp0[x+y] += 1ll*dp[u][0][x]*(dp[v][0][y]+dp[v][1][y])%mod;
- newDp1[x+y] += 1ll*dp[u][1][x]*dp[v][0][y]%mod;
- if(newDp0[x+y] >= mod) newDp0[x+y] -= mod;
- if(newDp1[x+y] >= mod) newDp1[x+y] -= mod;
- }
- }
- sub[u] += sub[v];
- for(int k = 0; k <= m; k++) dp[u][0][k] = newDp0[k], dp[u][1][k] = newDp1[k];
- }
- // debug(), dbg(dp[u]);
- }
- for(int i = 0; i < M; i++) {
- C[i][0] = C[i][i] = 1;
- for(int j = 1; j < i; j++) {
- C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod;
- }
- }
- int totalWays = 0;
- for(int k = 1; k <= m; k++) {
- int ways = (dp[1][0][k]+dp[1][1][k])%mod;
- ways = 1ll*ways*C[m-1][k-1]%mod;
- totalWays += ways;
- totalWays %= mod;
- }
- cout << totalWays << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement