[atAGC053C]Random Card Game

记两堆（从顶开始）依次为$a_{i}$和$b_{i}$（其中$i\in [1,n]$），考虑如何求最小得分：

注意到无法操作即其中一堆为空，得分即删除的数个数，而$2n$永远不会被删除

不妨假设$2n$在$b_{i}$中，最小得分也即删除$a_{i}$中所有数至少要删除$b_{i}$中几个数$+n$

结论：最小得分为$\max_{1\le i\le n}\min_{1\le j\le n,a_{i}

显然要删除$a_{i}$，其至少要与$b_{j}$一起操作，那么也即要在$b_{i}$中删除$j-i$个才能使两者相同

另一方面，对该值是否为0分类讨论：

1.若该值为0，操作最大的$i$满足$a_{i}

2.若该值不为0，操作最小的$i$满足$a_{i}>b_{i}$，不难证明操作后该值恰减小1，因此操作对应次数即可变为0

根据期望线性性可以提出$n$，问题即求$E\big(\max_{1\le i\le n}\min_{1\le j\le n,a_{i}

对于$X\in [1,n]$，有$E(X)=\sum_{d=1}^{n}P(X\ge d)=n-\sum_{d=0}^{n-1}P(X\le d)$，问题也即求$P(X\le d)$

实际上，这也等价于$\forall 1\le i\le n,a_{i}<\max_{1\le j\le \min(i+d,n)}b_{j}$

进一步的，可以将填数改为插入，通过调整顺序，即要求插入的数不在最后，那么答案也即
$$
\prod_{i=1}^{n-d}\frac{2i+d-1}{2i+d}\prod_{i=n-d+1}^{n}\frac{n+i-1}{n+i}
$$
这显然可以预处理并$o(1)$求出，时间复杂度为$o(n)$，可以通过

 1 #include
 2 using namespace std;
 3 #define N 2000005
 4 #define mod 1000000007
 5 #define ll long long
 6 int n,ans,inv[N],fac1[N],fac2[N],inv1[N],inv2[N];
 7 int main(){
 8     inv[0]=inv[1]=1;
 9     for(int i=2;imod;
10     fac1[0]=fac1[1]=fac2[0]=fac2[1]=1;
11     for(int i=2;i){
12         fac1[i]=(ll)fac1[i-1]*i%mod;
13         fac2[i]=(ll)fac2[i-2]*i%mod;
14     }
15     inv1[0]=inv1[1]=inv2[0]=inv2[1]=1;
16     for(int i=2;i){
17         inv1[i]=(ll)inv1[i-1]*inv[i]%mod;
18         inv2[i]=(ll)inv2[i-2]*inv[i]%mod;
19     }
20     scanf("%d",&n),ans=(n<<1);
21     for(int i=0;i){
22         int s1=fac2[(n<<1)-i-1];
23         if (i)s1=(ll)s1*inv2[i-1]%mod;
24         int s2=(ll)inv2[(n<<1)-i]*fac2[i]%mod;
25         int t1=(ll)fac1[(n<<1)-1]*inv1[(n<<1)-i-1]%mod;
26         int t2=(ll)inv1[(n<<1)]*fac1[(n<<1)-i]%mod;
27         ans=(ans-(ll)2*s1*s2%mod*t1%mod*t2%mod+mod)%mod;
28     }
29     printf("%d\n",ans);
30     return 0; 
31 }