鄱阳电商网站建设_上海it培训机构_巩义网站推广优化_网络推广工作

题意：
你想要把$n$堆石子都变为0，你可以进行两种操作：1.从一堆里面取走至少两个石子；2.在一个>=3的线段里面每堆取走一个。现在每堆石子的个数可能是$[L_i,R_i]$中的一个，问有多少种可能性，使得添加恰好$k$个石子后能够用操作变为0。

思路

很有趣的一道题，但是我无法独立完成。重要的性质我基本都观察到了，不过我考虑状态的时候出现了一些问题，主要就是基本功不够，无法再推下去了。所以只好去洛谷看了看题解，第二天再想就感觉豁然开朗了。

首先是大方向的确定，有个高中省队同学就是在考场上面搞错了方向，他以为是有一个特殊的结论。但是这很明显是不正确的，因为你只要手玩一下，观察怎么样才可能把石子删除，你就会发现这里面涉及到非常复杂的东西，基本上不可能用结论来概括，所以要考虑用dp。

因为k的恰好很麻烦，但是我们很容易发现能将其变成至少，只要特判k=1，全0，或者3个1的情况即可。

我们考虑前$i$个，思考其对后面的影响。就会发现其可能以某几种形态对后面产生影响，可以设置两个维度，$j$表示必须延申到$i+1$的段数，$k$表示必须延申到$i+2$的段数。

然后有一下几个结论：
(1)一个点覆盖次数<=3
(2)不可能某个点作为3个覆盖的开始或者结束
(3)不可能两个同时延申到4；
(4)>=5的数影响一样；
然后就有8种可能。

很显然，因为$k$不会被统计进方案，因此状态还需要到达每一种可能所需的石子数。这个状态看上去是$100^8$，但是不同形态之间可以用极少石子使其转换成另一种形态，我们爆搜一下，发现状态很少，直接dp就可以了。

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
using namespace std;
template<typename T>inline void qr(T &x){x=0;int f=0;char s=getchar();while(!isdigit(s))f|=s=='-',s=getchar();while(isdigit(s))x=x*10+s-48,s=getchar();x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){if(x<0)putchar('-'),x=-x;do{buf[++cc]=int(x%10);x/=10;}while(x);while(cc)putchar(buf[cc--]+'0');
}
const int N=1e3+10,S=6770,mod=1e9+7;
struct node{int x,y;node(int xx=0,int yy=0):x(xx),y(yy){}
};
vector<node>statu;int id[5][5];
map<vector<int>, int>mp;int cnt,val[S];vector<int>c[S];
int to[S][7];
int n,m,a[N],b[N];
int dp[N][S];
int dfs(vector<int>now){if(mp.find(now)!=mp.end())return mp[now];mp[now]=++cnt;val[cnt]=now[0];c[cnt]=now;int current=cnt;rep(num,0,5){vector<int>nxt(8, 101);rep(i,0,7)if(now[i]!=101){int x=statu[i].x;int y=statu[i].y;rep(t1,0,min(x,1)){rep(t2,0,2)if(x+y+t2<=3&&y+t1<=3&&id[y+t1][t2]!=-1){if(num<x+y+t2){int nd=x+y+t2-num;if(now[i]+nd<101)nxt[id[y+t1][t2]]=min(nxt[id[y+t1][t2]],now[i]+nd);}else if(num==x+y+t2||num>x+y+t2+1){nxt[id[y+t1][t2]]=min(nxt[id[y+t1][t2]],now[i]);}else{if(now[i]+1<101)nxt[id[y+t1][t2]]=min(nxt[id[y+t1][t2]],now[i]+1);}}}}to[current][num]=dfs(nxt);}return current;
}
void ad(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
void solve(){qr(n),qr(m);rep(i,1,n)qr(a[i]),qr(b[i]);memset(dp,0,sizeof(dp));dp[0][1]=1;rep(i,0,n-1){rep(j,1,cnt)if(dp[i][j]){rep(k,a[i+1],min(4,b[i+1])){ad(dp[i+1][to[j][k]],dp[i][j]);}if(b[i+1]>=5){int t=b[i+1]-max(5,a[i+1])+1;ad(dp[i+1][to[j][5]],1ll*dp[i][j]*t%mod);}}}int ans=0;rep(i,1,cnt)if(dp[n][i]){if(val[i]<=m)ad(ans,dp[n][i]);}if(m==1){bool bk=1;rep(i,1,n)if(a[i])bk=0;if(bk){ans--;if(ans<0)ans+=mod;}if(n==3){bk=1;rep(i,1,n){if(a[i]<=1&&b[i]>=1)continue;bk=0;}if(bk){ans--;if(ans<0)ans+=mod;}}}qw(ans);puts("");
}
int main(){// freopen("stone4.in","r",stdin);// freopen("stone4.out","w",stdout);rep(i,0,3)rep(j,0,3)id[i][j]=-1;rep(i,0,2)rep(j,0,2){if(i+j<=3){id[i][j]=statu.size();statu.push_back(node(i,j));}}vector<int>st(8, 101);st[0]=0;dfs(st);int tt;qr(tt);while(tt--)solve();return 0;
}