題目傳送門
題目大意（摘自洛谷）
描述
對于長度為n的陣列A，A中只包含從1到n的整數（可重復），如果A單調不上升或單調不下降，A就可稱為美麗的， 找出在長度為n時，有幾個美麗的A，
輸入
一個整數n,(1<=n<=10^5)
輸出
輸出長度為n時，有幾個美麗的A，由于答案可能非常的大，輸出時需要將答案對1000000007取模.
Translated by KethGeorge
輸入輸出樣例
輸入 #12輸出 #1
4輸入 #2
3輸出 #2
17
一道數論題
建立模型：一個高為1 ，長為2n-1的矩形，由1*1的小方格排列而成，其中n-1個是空格，n個記錄從第一個小方格到當前小方格中，共有多少個空格標志，這些數值組成所求陣列，只不過，數字的范圍是從0 ~ n-1，與題目從1 ~ n是等價的，
例如n=5，[1,2,2,4,5]（等價于[0,1,1,3,4]）即為
|
0 |
|
1 |
1 |
|
|
3 |
|
4 |
這種序列可以得到C(2n-1,n)個，同樣的，滿足非升序列的種數也是C(2n-1,n)，
但是，當陣列中n個數都相同，是兩種序列重復的，共有n種
因此，最終答案是，2C(2n-1,n)-n（或者C(2n,n)-n,可以發現恒等））
由于n和mod的值很大，我們要用逆元對組合數取模
……（此處省略114514字）數論只會GCD的我百度了半天
最終答案為(2*(2n-1)*..(n+1)*(n-1)!^(mod-2)-n+mod)%mod
其中乘方用快速冪
時間復雜度O(2*n+log1000000007)
上代碼
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1000000007; int n; ll up=1,down=1; ll inverse(ll x,ll y)//求逆元（快速冪） a關于p的逆元ans=a^(p-2) { ll ans=1; while(y) { if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans; } int main() { //freopen("array10.in","r",stdin); //freopen("array10.out","w",stdout); scanf("%d",&n); for(int i=n+1;i<2*n;i++)//分子(2n-1)*……*n+1 up=up*i%mod; for(int i=1;i<=n-1;i++)//分母(n-1)! down=down*i%mod; printf("%d\n",((2*up*inverse(down,(ll)mod-2))-n+mod)%mod);//變除為乘,求逆元 return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/205318.html
標籤：其他
下一篇：變數解構賦值的7大用途總結