CC

自然万物都趋向从有序变得无序

0%

HDU 6327 Random Sequence（期望dp）

发表于 更新于 分类于 Valine：

题目链接

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 131 Accepted Submission(s): 41

Problem Description

There is a positive integer sequence a1,a2,…,an with some unknown positions, denoted by 0. >Little Q will replace each 0 by a random integer within the range [1,m] equiprobably. After that, he >will calculate the value of this sequence using the following formula :

∏i=1nv[gcd(ai,ai−1,ai−2,aui−3)]\prod_{i=1}^n v[gcd(a_i,a_{i-1},a_{i-2},a_{ui-3})]

Little Q is wondering what is the expected value of this sequence. Please write a program to >calculate the expected value.

Input

The first line of the input contains an integer T(1≤T≤10), denoting the number of test cases.
in each test case, there are 2 integers n,m(4≤n≤100,1≤m≤100) in the first line, denoting the length >of the sequence and the bound of each number.
In the second line, there are n integers a1,a2,…,an(0≤ai≤m), denoting the sequence.
In the third line, there are m integers v1,v2,…vm(1≤vi≤109), denoting the array v.

Output

For each test case, print a single line containing an integer, denoting the expected value. If the answer is A / B, please print C(0≤C<109+7) where A≡C×B(mod109+7).

Sample Input

2
6 8
4 8 8 4 6 5
10 20 30 40 50 60 70 80
4 3
0 0 0 0
3 2 4

Sample Output

8000
3

Source

2018 Multi-University Training Contest 3

题意:

给定一个数列，数列中为0的点表示这个地方可以取1 ～ m的任意一个数，给定上面所描述的累成的定义，求答案的期望值。

思路:

官方题解：

设 f(i,x,y,z)表示考虑前 i 个位置,
a(i) = x, gcd(a(i) , a(i-1) ) = y, gcd(a(i) , a(i−1) , a(i−2) ) = z 的期望。
枚举 a i+1 的值转移即可。
时间复杂度 O(nmS),其中 S 表示 (x, y, z) 的状态数。
显然合法状态中 y|x, z|y,当 m = 100 时 S = 1471。

根据官方的题解，明显我们开不下100 * 100 * 100 * 100 的数组，我们可以考虑滚动数组，因为f(i,x,y,z) 只与f(i-1, , , ,)的值有关，那么我们就可以开一个 2 * 100 * 100 * 100的数组。

那么我们应该怎么样枚举，如果我们暴力枚举的话，那么时间复杂度是n*(m ^ 4)。考虑优化，这题的关键是求gcd，那么我们可以枚举因子，一个数的因子个数不会有太多，再加上我们要枚举因子的因子，所以最坏情况下大概是1500的复杂度，完全可以接受。具体的细节实现可以看代码。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*************************************************************************
    > File Name: HDU6327.cpp
    > Author: wood
    > Mail: cbcruel@gmail.com
    > Created Time: 2018年07月31日 星期二 09时49分03秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<string>

using namespace std;
typedef long long LL;
#define sqr(x) (x)*(x)
const double eps = 1e-8;
const double C = 0.57721566490153286060651209;
const double pi = acos(-1.0);
const LL mod = 1e9 + 7;
const int maxn = 1e5 + 10;


LL dp[2][102][102][102];
int gd[102][102];
LL v[102];
int l[102],r[102];
vector<int> fac[102];

LL gcd(LL a, LL b){
    return b ? gcd(b,a%b) : a;
}

LL qpow(LL x, LL n){
    LL ans = 1;
    while(n){
        if(n&1) (ans *= x) %= mod;
        (x *= x) %= mod;
        n >>= 1;
    }return ans;
}


int main(){
    int t;
    for(int i = 1; i <= 100; ++i)
        for(int j = 1; j <= 100; ++j)
            gd[i][j] = gcd(i,j);
    scanf("%d", &t);
    while(t--){
        int n,m,x;
        int num = 0;
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; ++i){
            scanf("%d", &x);
            if(x) r[i] = l[i] = x;
            else l[i] = 1,r[i] = m, num++;
        }
        for(int j = 1; j <= m; ++j)
            scanf("%lld", &v[j]);
        memset(dp,0, sizeof dp);
        int now = 0;
        for(int i = l[3]; i <= r[3]; ++i)
            for(int j = l[2]; j <= r[2]; ++j)
                for(int k = l[1]; k <= r[1]; ++k)
                    dp[now][i][gd[i][j]][gd[k][gd[i][j]]]++;
        for(int ii = 4; ii <= n; ++ii){
            now ^= 1;
            for(int i = 1; i <= m; ++i)
                for(int j = i; j <= m; j+= i)
                    for(int k = j; k <= m; k += j){
                        if(dp[now^1][k][j][i] == 0) continue;
                        for(int t = l[ii]; t <= r[ii]; ++t)
                            (dp[now][t][gd[t][k]][gd[t][j]] += dp[now^1][k][j][i] * v[gd[t][i]] % mod)%=mod;
                        dp[now^1][k][j][i] = 0;
            }
        }
        LL ans = 0;
        for(int i = 1; i <= 100; ++i)
            for(int j = i; j <= 100; j += i)
                for(int k = j; k <= 100; k += j)
                    (ans += dp[now][k][j][i])%=mod;
        (ans *= qpow(qpow(m,mod-2), num)) %= mod;
        printf("%lld\n", ans%mod);
    }return 0;
}