腾讯消消乐
题意
给出长度为 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;
}内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
