HNCPC2019自我补题

C.Distinct Substrings

算法:exmp 或者 SAM（待学习）

D. Modulo Nine

题目大意:

给你一个长度为n($n\le 50$)的十进制 整数。然后给你m($m\le 50$)个区间。每个区间的数位累乘 是 9的倍数。问你有多 少种合法的填写方案(mod 1e9 + 7)?

题目思路:

一个显然的条件:对于一个区间[L,R].只需要区间内含有两个含3因子的数即可。 那么令 $dp(i,j,k)$ 代表前i位,离i最近的两个含有3因子的数的位置j,k的合法方案。

一个确定的状态$(i,j,k)$,它的前导状态不太好确定。但是$(i,j,k)$可以 通过下一位填$\{1,2,4,5,7,8\}$转移到$(i+1,j,k)$ 通过下一位填$\{3,6\}$ 转移到$(i+1,k,i+1)$ 通过下一位填$\{0,9\}$转移到$(i+1,i+1,i+1)$ 所以利用刷表法。对于一个状态,当该状态有方案且若 在一个区间的右端点时，j,k都在L右边。则可以转移到下一个状态。 AC代码:

#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pb push_back #define mp make_pair using namespace std; const int mod = 1e9 + 7; ll dp[55][55][55] , l[55]; int main() { ios::sync_with_stdio(false); int n , m; while (cin >> n >> m){ memset (dp , 0 , sizeof dp); memset (l , 0 , sizeof l); for (int i = 1; i <= m ; i++){ ll x , y; cin >> x >> y; l[y] = max (l[y] , x); } dp[0][0][0] = 1; for (int i = 0 ; i < n ; i++){ for (int j = 0; j <= i ; j++){ for (int k = j; k <= i ; k++){ if (dp[i][j][k] == 0) continue; if (l[i] <= j && l[i] <= k){ dp[i + 1][j][k] = (dp[i + 1][j][k] + 6 * dp[i][j][k] % mod) % mod; dp[i + 1][k][i + 1] = (dp[i + 1][k][i + 1] + 2 * dp[i][j][k] % mod) % mod; dp[i + 1][i + 1][i + 1] = (dp[i + 1][i + 1][i + 1] + 2 * dp[i][j][k] % mod) % mod; } } } } ll ans = 0; for (int i = l[n] ; i <= n ; i++) for (int j = i; j <= n ; j++) ans = (ans + dp[n][i][j]) % mod; cout << ans << endl; } return 0; }