模拟赛-20190115-permutation

题目相关

题目链接

题目大意

给定$n$，$q$组询问，每组询问包含$x,y$，求满足条件的排列$a$数量
条件1：max(a1,a2⋅⋅⋅ay)=aymax(a_1,a_2···a_y)=a_ymax(a1​,a2​⋅⋅⋅ay​)=ay​
条件2: 2ax<ay2a_x<a_y2ax​<ay​

数据范围

$1\le n,q\le 1000000,1\le x<y\le n$

题解

这题的$\Theta (nlogn)$算法不能过
首先发现，$x$的值无论如何变化答案相同（可以把$x$位看成特殊位）
我们发现直接求并不好做，我们考虑这样一件事情：
如果题目的条件2改为2ax>ay2a_x>a_y2ax​>ay​，那么答案不变
为什么？
我们发现，当aya_yay​确定的时候，对于满足k<ayk<a_yk<ay​的数，满足2k<ay2k<a_y2k<ay​和满足2k>ay2k>a_y2k>ay​的数是一样多的，所以答案也是一样的
设AlessA_{less}Aless​为条件2为2ax<ay2a_x<a_y2ax​<ay​时的答案（即我们要求的）,
设AmoreA_{more}Amore​为条件2为2ax>ay2a_x>a_y2ax​>ay​时的答案，
设AequalA_{equal}Aequal​为条件2为2ax=ay2a_x=a_y2ax​=ay​时的答案，
设AnoneA_{none}Anone​为条件2没有时的答案，
容易发现Anone=(ny)(y−1)!(n−y)!=n!y!(n−y)!(y−1)!(n−y)!=n!yA_{none}=\binom{n}{y}(y-1)!(n-y)!=\frac{n!}{y!(n-y)!}(y-1)!(n-y)!=\frac{n!}yAnone​=(yn​)(y−1)!(n−y)!=y!(n−y)!n!​(y−1)!(n−y)!=yn!​
（即取出$y$个数，把最大值作为aya_yay​，再枚举前后的摆放方式，当然也可以用其它方法推）
并且Aless+Amore+Aequal=AnoneA_{less}+A_{more}+A_{equal}=A_{none}Aless​+Amore​+Aequal​=Anone​
由于我们知道Aless=AmoreA_{less}=A_{more}Aless​=Amore​
所以Aless=Anone−Aequal2A_{less}=\frac{A_{none}-A_{equal}}{2}Aless​=2Anone​−Aequal​​
考虑如何求AequalA_{equal}Aequal​
设gig_igi​为$y=i$时a1⋅⋅⋅aya_1···a_ya1​⋅⋅⋅ay​的选择方案数
容易发现Aequal=gy(y−2)!(n−y)!A_{equal}=g_y(y-2)!(n-y)!Aequal​=gy​(y−2)!(n−y)!
考虑怎么求gig_igi​
gi=∑j=1⌊n2⌋(2j−2i−2)=∑j=0⌊n2⌋−1(2ji)\begin{aligned} g_i&=\sum_{j=1}^{\left\lfloor \frac n2\right\rfloor}\binom{2j-2}{i-2}\\ &=\sum_{j=0}^{\left\lfloor \frac n2\right\rfloor-1}\binom{2j}{i} \end{aligned}gi​​=j=1∑⌊2n​⌋​(i−22j−2​)=j=0∑⌊2n​⌋−1​(i2j​)​
我们将其一般化
假设给定$m$
现在要求的是fn=∑i=0m(2in)f_n=\sum_{i=0}^m\binom{2i}{n}fn​=i=0∑m​(n2i​)
根据经典性质(nm)=(n−1m)+(n−1m−1)\binom nm=\binom{n-1}m+\binom{n-1}{m-1}(mn​)=(mn−1​)+(m−1n−1​)
我们可以将$f$进行一些转化
fn=∑i=0m(2in)=∑i=0m((2i−1n−1)+(2i−1n))=∑i=0m(2i−1n−1)+∑i=0m(2i−1n)\begin{aligned} f_n&=\sum_{i=0}^m\binom{2i}{n}\\ &=\sum_{i=0}^m(\binom{2i-1}{n-1}+\binom{2i-1}{n})\\ &=\sum_{i=0}^m\binom{2i-1}{n-1}+\sum_{i=0}^m\binom{2i-1}{n}\\ \end{aligned}fn​​=i=0∑m​(n2i​)=i=0∑m​((n−12i−1​)+(n2i−1​))=i=0∑m​(n−12i−1​)+i=0∑m​(n2i−1​)​
列出组合数的一个经典式子（我们发现这个式子和我们要求的$f$非常像）
∑i=xy(ix)=(y+1x+1)\sum_{i=x}^y\binom{i}{x}=\binom{y+1}{x+1}i=x∑y​(xi​)=(x+1y+1​)
将两个fnf_nfn​相加
2fn=∑i=0m(2i−1n−1)+∑i=0m(2i−1n)+∑i=0m(2in)=∑i=0m(2i−1n−1)+∑i=0m(2i−1n)+∑i=0m(2in)+fn−1−fn−1=∑i=0m(2i−1n−1)+∑i=0m(2in−1)+∑i=0m(2i−1n)+∑i=0m(2in)−fn−1=∑i=02m(in−1)+∑i=02m(in)−fn−1=(2m+1n)+(2m+1n+1)−fn−1=(2m+2n+1)−fn−1\begin{aligned} 2f_n&=\sum_{i=0}^m\binom{2i-1}{n-1}+\sum_{i=0}^m\binom{2i-1}{n}+\sum_{i=0}^m\binom{2i}{n}\\ &=\sum_{i=0}^m\binom{2i-1}{n-1}+\sum_{i=0}^m\binom{2i-1}{n}+\sum_{i=0}^m\binom{2i}{n}+f_{n-1}-f_{n-1}\\ &=\sum_{i=0}^m\binom{2i-1}{n-1}+\sum_{i=0}^m\binom{2i}{n-1}+\sum_{i=0}^m\binom{2i-1}{n}+\sum_{i=0}^m\binom{2i}{n}-f_{n-1}\\ &=\sum_{i=0}^{2m}\binom i{n-1}+\sum_{i=0}^{2m}\binom i{n}-f_{n-1}\\ &=\binom{2m+1}{n}+\binom{2m+1}{n+1}-f_{n-1}\\ &=\binom{2m+2}{n+1}-f_{n-1}\\ \end{aligned}2fn​​=i=0∑m​(n−12i−1​)+i=0∑m​(n2i−1​)+i=0∑m​(n2i​)=i=0∑m​(n−12i−1​)+i=0∑m​(n2i−1​)+i=0∑m​(n2i​)+fn−1​−fn−1​=i=0∑m​(n−12i−1​)+i=0∑m​(n−12i​)+i=0∑m​(n2i−1​)+i=0∑m​(n2i​)−fn−1​=i=0∑2m​(n−1i​)+i=0∑2m​(ni​)−fn−1​=(n2m+1​)+(n+12m+1​)−fn−1​=(n+12m+2​)−fn−1​​
容易发现m=⌊n2⌋−1m=\left\lfloor \frac n2\right\rfloor-1m=⌊2n​⌋−1
所以gx=(2⌊n2⌋x+1)−gx−12g_x=\frac{\binom{2\left\lfloor \frac n2\right\rfloor}{x+1}-g_{x-1}}2gx​=2(x+12⌊2n​⌋​)−gx−1​​
直接递推即可，预处理组合数，算法总复杂度$\Theta (n)$

代码

贴上AC代码

#include
#include
namespace fast_IO
{const int IN_LEN=10000000,OUT_LEN=10000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
#define rg register
template <typename T> inline T max(const T a,const T b){return a>b?a:b;}
template <typename T> inline T min(const T a,const T b){return a<b?a:b;}
template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;}
template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;}
template <typename T> inline T abs(const T a){return a>0?a:-a;}
template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;}
template <typename T> inline void swap(T*a,T*b){T c=a;a=b;b=c;}
template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);}
template <typename T> inline T square(const T x){return x*x;};
template <typename T> inline void read(T&x)
{char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;  
}
template <typename T> void printe(const T x)
{if(x>=10)printe(x/10);putchar(x%10+'0');
}
template <typename T> inline void print(const T x)
{if(x<0)putchar('-'),printe(-x);else printe(x);
}
const int maxn=1000001,mod=998244353;
int fac[maxn],ifac[maxn],inv[maxn];
inline int pow(int x,int y)
{int res=1;for(;y;y>>=1,x=(ll)x*x%mod)if(y&1)res=(ll)x*res%mod;return res;
}
inline int C(const int x,const int y)
{return (ll)fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
int n,q,f[maxn];
int main()
{fac[0]=1;for(rg int i=1;i<=1000000;i++)fac[i]=(ll)fac[i-1]*i%mod;ifac[1000000]=pow(fac[1000000],mod-2);inv[0]=1;for(rg int i=1000000;i>=1;i--)ifac[i-1]=(ll)ifac[i]*i%mod,inv[i]=(ll)ifac[i]*fac[i-1]%mod;read(n),read(q);const int INV=inv[2];f[0]=n>>1;const int P=(n>>1)<<1;for(rg int i=1;i<=n;i++)f[i]=(ll)INV*(C(P,i+1)+mod-f[i-1])%mod;while(q--){int x,y;read(x),read(y);print(((ll)fac[n]*inv[y]+mod-(ll)f[y-2]*fac[n-y]%mod*fac[y-2]%mod)%mod*INV%mod),putchar('\n');}return flush(),0;
}

总结

常数极小，稳稳的过
弱弱的推式子题（为何很多人都懒得自己推啊），转化问题很巧妙

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！