AGC053C Random Card Game

~~昨晚十点过开题，睡觉时躺床上脑子里全是这个题，两三点的时候想出来了。~~XD

由于 $2n$ 无论与什么数一起选，均能删掉选择的数，最后留下的一定是 $2n$ 所在的牌组。只有当一个牌组被清空时才会结束，所以最少的操作次数其实就是 $n$ 加上另一个牌组最少需要被删除的数的个数。

设 $2n$ 所在的数组为数组 $B$ ，另一个数组为 $A$ ，仔细分析可以发现结论：

设对 $A$ 数组中从上到下第 $i(1 \le i \le n)$ 个元素 $A_i$，$t_i = \min\{j | B_j > A_i\} - i$ ，最少需要被删除的数的个数为 $\max(0,\max_{1 \le i \le n}t_i)$ 。

需要被删除的个数至少为结论中的值：对每个左数组中的值，它都需要右数组中的一个值和它配对（即在数组中编号相同）并删除。因此，考虑 $t_i$ 取到最大值的 $i$ ，即 $B$ 数组中最靠前的 $B_j > A_i$ 的位置尽量靠后，如果不把中间的 $t_i$ 个数删完，$A_i$ 一定无法被删除掉。
需要被删除的个数不超过结论中的值：我们可以总是操作最靠前的 $A_i > B_i$ 的位置，直到删够了 $\max(0,\max_{1 \le i \le n}t_i)$ 。对于每个 $A$ 中的数，都存在一个比它大的数在 $B$ 中更靠前的位置，因此只需要从后到前用 $B$ 中这些数删掉 $A$ 的数。

现在我们可以计算最少需要被删除的数的个数大于等于 $x$ 的方案数。

如果从大到小向 $A,B$ 数组中填数，当我们向 $B_i$ 填数后， $A_1 \sim A_{i+x}$ 之间的位置都可以填数了，因为它们可以被一个比它大的 $B$ 在偏移不超过 $x$ 时删除。因此我们总是不断在 $B$ 中的一个前缀最大的位置填数，于是有些 $A$ 就可以填任何数了，直到某次填数后 $A$ 中所有位置都可以填数。

对于所有前缀最大的位置，它的方案只有 $1$ ，因为只能填当前剩下的数中最大的。当填完 $B$ 的一个前缀最大值后，假设新增了 $k$ 个 $A,B$ 中可以填入的位置，且之前已经填好了 $t$ 个数，那么贡献是 $(2n-t-1)(2n-t-2)\cdots (2n-t-k)$ 。

我们可以开始就给答案乘上 $(2n)!$ ，于是填入 $B$ 中的一个前缀最大值时相当于扣掉这其中的某一项。具体来说，假设在填这个前缀最大值前已经填了 $k$ 个数，就给答案乘上 $\frac{1}{2n-k}$ 。

而每个 $B$ 中的位置都可以选择是否作为前缀最大值，因此系数是 $(1+\frac{1}{2n-2i-x})$ 。

答案就是 $i = 1 \sim n-x$ 的这些系数乘起来，稍微推以下可以发现可以由几个双阶乘拼起来：

$ans_x = \frac{(2n-i-1)!!(i)!!}{(2n-i-2)!!(i-1)!!}$

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
// #pragma GCC optimize(2)
typedef long long ll;
const int MAXN = 2e6 + 10;
const int P = 1e9 + 7;
int n , m , q;

int Pow( int x , int a ) {
    int ret = 1;
    while( a ) {
        if( a & 1 ) ret = ret * 1ll * x % P;
        x = x * 1ll * x % P , a >>= 1;
    }
    return ret;
}

int J[MAXN] , iJ[MAXN];
void solve() {
    cin >> n;
    J[0] = J[1] = 1;
    rep( i , 2 , n * 2 ) J[i] = J[i - 2] * 1ll * i % P;
    iJ[n * 2] = Pow( J[n * 2] , P - 2 ) , iJ[n * 2 - 1] = Pow( J[n * 2 - 1] , P - 2 );
    per( i , n * 2 , 2 ) iJ[i - 2] = iJ[i] * 1ll * i % P;
    int ret = 0 , las = 0;
    rep( i , 0 , n - 1 ) {
        int S = Pow( 2 * n , P - 2 );
        int res = J[2 * n - 2 - i + 1] * 1ll * iJ[2 * n - 2 - i] % P * J[i] % P * iJ[i + 1] % P * S % P * ( i + 1 ) % P;
        ret = ( ret + ( res + P - las ) * 1ll * i ) % P;
        las = res;
    }
    cout << ( ret * 2ll + n ) % P << endl;
}

signed main() {
	// freopen("in","r",stdin);
	// freopen("fout","w",stdout);
	// int T;cin >> T;while( T-- ) solve();
	solve();
}