Luogu3581 CZA

Arahc 11.0
  2022-03-10 08:00 2022-03-10 08:00 创建   2023-03-15 02:54:40 2023-03-15 02:54:40 更新      1.3k 字  7 分钟  

题面

简化题意

nn 个人坐成一个环，相邻两人编号差的绝对值不超过 pp，且满足 kk 个形如『某人不能坐在某人右边』这样的要求。求 nn 的位置固定后，其他人坐座位的方案数。

n≤106,m≤105,p≤3n\leq 10^6,m\leq 10^5,p\leq 3，对 109+710^9+7 取模。

题解

pp 只有四种取值，分类讨论吧。

分类讨论前，为了方便，先把一些边界特判掉，后文默认 n>2n>2。

零、壹、贰

这三种情况难度速降普及组。简单带过一下就好了。

  • p=0p=0 答案为 00。
  • p=1p=1 答案为 00，因为 nn 旁边只能做 n−1n-1，坐不出第二个人。
  • p=2p=2 时 nn 旁边只能坐 n−1,n−2n-1,n-2。枚举 n−1n-1 在左边还是右边，依次推出所有座次，然后判定是否满足要求。

叁

仍然按照 nn 到 11 的顺序考虑。假设当前考虑到放第 ii 个人，这个人只能放在 i+1,i+2,i+3i+1,i+2,i+3 这三个人中的两个的中间。而且一旦确定 ii 放在这个位置，就不能放 i−1,i−2⋯i-1,i-2\cdots 了 。

还要注意条件中的是一个人的右边，因此区分左右位置，只不过是转移的判断谁在谁右边的顺序换一下而已。

设 fi,0/1,23f_{i,0/1,2^3} 表示当前 [n,i][n,i] 这些人的位置固定，正在考虑 i−1i-1 的位置，判断标准是左边还是右边，i,i+1,i+2i,i+1,i+2 这三个人两两之间能不能放一个 i−1i-1。

转移是一个巨大分类讨论。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
using namespace std;
const int max_n=1000006,mod=1000000007;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}

int n,m,p,ans;
bool cant[max_n][8];

inline bool Can(int x,int y){
    if(abs(x-y)>p) return 0;
    return cant[x][x-y+3]^1;
}

int a[max_n],f[max_n][2][8];

inline int State(int can1,int can2,int can3){
    return can1|(can2<<1)|(can3<<2);
}

inline void ZhuanYi(int i,int j,int k){
    bool can1=k&1,can2=(k>>1)&1,can3=(k>>2)&1;
    if(i>2){
        if(!j){
            if(can1 && ((can3 && Can(i,i+2) && Can(i+2,i-1)) || (!can3 && Can(i+2,i-1))))
                f[i-1][j][State(can2,0,1)]=(f[i-1][j][State(can2,0,1)]+f[i][j][k])%mod;
            if(can2 && (!can1 || Can(i+2,i+1)) && (!can3 || Can(i,i+2)))
                f[i-1][j^1][State(0,1,1)]=(f[i-1][j^1][State(0,1,1)]+f[i][j][k])%mod;
            if(can3 && (!can1 || Can(i+2,i+1)) && Can(i-1,i+2))
                f[i-1][j][State(can2,1,0)]=(f[i-1][j][State(can2,1,0)]+f[i][j][k])%mod;
        }
        else{
            if(can1 && ((can3 && Can(i+2,i) && Can(i-1,i+2)) || (!can3 && Can(i-1,i+2))))
                f[i-1][j][State(can2,0,1)]=(f[i-1][j][State(can2,0,1)]+f[i][j][k])%mod;
            if(can2 && (!can1 || Can(i+1,i+2)) && (!can3 || Can(i+2,i)))
                f[i-1][j^1][State(0,1,1)]=(f[i-1][j^1][State(0,1,1)]+f[i][j][k])%mod;
            if(can3 && (!can1 || Can(i+1,i+2)) && Can(i+2,i-1))
                f[i-1][j][State(can2,1,0)]=(f[i-1][j][State(can2,1,0)]+f[i][j][k])%mod;
        }
        return;
    }
    if(!j){
        if(can1 && (!can2 || Can(i+1,i)) && (!can3 || Can(i,i+2)) && Can(i+2,i-1) && Can(i-1,i+1))
            ans=(ans+f[i][j][k])%mod;
        if(can2 && (!can1 || Can(i+2,i+1)) && (!can3 || Can(i,i+2)) && Can(i+1,i-1) && Can(i-1,i))
            ans=(ans+f[i][j][k])%mod;
        if(can3 && (!can1 || Can(i+2,i+1)) && (!can2 || Can(i+1,i)) && Can(i,i-1) && Can(i-1,i+2))
            ans=(ans+f[i][j][k])%mod;
    }
    else{
        if(can1 && (!can2 || Can(i,i+1)) && (!can3 || Can(i+2,i)) && Can(i-1,i+2) && Can(i+1,i-1))
            ans=(ans+f[i][j][k])%mod;
        if(can2 && (!can1 || Can(i+1,i+2)) && (!can3 || Can(i+2,i)) && Can(i-1,i+1) && Can(i,i-1))
            ans=(ans+f[i][j][k])%mod;
        if(can3 && (!can1 || Can(i+1,i+2)) && (!can2 || Can(i,i+1)) && Can(i-1,i) && Can(i+2,i-1))
            ans=(ans+f[i][j][k])%mod;
    }
}

inline void Solve(){
    f[n-2][0][7]=f[n-2][1][7]=1;
    for(register int i=n-2;i>1;--i)
        for(register int j=0;j<2;++j)
            for(register int k=0;k<8;++k)
                if(f[i][j][k])
                    ZhuanYi(i,j,k);
    write(ans);
}

signed main(){
    n=read(),m=read(),p=read();
    if(n==1){
        puts("1");
        return 0;
    }
    if(n==2){
        puts(m==0?"1":"0");
        return 0;
    }
    if(p<2){
        puts("0");
        return 0;
    }
    for(register int i=1;i<=m;++i){
        int x=read(),y=read();
        if(abs(x-y)>p) continue;
        cant[x][x-y+3]=1;
    }
    if(p==2){
        for(register int i=1;i<=n;++i){
            if(i&1) a[i/2+1]=n-i;
            else a[n-i/2+1]=n-i;
        }
        ans=2,a[0]=a[n],a[n+1]=a[1];
        for(register int i=1;i<=n;++i)
            if(!Can(a[i],a[i+1])){
                --ans;
                break;
            }
        for(register int i=1;i<=n;++i)
            if(!Can(a[i],a[i-1])){
                --ans;
                break;
            }
        write(ans);
        return 0;
    }
    Solve();
    return 0;
}
  • 标题: Luogu3581 CZA
  • 作者: Arahc
  • 创建于 : 2022-03-10 08:00:00
  • 更新于 : 2023-03-15 02:54:40
  • 链接: https://arahc.github.io/2022/03/10/【题解】Luogu3581-CZA/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
Luogu3581 CZA
  1. 题面
  2. 题解
    1. 零、壹、贰
    2. 叁
  3. 代码