题目描述：
算法标签：推式子，组合数的一些性质
思路：
考虑满足第一个条件的方案数，对于任意一种排列，前1-y中每一位为前y位最大值的概率均等，所以第y位为前y为最大值的方案数为
考虑第二个条件，任选两个不同的数位x,y，2*Px<2*Py的概率和2*Px>2*Py的概率相等，所以我们如果求出2*Px=Py的方案数，就能求出满足第二个条件的方案数。
令f[x]表示满足条件1 且2*Px=Py的方案数。
则
考虑计算f[x]
因为后半部分均与i无关，我们令
考虑如何递推求g[x]。
观察组合数的杨辉三角图，发现
于是就可以递推O(n)求g[x]了，求ans的问题就迎刃而解了。
以下代码：
#include<bits/stdc++.h> #define il inline #define LL long long #define _(d) while(d(isdigit(ch=getchar()))) using namespace std; const int N=1e6+5,p=998244353; int n,q,g[N],jc[N],ny[N],inv2,m; il int read(){int x;char ch;_(!);x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return x; } il int ksm(LL a,int y){LL b=1;while(y){if(y&1)b=b*a%p;a=a*a%p;y>>=1;}return b; } il int mu(int x,int y){if(x+y>=p)return x+y-p;return x+y; } il int C(int n,int m){return 1ll*jc[n]*ny[m]%p*ny[n-m]%p; } int main() {freopen("permutation.in","r",stdin);freopen("permutation.out","w",stdout);n=read();q=read();inv2=ksm(2,p-2);m=n>>1;jc[0]=1;for(int i=1;i<=n;i++)jc[i]=1ll*jc[i-1]*i%p;ny[n]=ksm(jc[n],p-2);for(int i=n;i;i--)ny[i-1]=1ll*ny[i]*i%p;g[0]=m;for(int i=1;i<=n-2;i++)g[i]=1ll*mu(C(m<<1,i+1),p-g[i-1])*inv2%p;while(q--){read();int y=read();int res=1ll*g[y-2]*jc[y-2]%p*jc[n-y]%p;res=mu(p-res,1ll*jc[n]*ksm(y,p-2)%p);printf("%d\n",1ll*res*inv2%p);}return 0; }