Link

传送门

Problem

For a sequence a of n integers between 1 and m, inclusive, denote f(a) as the number of distinct subsequences of a (including the empty subsequence).

You are given two positive integers n and m. Let S be the set of all sequences of length n consisting of numbers from 1 to m. Compute the sum f(a) over all a in S modulo 109 + 7.

The only line contains two integers n and m (1 ≤ n, m ≤ 106) — the number of elements in arrays and the upper bound for elements.

Print the only integer c — the desired sum modulo 109 + 7.

Mean

设f(a)为串a的不同子串(可空)的个数。求长度为N,最多M种字符的所有字符串的f(a)之和。

Analysis

参考网上题解做的,理解了好一会…

dp[i][j]表示长度为i,以字符j结尾的答案是多少,pre[j]为之前字符j的位置

dp[i][j]=sigma(dp[i-1][k]*2-dp[pre[j]-1][k])

然后这个玩意儿显然对于任意的j的都是一样的,而且pre[j]前面的每个位置都是可能的,这里的dp是个前缀和,所以直接扣除就可以了

那么直接化简为:dp[i]=dp[i-1]*(2m-1)

但是这个dp是没有考虑空串的

那么在加上空串就好了,所以答案就是

dp[i] = dp[i-1]*(2m-1)+m^(i-1)

我的理解是:

长度为i时,相当于对长度为i-1串添加一个字符(有m种情况),那么就是dp[i]=dp[i-1]*2m。但是添加字符后计算的子串跟之前有重复,总数量是dp[i-1]。但是扣除的这些中又多扣除了空串,所以加上长为i-1时所有串的数量(即空串数量),有m^(i-1)个。

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll mod = 1e9+7;

int main() {
    ll N, M; cin >> N >> M;
    ll ans = 2 * M, tmp = 1;
    for(int i = 2; i <= N; ++i) {
        tmp = (tmp * M) % mod;
        ans = (ans * (2 * M - 1) + tmp) % mod;
    }
    cout << ans << endl;
    return 0;
}

PS:多做难题,少做水题,才能提高…

欢迎留言