洛谷 Array 数论

题目：

对于长度为n的数组A，A中只包含从1到n的整数（可重复）。如果A单调不上升或单调不下降，A就可称为美丽的。 找出在长度为n时，有几个美丽的A。

---

思路：

这是一道数论题。

我们先找找“单调不递减的A”。

1.构造模型：设一个长度为（2*n-1）的序列，用1填满n个空，剩余（n-1）个空；

2.一一对应：找到每一个“1”，用其前方总共的“空格数”构成新序列。如下图所示。

 

 

3.合理性：构成的序列满足两个条件。

• （1）不递减：因为空格的数目只会累加。（如果两个“1”相邻的话会出现新序列中有相同数字的情况）
• （2）新序列中每个数字都是0到n-1的整数（可重复）对应题干中“从1到n的整数”:因为空格的数目最多只有n-1。

可见，单调不递减的A的数目=。

易得，单调不递增的A的数目=单调不递减的A的数目=。

所以，由容斥定理得，答案=不递增+不递减-既不递增.也不递减（常数序列）                                                                             .

---

代码展示：

#include<stdio.h>
#include<stdlib.h>
const int mod=1000000007;
long long ny(long long x)//逆元 取模 
{int cf=mod-2;long long base=x,ans=1;while(cf){if(cf%2==1) ans*=base;ans%=mod;base=base*base;base%=mod;cf>>=1;}return ans;
}
long long c(int x,int y)//计算组合数 
{long long fz=1,fm=1,ans;int i;for(i=x;i>=x-y+1;i--) {fz*=i;fz%=mod;}for(i=1;i<=y;i++){fm*=i;fm%=mod;}fm=ny(fm);ans=fz*fm;ans%=mod;return ans;
}
long long zj;
int main()
{//答案是c(2n，n)-n int n,i;scanf("%d",&n);zj=c(2*n,n);zj-=n;if(zj<0) zj+=mod;printf("%lld",zj);return 0;
}