（状压dp）2017 计蒜之道复赛 F. 腾讯消消乐

腾讯推出了一款益智类游戏——消消乐。游戏一开始，给定一个长度为 $A_iAi。$

游戏的目标是把这些数全都删去，每次删除的操作为：选取一段连续的区间，不妨记为

注意：一次删除以后，剩下的数会合并成为一个连续区间。

定义

你需要实现一个程序，计算 $sum_{i=1}^{n}{(f(i) ast i)} ext{ mod } 1000000007∑i=1n(f(i)∗i) mod 1000000007。$

输入格式

第一行输入两个整数

第二行输入 $a_i(1 le a_i le 10^5)ai(1≤ai≤105)，表示初始序列中的每个数。$

输入数据保证 $min(a_1,a_2,ldots a_n)1≤k≤min(a1,a2,…an)。$

输出格式

输出一个整数，表示算出的答案。

样例说明

对于样例 1 而言，

对于样例 2，

样例输入1

4 1
1 1 1 1

样例输出1

样例输入2

2 2
2 3

样例输出2

样例输入3

1 233
233

样例输出3

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <queue>
 8 #include <set>
 9 #include <map>
10 #include <list>
11 #include <vector>
12 #include <stack>
13 #define mp make_pair
14 //#define P make_pair
15 #define MIN(a,b) (a>b?b:a)
16 //#define MAX(a,b) (a>b?a:b)
17 typedef long long ll;
18 typedef unsigned long long ull;
19 const int MAX=1<<18;
20 const int MAX_V=6e4+5;
21 const ll INF=2e11+5;
22 //const double M=4e18;
23 using namespace std;
24 const ll MOD=1e9+7;
25 typedef pair<ll,int> pii;
26 const double eps=0.000000001;
27 #define rank rankk
28 inline ll gcd(ll a,ll b)
29 {
30     for(ll t=a%b;t;a=b,b=t,t=a%b);
31     return b;
32 }
33 ll dp[MAX][20],a[20],an;
34 int n,k;
35 int nowgcd,st;
36 int main()
37 {
38     dp[0][0]=1LL;
39     scanf("%d%d",&n,&k);
40     for(int i=0;i<n;i++)
41         scanf("%lld",&a[i]);
42     int da=(1<<n)-1;
43     for(int i=0;i<=da;i++)
44     {
45         for(int j=0;j<n;j++)
46         {
47             st=0;
48             if(1&(i>>j))
49                 continue;
50             nowgcd=a[j];
51             for(int v=j;v<n;v++)
52             {
53                 if(1&(i>>v))
54                     continue;
55                 nowgcd=gcd(nowgcd,a[v]);
56                 if(nowgcd<k)
57                     break;
58                 st|=(1<<v);
59                 for(int q=1;q<=n;q++)
60                     dp[i|st][q]+=dp[i][q-1];
61             }
62         }
63     }
64     for(int i=1;i<=n;i++)
65         an=(an+((dp[da][i]%MOD)*i%MOD))%MOD;
66     printf("%lld
",an);
67     return 0;
68 }

（状压dp）2017 计蒜之道 复赛 F. 腾讯消消乐