网站工程师是做什么的,郑州百度推广seo,登记注册身份验证app下载,廊坊网站建设设计题目#xff1a;
对于长度为n的数组A#xff0c;A中只包含从1到n的整数#xff08;可重复#xff09;。如果A单调不上升或单调不下降#xff0c;A就可称为美丽的。 找出在长度为n时#xff0c;有几个美丽的A。 思路#xff1a;
这是一道数论题。
我们先找找“单调不递…题目
对于长度为n的数组AA中只包含从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的数目。
所以由容斥定理得答案不递增不递减-既不递增.也不递减常数序列 . 代码展示
#includestdio.h
#includestdlib.h
const int mod1000000007;
long long ny(long long x)//逆元 取模
{int cfmod-2;long long basex,ans1;while(cf){if(cf%21) ans*base;ans%mod;basebase*base;base%mod;cf1;}return ans;
}
long long c(int x,int y)//计算组合数
{long long fz1,fm1,ans;int i;for(ix;ix-y1;i--) {fz*i;fz%mod;}for(i1;iy;i){fm*i;fm%mod;}fmny(fm);ansfz*fm;ans%mod;return ans;
}
long long zj;
int main()
{//答案是c(2nn)-n int n,i;scanf(%d,n);zjc(2*n,n);zj-n;if(zj0) zjmod;printf(%lld,zj);return 0;
}
