21.4.21 t1

tag:构造

题意

设计一个确定性有限状态自动机，使得恰好能接受1~n的全排列中的 \(q\) 个

\(n\leq12,0\leq q\leq n!\)

输出

第一行为状态数 \(Q(Q\le n+1)\)

接下来 \(Q\) 行，每行 \(n\) 个数。第 \(i\) 行第 \(j\) 个数 \(a_{i,j}\) 表示第 \(i\) 个状态在遇到 \(j\) 时会转移到状态 \(a_{i,j}\)

接下来一行一个数 \(q_0\) 表示初始状态为 \(q_0\)

接下来一行若干个数，第一个数为接受的状态数 \(n\)，后面 \(n\) 个不同整数\(f_1,f_2\cdots f_n\) 表示接受状态 \(f_1,f_2\cdots f_n\)

实际上可以构造出自动机恰好接受从 \(1,2\cdots n\) 一直到第 \(q\) 个排列。

将第 \(n\) 个状态当作“垃圾桶”，第 \(n+1\) 个状态当作"终点"。这两个状态都是自己连自己。

举个例子就很明显了。\(n=4\)，接受所有小于 \(3,2,4,1\) 的排列。

拆分一下：

• 接受所有以 \((1)\)、\((2)\) 开头的排列

连 \((1\to n+1,1/2),\ (1\to2,3)\ (1\to n,4)\)

• 接受所有以 \((3,1)\) 开头的排列

连 \((2\to n+1,1),\ (2\to3,2)\ (2\to,n,3/4)\)

• 接受所有以 \((3,2,1)\)、\((3,2,4)\) 开头的排列

连 \((3\to n+1,1/4),\ (3\to n, 2/3)\)

思路就是逐位限定。当前状态向终点 \(n+1\) 的连边就是当前位接受的状态，然后再向下一个状态连一条边，其余的边都往垃圾桶 \(n\) 连。

#include
using namespace std;
 
template
inline void Read(T &n){
    char ch; bool flag=false;
    while(!isdigit(ch=getchar()))if(ch==‘-‘)flag=true;
    for(n=ch^48;isdigit(ch=getchar());n=(n<<1)+(n<<3)+(ch^48));
    if(flag)n=-n;
}

int n, q;

char vis[15];
int ans[15][15];

int getnxt(int x){x++;while(vis[x])x++;return x;}

int main(){
    // freopen("1.out","w",stdout);
    Read(n); Read(q);
    int tp = 1;
    vis[0] = true;
    for(register int i=1; i