题面

Sol

先设一个套路的状态：\(f[i][j]\)表示到第\(i\)个人，有\(j\)对冲突

但是我们不能确定\(i-1\)，所以不好决策i的位置

所以再加一维\(0/1\)，\(f[0/1][i][j]\)表示\(i\)和\(i-1\)是否有冲突

每枚举一个人，我们就要把它插入到之前的队列中

转移：

\(f[0][i][j]\)：

乘上\(j\)，转移给\(f[0][i+1][j-1]\)，表示消除一个冲突

乘上\(i+1-j-2\)，转移给\(f[0][i+1][j]\)，表示不消除冲突，并且在剩下的\(i+1-j\)选一个不与\(i\)相邻的位置插入\(i+1\)，所以减去\(2\)

乘上\(2\)：转移给\(f[1][i+1][j+1]\)，即选一个与\(i\)相邻的位置插入\(i+1\)

\(f[1][i][j]\)：类似，四种情况自己\(yy\)去吧

# include 
    
     # define RG register# define IL inline# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;const int Zsy(7777777);IL ll Input(){    RG ll x = 0, z = 1; RG char c = getchar();    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);    return x * z;}int n, f[2][1005][1005];IL void Up(RG int &x, RG int y){    x += y;    if(x >= Zsy) x -= Zsy;}int main(RG int argc, RG char* argv[]){    n = Input();    f[0][1][0] = 1;    for(RG int i = 1; i < n; ++i)        for(RG int j = 0; j < i; ++j){            if(f[0][i][j]){                if(j) Up(f[0][i + 1][j - 1], 1LL * f[0][i][j] * j % Zsy);                if(i - j - 1 > 0) Up(f[0][i + 1][j], 1LL * f[0][i][j] * (i - j - 1) % Zsy);                Up(f[1][i + 1][j + 1], 1LL * f[0][i][j] * 2 % Zsy);            }            if(f[1][i][j]){                Up(f[1][i + 1][j], f[1][i][j]);                Up(f[1][i + 1][j + 1], f[1][i][j]);                if(j > 1) Up(f[0][i + 1][j - 1], 1LL * f[1][i][j] * (j - 1) % Zsy);                if(i - j > 0) Up(f[0][i + 1][j], 1LL * f[1][i][j] * (i - j) % Zsy);            }        }    printf("%d\n", f[0][n][0]);    return 0;}