【GDOI2017第二轮模拟day2】中位数

题目大意

给定n,k，求多少个n的排列在经过以下计算后得到k：

n≤1000000 且为奇数

分析

直接算不好算，可以转化成：结果是大于等于k的减大于等于k+1的。
然后把大于等于k的数看成1，小于k的看成0。继续挖掘有什么性质。
把每一层看成去掉第一、最后的位置，在草稿纸上手玩一下，可以发现：
1. 如果原序列中间的数是1，且两边有一个1，那么答案一定是1
2. 如果原序列中间的数与两边的不同，那么向两边扩展（要一直保证对称且相邻元素不同）。例如：01010101011，得到的是1

那么可以枚举对称的部分有多大，然后用组合数计算未确定的部分

注意判边界

时间复杂度$O(n)$

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int N=1000005,mo=998244353;typedef long long LL;int n,m,Fac[N],Inv[N],F_Inv[N],ans;int C(int n,int m)
{return (LL)Fac[n]*F_Inv[m]%mo*F_Inv[n-m]%mo;
}int calc(int m)
{if (m==0) return 0;if (m==1){if (n==1) return 1;return 0;}ans=(m==n/2+1);for (int i=1;i<=n/2;i++){if (m>i){ans=(ans+(LL)2*C(n-i-i-1,m-i-1))%mo;if (m>i+1) ans=(ans+C(n-i-i-1,m-i-2))%mo;}}ans=(LL)ans*Fac[m]%mo*Fac[n-m]%mo;return ans;
}int main()
{scanf("%d%d",&n,&m);Fac[0]=F_Inv[0]=Fac[1]=Inv[1]=F_Inv[1]=1;for (int i=2;i<=n;i++){Fac[i]=(LL)Fac[i-1]*i%mo;Inv[i]=(LL)Inv[mo%i]*(mo-mo/i)%mo;F_Inv[i]=(LL)F_Inv[i-1]*Inv[i]%mo;}ans=calc(n-m+1)-calc(n-m);if (ans<0) ans+=mo;printf("%d\n",ans);return 0;
}