1485: [HNOI2009]有趣的數列 Time Limit: 10 Sec Memory Limit: 64 MB Submit: 484 Solved: 272 [Submit][Status] Description 我們稱一個長度為2n的數列是有趣的，當且僅當該數列滿足以下三個條件： (1)它是從1到2n共2n個整數的一個排列{ai}； (2)所有的奇數項滿足a1<a3<…<a2n-1，所有的偶數項滿足a2<a4<…<a2n； (3)任意相鄰的兩項a2i-1與a2i(1≤i≤n)滿足奇數項小於偶數項，即：a2i-1<a2i。 現在的任務是：對於給定的n，請求出有多少個不同的長度為2n的有趣的數列。因為最後的答案可能很大，所以只要求輸出答案 mod P的值。 Input 輸入文件只包含用空格隔開的兩個整數n和P。輸入數據保證，50%的數據滿足n≤1000，100%的數據滿足n≤1000000且P≤1000000000。 Output 僅含一個整數，表示不同的長度為2n的有趣的數列個數mod P的值。 Sample Input 3 10 Sample Output 5 對應的5個有趣的數列分別為（1,2,3,4,5,6），（1,2,3,5,4,6），（1,3,2,4,5,6），（1,3,2,5,4,6），（1,4,2,5,3,6） 【轉化】就是求卡特蘭數。 【初始代碼】 [cpp] #include<cstdio> using namespace std; typedef long long ll; ll prime[200005],a[200005]; bool f[2000005]; ll temp,n,p,i,j,cnt,mod; ll pow(ll a,ll b) { ll ans; for (ans=1;b;b>>=1,a=a*a%mod) if (b&1) ans=ans*a%mod; return ans; } int main() { scanf("%lld%lld",&n,&mod); for (i=2;i<=n*2;i++) { if (!f[i]) prime[++cnt]=i; for (j=1;j<=cnt&&prime[j]*i<=n*2;j++) f[prime[j]*i]=true; } for (i=n+2;i<=n*2;i++) for (j=1,p=i;j<=cnt&&p;j++) while (p%prime[j]==0) a[j]++,p/=prime[j]; for (i=2;i<=n;i++) for (j=1,p=i;j<=cnt&&p;j++) while (p%prime[j]==0) a[j]--,p/=prime[j]; temp=1; for (j=1;j<=cnt;j++) if (a[j]) temp=(temp*pow(prime[j],a[j]))%mod; printf("%lld",temp);for (;;); return 0; } 用歐拉篩法，O（n）的效率求出每個質數。然後枚舉階乘，像質數表一樣把一個數給分解。但是效率很低。 【優化1】如果一個數是合數，我們可以把它的某個因子記下來。然後我們同樣從開始枚舉階乘，而且是倒著枚舉。對於每個數，如果它是合數，我就把它分解。比如，設f[n]為結果中含有n因子的個數。u是n的一個約數。那麼我們可以f[u]+=f[n],f[n/u]+=f[n]。這樣就不用多次用快速冪了。直到n是質數為止。 【優化2】開始可以把1--n的f[i]設為-1，把n+2--2*n(注意，最後要除n+1,所以從n+2開始)的f[i]設為1.這樣只需1次循環。 【AC代碼】 [cpp] #include<cstdio> using namespace std; typedef long long ll; ll prime[200005],a[2000005],come[2000005]; ll temp,n,p,i,j,cnt,mod; ll pow(ll a,ll b) { ll ans; for (ans=1;b;b=b/2,a=a*a%mod) if (b&1) ans=ans*a%mod; return ans; } int main() { scanf("%lld%lld",&n,&mod); for (i=2;i<=n*2;i++) { if (!come[i]) prime[++cnt]=i; for (j=1;j<=cnt&&prime[j]*i<=n*2;j++) come[prime[j]*i]=i; } temp=1; for (i=2;i<=n;i++) a[i]=-1; for (i=n+2;i<=2*n;i++) a[i]=1; for (i=n*2;i>1;i--) if (come[i]) { a[come[i]]+=a[i]; a[i/come[i]]+=a[i]; } else temp=temp*pow(i,a[i])%mod; printf("%lld",temp); return 0; }
