2019湖南省赛 D Modulo Nine（DP）

题意：
n位数，给定m个区间使得任意区间数乘积为9的倍数，求多少种构造方法。

思路：
要使得区间数的乘积为9的倍数，至少得2个3/6，或者1个0/9。
定义$f[i][j][k]$代表到了第$i$位时，最后两个符合条件的数$j,k,j\ge k$的位置。

对于每个区间，设置$L[i]$代表第$i$个位置的最小区间的左下标。因为相同右下标的区间，左下标更大肯定还是都成立，而且区间越小方案数相对越多。

那么对于第$i$个位置，
可以填 3/6，那么

1. 第$i$个位置填1/2/4/5/7/8
   $f[i][j][k]=(f[i][j][k]+f[i-1][j][k]\ast 6);$
2. 第$i$个位置填 3/6
   $f[i][i][j]=(f[i][i][j]+f[i-1][j][k]\ast 2);$
3. 第$i$个位置填 0/9
   $f[i][i][i]=(f[i][i][i]+f[i-1][j][k]\ast 2);$

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>using namespace std;typedef long long ll;const int mod = 1e9 + 7;ll L[55],f[55][55][55];int main() {int n,m;while(~scanf("%d%d",&n,&m)) {memset(L,0,sizeof(L));memset(f,0,sizeof(f));for(int i = 1;i <= m;i++) {ll l,r;scanf("%lld%lld",&l,&r);L[r] = max(L[r],l);}f[0][0][0] = 1;for(int i = 1;i <= n;i++) {for(int j = L[i - 1];j <= i;j++) {for(int k = L[i - 1];k <= j;k++) {f[i][j][k] = (f[i][j][k] + f[i - 1][j][k] * 6 % mod) % mod;f[i][i][j] = (f[i][i][j] + f[i - 1][j][k] * 2 % mod) % mod;f[i][i][i] = (f[i][i][i] + f[i - 1][j][k] * 2 % mod) % mod;}}}ll ans = 0;for(int i = L[n];i <= n;i++) {for(int j = L[n];j <= i;j++) {ans = (ans + f[n][i][j]) % mod;}}printf("%lld\n",ans);}return 0;
}