p很小，讨论
p=0。。。
p=1。。。
p=2：n-1放左或者放右两种情况，剩下怎么放是固定的，模拟然后判断即可
p=3：
正着做要状压，类似放书和排座位那些题，考虑以某个顺序加入元素，不断扩充出整个环
不妨从n开始往下加，其实只用考虑i,i-1,i-2和要放的i-3的关系。i-3只能放在这三个的两个的中间，
所以这中间不能再有之前的i+1，i+2这种了。
而且区分左右还要记录顺逆
f[i][0/1][2^3]前i个，顺逆，相邻能不能放（是否紧相邻）
然后枚举放哪里转移，之后i会固定，看会不会和i-1,i-2,i-3冲突
转移时候大力分类讨论
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define reg register int #define il inline #define numb (ch^'0') using namespace std; typedef long long ll; il void rd(int &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=1000000+5; const int mod=1e9+7; int n,k,p; int no[N][7];//0:-3; 1:-2 ; 2:-1 ; 3:0 ; 4:1 ; 5:2 ; 6:3 int add(int x,int y){ return x+y>=mod?x+y-mod:x+y; } void sol0(){ if(n==1) puts("1"); else puts("0"); } void sol1(){ if(n==1||(n==2&&k==0)) puts("1"); else puts("0"); } int a[N]; void sol2(){ if(n<=2){ if(n==1||(n==2&&k==0)) puts("1"); else puts("0"); return; } int ans=0; a[1]=n; for(reg x=n-1,i=2;x>0;++i,x-=3) a[i]=x; for(reg x=n-2,i=n;x>0;--i,x-=2) a[i]=x; bool fl=true; for(reg i=1;i<n;++i){ if(no[a[i]][a[i+1]-a[i]+3]) fl=false; } if(no[a[n]][a[1]-a[n]+3]) fl=false; if(fl) ++ans; a[1]=n; for(reg x=n-2,i=2;x>0;++i,x-=2) a[i]=x; for(reg x=n-1,i=n;x>0;--i,x-=2) a[i]=x; fl=true; for(reg i=1;i<n;++i){ if(no[a[i]][a[i+1]-a[i]+3]) fl=false; } if(no[a[n]][a[1]-a[n]+3]) fl=false; if(fl) ++ans; printf("%d",ans); } int f[N][2][8]; int dis(int x,int y){ return y-x+3; } int mk(int s1,int s2,int s3){ return s3*4+s2*2+s1; } void calc(int i,int j,int s){//add i-1 int now=f[i][j][s]; int s1=s&1,s2=(s>>1)&1,s3=(s>>2)&1; if(i!=2){ if(j==0){//shun if(s1){ if(s3){ if(no[i][dis(i,i+2)]==0&&no[i+2][dis(i+2,i-1)]==0) f[i-1][j][mk(s2,0,1)]=add(f[i-1][j][mk(s2,0,1)],now); } else{ if(no[i+2][dis(i+2,i-1)]==0) f[i-1][j][mk(s2,0,1)]=add(f[i-1][j][mk(s2,0,1)],now); } } if(s2){ if((s1==0||no[i+2][dis(i+2,i+1)]==0)&&(s3==0||no[i][dis(i,i+2)]==0)) f[i-1][j^1][mk(0,1,1)]=add(f[i-1][j^1][mk(0,1,1)],now); } if(s3){ if((s1==0||no[i+2][dis(i+2,i+1)]==0)&&(no[i-1][dis(i-1,i+2)]==0)) f[i-1][j][mk(s2,1,0)]=add(f[i-1][j][mk(s2,1,0)],now); } } else{//j==1 if(s1){ if(s3){ if(no[i+2][dis(i+2,i)]==0&&no[i-1][dis(i-1,i+2)]==0) f[i-1][j][mk(s2,0,1)]=add(f[i-1][j][mk(s2,0,1)],now); } else{ if(no[i-1][dis(i-1,i+2)]==0) f[i-1][j][mk(s2,0,1)]=add(f[i-1][j][mk(s2,0,1)],now); } } if(s2){ if((s1==0||no[i+1][dis(i+1,i+2)]==0)&&(s3==0||no[i+2][dis(i+2,i)]==0)) f[i-1][j^1][mk(0,1,1)]=add(f[i-1][j^1][mk(0,1,1)],now); } if(s3){ if((s1==0||no[i+1][dis(i+1,i+2)]==0)&&(no[i+2][dis(i+2,i-1)]==0)) f[i-1][j][mk(s2,1,0)]=add(f[i-1][j][mk(s2,1,0)],now); } } }else{//las if(j==0){ if(s1){ if((s3==0||no[i][dis(i,i+2)]==0)&&(no[i+2][dis(i+2,i-1)]==0)&&(no[i-1][dis(i-1,i+1)]==0)&&(s2==0||no[i+1][dis(i+1,i)]==0)){ f[i-1][j][mk(0,0,0)]=add(f[i-1][j][mk(0,0,0)],now); } } if(s2){ if((s3==0||no[i][dis(i,i+2)]==0)&&(s1==0||no[i+2][dis(i+2,i+1)]==0)&&(no[i+1][dis(i+1,i-1)]==0&&no[i-1][dis(i-1,i)]==0)){ f[i-1][j^1][mk(0,0,0)]=add(f[i-1][j^1][mk(0,0,0)],now); } } if(s3){ if((s1==0||no[i+2][dis(i+2,i+1)]==0)&&(s2==0||no[i+1][dis(i+1,i)]==0)&&(no[i][dis(i,i-1)]==0&&no[i-1][dis(i-1,i+2)]==0)){ f[i-1][j][mk(0,0,0)]=add(f[i-1][j][mk(0,0,0)],now); } } } else{ if(s1){ if((s3==0||no[i+2][dis(i+2,i)]==0)&&(no[i-1][dis(i-1,i+2)]==0)&&(no[i+1][dis(i+1,i-1)]==0)&&(s2==0||no[i][dis(i,i+1)]==0)){ f[i-1][j][mk(0,0,0)]=add(f[i-1][j][mk(0,0,0)],now); } } if(s2){ if((s3==0||no[i+2][dis(i+2,i)]==0)&&(s1==0||no[i+1][dis(i+1,i+2)]==0)&&(no[i-1][dis(i-1,i+1)]==0&&no[i][dis(i,i-1)]==0)){ f[i-1][j^1][mk(0,0,0)]=add(f[i-1][j^1][mk(0,0,0)],now); } } if(s3){ if((s1==0||no[i+1][dis(i+1,i+2)]==0)&&(s2==0||no[i][dis(i,i+1)]==0)&&(no[i-1][dis(i-1,i)]==0&&no[i+2][dis(i+2,i-1)]==0)){ f[i-1][j][mk(0,0,0)]=add(f[i-1][j][mk(0,0,0)],now); } } } } } void sol3(){ if(n<=2){ if(n==1||(n==2&&k==0)) puts("1"); else puts("0"); return; } if(n==3){ int ans=0; if(no[n][dis(n,n-1)]==0&&no[n-1][dis(n-1,n-2)]==0&&no[n-2][dis(n-2,n)]==0) ++ans; if(no[n][dis(n,n-2)]==0&&no[n-2][dis(n-2,n-1)]==0&&no[n-1][dis(n-1,n)]==0) ++ans; printf("%d",ans); return ; } f[n-2][1][7]=1;f[n-2][0][7]=1; for(reg i=n-2;i>=2;--i){ for(reg s=0;s<8;++s){ if(f[i][0][s]) calc(i,0,s); if(f[i][1][s]) calc(i,1,s); } } int ans=0; for(reg s=0;s<8;++s){ ans=add(ans,add(f[1][0][s],f[1][1][s])); } printf("%d",ans); } int main(){ rd(n);rd(k);rd(p); int x,y; for(reg i=1;i<=k;++i){ rd(x);rd(y); if(abs(x-y)<=p){ no[x][y-x+3]=1; } } if(p==0) sol0(); else if(p==1) sol1(); else if(p==2) sol2(); else sol3(); return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2019/3/3 10:02:45 */