题目
给出 \(n\)，求有多少个长度为 \(2n\) 的序列满足以下条件：
- 数字 \(1\sim n\) 每个正好各出现两次。
- 仅存在一个数字 \(x\) 满足 \(x\) 所在位置前的数字出现次数都没有 \(x\) 多。
思路
首先显然的是，对于一个满足条件 1 的序列，第一个位置的数字必然满足条件 2，所以这个数字 \(x\) 必然就是该序列的第一个数字。
那么假设第一个数字位置为 \(1\) 和 \(i\)，那么显然需要满足第 \(2\sim i-1\) 的数字各不相同。而 \(i+1\sim 2n\) 的数字无特殊要求。
那么考虑枚举第一个数字第二次出现的位置 \(i\)，然后这种情况下的方案数就是 \(2\sim i-1\) 合法的方案书乘 \(i+1\sim n\) 合法的方案数。
那么前者相对好求，答案显然是从\(n-1\) 个数字中选出 \(i-2\) 个数字的排列。可以写作 \(C^{i-2}_{n-1}!\)。
后者没有什么特殊要求，所以可以先看做有 \(n-i\) 个数字随便排列即 \((2n-i)!\)，但是由于还有 \(n+1-i\) 个数字可以被选两次，所以每一种等价的情况被计算了 \(2^{n+1-i}\) 次。所以最终有 \(\frac{(2n-i)!}{2^{n+1-i}}\) 种情况。
又因为第一个位置有 \(n\) 种可能，所以答案为
\[n\times \sum^{n+1}_{i=1}C^{i-2}_{n+1}!\times \frac{(2n-i)!}{2^{n+1-i}}
\]
但是这题稍微卡常。我们发现 \(2^{n+1-i}\) 其实可以在枚举过程中顺便递推，避免了每次计算花费过多时间。
时间复杂度 \(O(n\log n)\)。
\(\operatorname{Update:}\)这道题还有递推式，可以在 \(O(n)\) 复杂度内求出。暂时不会证。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2000010,MOD=998244353;
int n;
ll ans,power,fac[N];
inline ll fpow(ll x,ll k)
{
ll s=1;
for (;k;k>>=1,x=x*x%MOD)
if (k&1) s=s*x%MOD;
return s;
}
inline ll C(int a,int b)
{
ll inv=fpow(fac[b]*fac[a-b]%MOD,MOD-2);
return fac[a]*inv%MOD;
}
int main()
{
scanf("%d",&n);
fac[0]=1;
for (register int i=1;i<=2*n;i++)
fac[i]=fac[i-1]*i%MOD;
ll inv2=fpow(2LL,MOD-2);
power=1LL;
for (register int i=n+1;i>=2;i--)
{
ll s1=fac[i-2]*C(n-1,i-2)%MOD;
ll s2=fac[2*n-i]*power%MOD;
ans=(ans+s1*s2)%MOD;
power=power*inv2%MOD;
}
printf("%lld",ans*n%MOD);
return 0;
}