nssl 1452 2018CodeM总决赛 排行榜

$Description$

有一种长度为 $2n$的序列，它有 $n$种数字，每种数字恰好出现两次，假设开头的那个数字为 $x$， $x$第二次出现的位置为 $i$，则对于任意的 $j\in(1,i)$，不存在任何一种数字出现了两次，这种序列的数量

数据范围： $n\leq 10^6$

$Solution$

首先打表找规律

#include<cstdio>
using namespace std;int n,num[1000010],ans;
inline void dfs(int dep,int key)
{if(dep>2*n) {ans++;return;}//搜出了一种合法序列，统计for(register int i=1;i<=n;i++)if(num[i]<2&&(num[i]+1<=num[key]||i==key))//这个数字没被选完，并且数量比x少，如果恰好是x则特判{num[i]++;dfs(dep+1,key);num[i]--;}return;
}
signed main()
{scanf("%d",&n);for(register int i=1;i<=n;i++) num[i]++,dfs(2,i),num[i]--;//锁定第一个数，从第二个数开始搜printf("%d",ans);
}

然后就成功得到了一个数列
1,4,48,1152,46080,2764800
乍看好像没有规律，我们发现它们增长较快，于是求一下它们后项与前项的比，发现是
4,12,24,40,60
做差，得到等差数列
8,12,16,20,24

于是我们就可以 $O(n)$得出答案

$Code$

#include<cstdio>
#define mod 998244353
using namespace std;int n;
long long ans,mul,add;
signed main()
{scanf("%d",&n);ans=1;for(register int i=1;i<n;i++){add+=4;(mul+=add)%=mod;(ans*=mul)%=mod;}printf("%lld",ans);
}

正解

不是本人想出来的，是本届的dalaowyc
这边转载一手