[Problem Discription]\color{blue}{\texttt{[Problem Discription]}}[Problem Discription][Analysis]\color{blue}{\texttt{[Analysis]}}[Analysis]设大小为xxx的元素在平衡位置iii。设在[1,i−1][1,i-1][1,i−1]中有uuu个数小于xxx则有(i−1−u)(i-1-u)(i−1−u)个数大于xxx。一共有(n−x)(n-x)(n−x)个数大于xxx所以在[i1,n][i1,n][i1,n]中大于xxx的数有(n−x−(i−1−u))n−x−iu1(n-x-(i-1-u))n-x-iu1(n−x−(i−1−u))n−x−iu1个。因为iii是平衡位置所以un−x−iu1un-x-iu1un−x−iu1所以0n−x−i10n-x-i10n−x−i1即xn−i1xn-i1xn−i1。可见平衡位置上的元素其实是确定了的。想到一个思维游戏。桌面上有100100100个硬币其中101010个正面朝上其余反面朝上。你现在闭着眼睛看不见硬币被随机打乱了。你需要把硬币分成两组不需要一样多还可以进行任意次的翻转操作每次操作把一枚硬币翻过来正面变成反面反面变成正面。问如何操作才能保证两堆硬币正面朝上的数量一样多。正解非常的巧妙。你把任意101010枚硬币拿出来成一堆然后把它们全部翻转就能完成要求。证明假设这101010枚硬币中正面朝上的数量是xxx则反面朝上(10−x)(10-x)(10−x)初始101010个正面朝上剩下909090枚硬币中正面朝上(10−x)(10-x)(10−x)。翻转后正面朝上的数量一定相等均为(10−x)(10-x)(10−x)。因此平衡位置数量是kkk只需要选出kkk个位置放上正确的元素剩下的全错排即可。答案为∑i⌈n2⌉n(ni)Dn−i\sum\limits_{i\left \lceil \frac{n}{2} \right \rceil}^{n} \binom{n}{i}D_{n-i}i⌈2n​⌉∑n​(in​)Dn−i​其中DiD_{i}Di​表示全错排数。时间复杂度O(n)O(n)O(n)。Code\color{blue}{\text{Code}}CodeintD[N],fac[N],inv[N],n,ans;intksm(inta,intb){intres1;while(b){if(b1)res1ll*res*a%mod;a1ll*a*a%mod;b1;}returnres;}voidget_fac_and_inv(intn){fac[0]1;for(inti1;in;i)fac[i]1ll*i*fac[i-1]%mod;inv[n]ksm(fac[n],mod-2);for(intin;i1;i--)inv[i-1]1ll*i*inv[i]%mod;}intC(intn,intm){return1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}intmain(){scanf(%d,n);get_fac_and_inv(n);D[1]0;D[0]1;for(inti2;in;i)D[i]1ll*(i-1)*((D[i-1]D[i-2])%mod)%mod;intm(n1);if(n1)m;for(intim;in;i)ans(ans1ll*C(n,i)*D[n-i]%mod)%mod;printf(%d,ans);return0;}