洛谷2675 三角圣地

Posted by yjjr's blog on December 25, 2017

标签:数学,贪心

题目

题目传送门

不是说三角形是最稳定的图形嘛,数字王国的中心便是由一个倒三角构成。这个倒三角的顶端有一排数字,分别是1~N。1~N可以交换位置。之后的每一行的数字都是上一行相邻两个数字相加得到的。这样下来,最底端就是一个比较大的数字啦!数字王国称这个数字为“基”。国王1希望“基”越大越好,可是每次都自己去做加法太繁琐了,他希望你能帮他通过编程计算出这个数的最大值。但是这个值可能很大,所以请你输出它mod 10007 的结果。

任务:给定N,求三角形1~N的基的最大值 再去 mod 10007。

输入:一个整数N

输出:一个整数,表示1~N构成的三角形的最大的“基”

输入输出样例 输入样例#1: 复制

4

输出样例#1: 复制

24

说明

数据:

20% 0<=N<=100

50% 0<=N<=3000

100% 0<=N<=1000000

样例解释:

1 3 4 2

4 7 6

11 13 24 是N=4的时候的最大值,当然还有别的构成形式。

PS:它叫做三角圣地,其实它就是个三角形~

本题数据已经更新(我更新的)

分析

思路:观察发现越大的数排在中间位置对答案越有利,所以就可以贪心了 而不同位置对答案有不同的贡献次数 拿样例举例 1 3 4 2 那么第一个位置1对答案贡献1次 第二个位置3对答案贡献3次 第三个位置4对答案贡献3次 第四个位置2对答案贡献1次

不难发现这个贡献次数为杨辉三角(就是组合数)

我们可以O(n^2)求出组合数对10007的取模

$ ans=\sum_{i=1}^n C(n,i)*i$

当然答案要取模,在计算的过程中防止负数的出现,要加入判断

O(n^2)求组合数就可以获得50分了

但是觉得这题太水了点,于是加强了下数据范围。

N<=1000000

快速求出组合数,模数也那么小,当然是Lucas定理了!

套个lucas定理的板子就可以了,不知道Lucas的出门右转百度

这题数据出锅了,自己真的zz,爆了long long

此题感谢@BFSBFSBFSBFS @siyuan 的交流和支持

code

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define rep(i,a,b) for(int i=a;i<=b;i++)
    #define dep(i,a,b) for(int i=a;i>=b;i--)
    #define ll long long
    #define mem(x,num) memset(x,num,sizeof x)
    #define reg(x) for(int i=last[x];i;i=e[i].next)
    using namespace std;
    inline ll read()//快速读入
    {
        ll f=1,x=0;char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
    const int p=10007;  
    ll fac[p],inv[p],n;//注意要用long long否则会爆掉
    ll ans;  
    void work()  
    {  
        fac[0]=fac[1]=inv[0]=inv[1]=1;  
        rep(i,2,p-1)fac[i]=fac[i-1]*i%p;  //阶乘预处理
        rep(i,2,p-1)inv[i]=(p-p/i)*inv[p%i]%p;  
        rep(i,1,p-1)inv[i]=inv[i-1]*inv[i]%p;  //逆元预处理
    }  
    ll C(ll n,ll m)  
    {  
        if(n<m)return 0;  //舍去组合数无意义的情况
        if(n<p&&m<p)return fac[n]*inv[m]%p*inv[n-m]%p;  
        return C(n/p,m/p)*C(n%p,m%p)%p;  
    }  
    int main()  
    {  
        //freopen("data20.in","r",stdin);
        //freopen("data20.ans","w",stdout);
        work();  //预处理出乘法逆元和阶乘
        n=read();
        rep(i,1,n){
            if(i%2==0){ans=(ans+((ll)(i*C(n-1,n-i/2)))%p)%p;if(ans<0)ans+=p;}
            else{ans=(ans+((ll)(C(n-1,(i+1)/2-1)*i))%p)%p;if(ans<0)ans+=p;}//这个数本身*这个数贡献的次数,将其累加到答案中去
        }
        cout<<ans<<endl;
        return 0;  
    }  
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr