當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

模拟赛-20190115-permutation

發布時間：2024/4/11 编程问答 39 豆豆

生活随笔收集整理的這篇文章主要介紹了模拟赛-20190115-permutation 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

題目相關

題目鏈接

題目大意

給定 $n$ ， $q$ 組詢問，每組詢問包含 $x, y$ ，求滿足條件的排列 $a$ 數量
條件1： $max(a_1,a_2···a_y)=a_y$
條件2: $2a_x<a_y$

數據范圍

$1≤n,q≤1000000,1≤x<y≤n1\le n,q\le1000000,1\le x<y\le n$

題解

這題的 $Θ(nlogn)\Theta(nlogn)$ 算法不能過
首先發現， $x$ 的值無論如何變化答案相同（可以把 $x$ 位看成特殊位）
我們發現直接求并不好做，我們考慮這樣一件事情：
如果題目的條件2改為 $2a_x>a_y$ ，那么答案不變
為什么？
我們發現，當 $a_y$ 確定的時候，對于滿足 $k<a_y$ 的數，滿足 $2k<a_y$ 和滿足 $2k>a_y$ 的數是一樣多的，所以答案也是一樣的
設 $A_{less}$ 為條件2為 $2a_x<a_y$ 時的答案（即我們要求的）,
設 $A_{more}$ 為條件2為 $2a_x>a_y$ 時的答案，
設 $A_{equal}$ 為條件2為 $2a_x=a_y$ 時的答案，
設 $A_{none}$ 為條件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!}y$
（即取出 $y$ 個數，把最大值作為 $a_y$ ，再枚舉前后的擺放方式，當然也可以用其它方法推）
并且 $A_{less}+A_{more}+A_{equal}=A_{none}$
由于我們知道 $A_{less}=A_{more}$
所以 $Aless=Anone?Aequal2A_{less}=\frac{A_{none}-A_{equal}}{2}$
考慮如何求 $A_{equal}$
設 $g_i$ 為 $y = i$ 時 $a_1···a_y$ 的選擇方案數
容易發現 $A_{equal}=g_y(y-2)!(n-y)!$
考慮怎么求 $g_i$
$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}$
我們將其一般化
假設給定 $m$
現在要求的是 $fn=∑i=0m(2in)f_n=\sum_{i=0}^m\binom{2i}{n}$
根據經典性質 $(nm)=(n?1m)+(n?1m?1)\binom nm=\binom{n-1}m+\binom{n-1}{m-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}$
列出組合數的一個經典式子（我們發現這個式子和我們要求的 $f$ 非常像）
$∑i=xy(ix)=(y+1x+1)\sum_{i=x}^y\binom{i}{x}=\binom{y+1}{x+1}$
將兩個 $f_n$ 相加
$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}$
容易發現 $m=?n2??1m=\left\lfloor \frac n2\right\rfloor-1$
所以 $gx=(2?n2?x+1)?gx?12g_x=\frac{\binom{2\left\lfloor \frac n2\right\rfloor}{x+1}-g_{x-1}}2$
直接遞推即可，預處理組合數，算法總復雜度 $Θ(n)\Theta(n)$

代碼

貼上AC代碼

#include<cstdio> #include<cctype> 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; }

總結

常數極小，穩穩的過
弱弱的推式子題（為何很多人都懶得自己推啊），轉化問題很巧妙

總結

以上是生活随笔為你收集整理的模拟赛-20190115-permutation的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

Permutation

上一篇：模拟赛-20190114-新魔法(dis
下一篇： [PKUWC2018][loj2537]