给出一个长度为n尾的数组,每一位可以填入一个0~9的整数.再给出m条限制,每条限制给出一个l和r.要求

\Pi _{i=l}^{r} a_{i} \equiv 0 (mod \ 9)

求有多少种满足方案的数列构造方法.

链接

题解

显然,可以填入的数分为三类:含有一个因子3的:3,6;两个因子3的:0,9;以及不含有因子3的.而当且仅当l到r这个区间中含有的因子3至少有两个,才可以满足限制条件.

对于同一个r,当最大的l所对应的限制条件被满足时,其他所有的以r限制条件都会被满足,这一结论是显然的.

考虑dp[i][j][k]表示构造到第i个位置时,上一个因子3出现在j位置,上上个因子3出现在k位置.然后从i向i+1转移.每次转移之前,需要判断i位置的状态是否合法,即能否满足限制条件的要求.具体的转移方程如代码所示.总的时间复杂度为

O(n^3)

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 55
#define MOD 1000000007
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int i,j,k,n,m,x,y;
LL Ans;
LL dp[N][N][N],l[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

int main(){
    while (~scanf("%d%d",&n,&m)){
        memset(l,0,sizeof(l));  memset(dp,0,sizeof(dp));
        for (i=1;i<=m;i++){
            scanf("%d%d",&x,&y);    l[y]=Max(l[y],x);
        }
        dp[0][0][0]=1;  Ans=0;
        for (i=0;i<n;i++)
            for (j=0;j<=i;j++)
                for (k=0;k<=j;k++){
                    if (k<l[i]) continue;
                    dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k]*6)%MOD;
                    dp[i+1][i+1][j]=(dp[i+1][i+1][j]+dp[i][j][k]*2)%MOD;
                    dp[i+1][i+1][i+1]=(dp[i+1][i+1][i+1]+dp[i][j][k]*2)%MOD;
                }
        for (j=0;j<=n;j++)
            for (k=0;k<=j;k++)
                if (k>=l[n]) Ans=(Ans+dp[n][j][k])%MOD;
        printf("%lld\n",Ans);
    }
    return 0;
}