CF57C Array

题目传送门

题目大意(摘自洛谷

描述

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

输入

一个整数n,(1<=n<=10^5)

输出

输出长度为n时,有几个美丽的A,由于答案可能非常的大,输出时需要将答案对1000000007取模.

Translated by KethGeorge

输入输出样例
输入 #1
2
输出 #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;
}

 

上一篇:[蓝桥杯][基础训练]2n皇后问题


下一篇:养花