最后的晚餐

#最后的晚餐

题目大意

有一个有$2\ast n2*n$个座位的圆桌，还有$nn$对情侣

求任意一对情侣不相邻的座位安排方案数（按顺/逆时针旋转重合视为一种方案）

分析

感觉主流做法都是组合数+简单容斥

这里来一个非主流做法，希望能给到大家一些新的思路

Step One

首先假设，这$nn$对情侣中每队都有一个人上位了

那么就是说现在的方案就有$n!n!$

Step Two

为了满足题意，要把剩下的$nn$个人插入到现有的队伍中去

定义$f(x)f(x)$表示把$nn$中的前$xx$个人插入到队列中的方案数

那么有

如何理解这个递推式子？

感性理解

1： $f(x-1)\ast (n+x-3)f(x-1)*(n+x-3)$

当插入第$xx$个人时，已经有$n+x-1n+x-1$个人上位了，理论上这个人能去的位置有$n+x-1n+x-1$个

但是这个人却和自己的另一半闹矛盾了，不想和他(她)坐在一起

就是说，这个人实际能去的位置只有$n+x-3n+x-3$个（他(她)左右有两个不能去）

这部分的方案数就是$f(x-1)\ast (n+x-3)f(x-1)*(n+x-3)$

2： $f(x-2)\ast (x-1)\ast 2f(x-2)*(x-1)*2$

当插入第$xx$个人时，前面有人想通过这位接近自己的另一半

就是说，它可以作为前$x-1x-1$个入队的人的某一个的缓冲(即暂时当一下电灯泡)

那么他们又有左右两边两种选择

所以这部分的方案数就是$f(x-2)\ast (x-1)\ast 2f(x-2)*(x-1)*2$

所以得到了最后的$f(x)=f(x-1)\ast (n+x-3)+f(x-2)\ast (x-1)\ast 2f(x)=f(x-1)*(n+x-3)+f(x-2)*(x-1)*2$

再乘上最开始的$n!n!$看上去就大功告成了

但是这不是链，这是环

易证其实只有$(n-1)!(n-1)!$个本质不同的初始方案

所以最后的答案应该是$f(n)\ast (n-1)!f(n)*(n-1)!$

#include <bits stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 3e7 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o &lt; '0' || o &gt; '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o &gt;= '0' &amp;&amp; o &lt;= '9'; o = getchar()) x = (x &lt;&lt; 1) + (x &lt;&lt; 3) + (o ^ 48);
    return x * t;
}

int f[maxn];

signed main()
{  
    int n = __read();
    if (n == 1) return puts("0") &amp; 0;
    f[0] = 1, f[1] = n - 2;
    for (int i = 2; i &lt;= n; ++i)
        f[i] = (1ll * f[i - 1] * (n + i - 3) % mod + 1ll * f[i - 2] * (i - 1) % mod * 2 % mod) % mod;
    
    for (int i = 2 ; i &lt; n; ++i)
        f[n] = 1ll * f[n] * i % mod;
    
    printf ("%d\n", f[n]);
    system("pause");
}