本文共 862 字，大约阅读时间需要 2 分钟。

考虑这么多限制很不好做,而且区间可能彼此嵌套,无法同时满足限制

考虑一段区间乘机模$9$为零有什么特殊点.

其实就是分解质因子之后,至少有两个因子都为$3$

那么我们在第$i$位填充了$3,6$后,相当于在这个位置设置了一个因子$3$

我们在第$i$位填充了$9,0$后,相当于在这个位置设置了两个因子$3$

所以我们对于每个位置$i$,考虑它作为限制区间的右端点,那么若干个左端点只有最右的区间有用

所以我们定义$f[i][j][k]$表示填充了$[1,i]$的数字,且满足了所有右端点小于等于$i$的区间限制

最近出现的因子$3$为$k$位置,次近的是$j$位置

#include 
   
    using namespace std;#define int long longconst int mod = 1e9+7;const int maxn = 59;typedef pair
    
     p;int n,m,f[maxn][maxn][maxn],lim[maxn];signed main(){
   	while( cin >> n >> m )	{
   		for(int i=1;i<=m;i++)		{
   			int l,r; cin >> l >> r;			if( lim[r]==0 || lim[r]
     
      =lim[n] )	ans = ( ans+f[n][j][k] )%mod;		for(int i=0;i<=n;i++)		for(int j=0;j<=n;j++)		for(int k=0;k<=n;k++)			f[i][j][k] = 0;		memset( lim,0,sizeof lim );		cout << ans << endl;	}}
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116464223 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！