NOIP前做了几道POI，现在终于能在BZOJ上提交了…

交上去最后几个点WA，看了数据发现p=0的特判错了…

 

p=0,1时特判

p=2时构造两种情况判断

p=3时不考虑1的座位进行DP

可以发现对于i+1的位置安排，我们只关心i-2,i-1,i的相对顺序以及它们的相邻、边界情况

所以设f[i][j][S1][S2]表示已经安排了前i个人的座位，i-2,i-1,i的顺序为j，是否有人在两端点为S1，是否有人相邻为S2的方案数

答案最后再除以n

这样复杂度有点飞…

 

#include
     
      typedef long long ll;const int N=1000010,P=1000000007;int n,m,p,i,j,S1,S2,ans;bool ban[N][7];//0:-3 3:0 6:3inline int abs(int x){return x>0?x:-x;}inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}namespace Subtask2{int a[N];bool flag;inline void Main(){  if(n&1){    flag=1;    for(a[j=1]=1,i=2;i
      
       2;i-=2)a[++j]=i;    for(i=1;i
       
        2;i-=2)a[++j]=i;    for(i=1;i
        
         >=1,a=a*a%P)if(b&1)t=t*a%P;return t;}inline void add(int l,int r){  int nj=0,i,t=0,p;  for(i=l;i<=r;i++)if(tmp[i]>=2)pl[++t]=i,(nj*=10)+=tmp[i];  e[++ed].j=hash[nj];  e[ed].S1=((pl[1]==l)<<1)|(pl[3]==r);  e[ed].S2=((pl[1]+2>=pl[2])<<1)|(pl[2]+2>=pl[3]);  for(t=0,i=l;i<=r;i++)if(tmp[i]){    pl[++t]=i;    if(tmp[i]==4)p=t;  }  if(p>1&&pl[p-1]+2>=pl[p])e[ed].l=tmp[pl[p-1]];  if(p<4&&pl[p]+2>=pl[p+1])e[ed].r=tmp[pl[p+1]];  e[ed].nxt=g[j][S1][S2];  g[j][S1][S2]=ed;}inline void init(){  hash[243]=1;hash[324]=2;hash[342]=3;hash[423]=4;hash[432]=5;  for(j=0;j<6;j++)for(S1=0;S1<4;S1++)for(S2=0;S2<4;S2++){    isl=S1>>1&1,isr=S1&1,cl1=S2>>1&1,cl2=S2&1;    tmp[r=0]=0;    if(!isl)tmp[++r]=0;    tmp[pos[1]=++r]=loc[j][0];    tmp[++r]=0;if(!cl1)tmp[++r]=0;    tmp[pos[2]=++r]=loc[j][1];    tmp[++r]=0;if(!cl2)tmp[++r]=0;    tmp[++r]=loc[j][2];    if(!isr)tmp[++r]=0;    if(isl&&isr)tmp[0]=4,add(0,r),tmp[0]=0,tmp[r+1]=4,add(1,r+1),tmp[r+1]=0;    if(cl1)tmp[pos[1]+1]=4,add(1,r),tmp[pos[1]+1]=0;    if(cl2)tmp[pos[2]+1]=4,add(1,r),tmp[pos[2]+1]=0;  }}inline void Main(){  init();  for(j=0;j<6;j++)f[1][j][3][3]=1;  for(i=3;i
         
          >1&1){        if(loc[j][0]==1&&ban[i-2][loc[j][1]+2]&&e[k].l!=1)continue;        if(loc[j][1]==1&&ban[i+loc[j][0]-3][4-loc[j][0]]&&e[k].r!=1)continue;      }      if(S2&1){        if(loc[j][1]==1&&ban[i-2][loc[j][2]+2]&&e[k].l!=1)continue;        if(loc[j][2]==1&&ban[i+loc[j][1]-3][4-loc[j][1]]&&e[k].r!=1)continue;      }      if(S1==3){        if(loc[j][0]==1&&ban[i+loc[j][2]-3][4-loc[j][2]]&&e[k].l&&e[k].r)continue;        if(loc[j][2]==1&&ban[i-2][loc[j][0]+2]&&e[k].l&&e[k].r)continue;      }      if(S1&1){        if(loc[j][2]==1&&ban[i-2][6]&&(!e[k].l||!e[k].r))continue;      }      if(S1>>1&1){        if(loc[j][0]==1&&ban[i+1][0]&&(!e[k].l||!e[k].r))continue;      }      (f[i&1^1][e[k].j][e[k].S1][e[k].S2]+=f[i&1][j][S1][S2])%=P;    }  }  for(j=0;j<6;j++)for(S1=0;S1<4;S1++)for(S2=0;S2<4;S2++)if(f[n&1][j][S1][S2]){    if(S2>>1&1)if(ban[n+loc[j][0]-3][loc[j][1]-loc[j][0]+3])continue;    if(S2&1)if(ban[n+loc[j][1]-3][loc[j][2]-loc[j][1]+3])continue;    if(S1==3)if(ban[n+loc[j][2]-3][loc[j][0]-loc[j][2]+3])continue;    (ans+=f[n&1][j][S1][S2])%=P;  }  ans=(ll)ans*pow(n,P-2)%P;}}int main(){  read(n),read(m),read(p);  if(n==1)return puts("1"),0;  if(p==0)return puts("0"),0;  if(n==2)return puts(m?"0":"1"),0;  if(p==1)return puts("0"),0;  while(m--){    read(i),read(j);    if(abs(i-j)<=p)ban[i][j-i+3]=1;  }  if(p==2)Subtask2::Main();else Subtask3::Main();  return printf("%d",ans),0;}