04月25日, 2016 1,859 views次
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：多做难题，少做水题，才能提高…
