腾讯消消乐（状态压缩DP）

腾讯消消乐

题意

给出长度为 n 的序列，每次可以选择删除序列的一个连续区间，要求这一段区间内所有数最大公约数不小于 k ，删除后剩下的序列仍然构成连续序列。

定义 f(i) 为进行 i 次操作将整个序列删完的方案数。计算 $\sum_{i=1}^{n}{(f(i) \ast i)} \text{ mod } 1000000007 $。

分析

dp[s][i] 表示 s 这个状态需要 i 次删完的方案数（s 表示这个数是否存在的 01 串），状态转移就是 dp[s | t][i] += dp[s][i - 1]，那么加上的 dp[s][i - 1]表示最后一步操作是把 t 这个状态变为 0 的方案数。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 3e5;

const ll MOD = 1e9 + 7;

ll dp[MAXN][20];

int a[20];

int main() {

    int n, k;

    cin >> n >> k;

    for(int i = 0; i < n; i++) cin >> a[i];

    dp[0][0] = 1;

    int total = (1 << n) - 1;

    for(int s = 0; s <= total; s++) {

        for(int l = 0; l < n; l++) {

            if((s >> l) & 1) continue;

            int t = 0;

            int gcds = 0;

            for(int r = l; r < n; r++) {

                if((s >> r) & 1) continue;

                if(__gcd(gcds, a[r]) < k) break;

                gcds = __gcd(gcds, a[r]);

                t |= (1 << r);

                for(int i = 1; i <= n; i++) {

                    dp[s | t][i] = (dp[s | t][i] + dp[s][i - 1]) % MOD;

                }

            }

        }

    }

    ll ans = 0;

    for(int i = 1; i <= n; i++) {

        ans = (ans + i * dp[total][i]) % MOD;

    }

    cout << ans << endl;

    return 0;

}

巴特西

腾讯消消乐（状态压缩DP）

腾讯消消乐

题意

分析

code

最新文章

热门文章

巴特西

腾讯消消乐 （状态压缩DP）

腾讯消消乐

题意

分析

code

最新文章

热门文章

腾讯消消乐（状态压缩DP）