《瞿葩的数字游戏》T3-三角圣地（Lucas）

ztz11 2018-06-21 原文

题目背景

国王1带大家到了数字王国的中心：三角圣地。

题目描述

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

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

输入输出格式

输入格式：

一个整数N

输出格式：

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

思路：

其实这道题大家画个图就会发现，1~n个数在他们自己位置上的权值是杨辉三角形第n行

由于可以交换位置，所以将最大的放在中间即可

于是开始算了

一开始，我用的递推组合数直接求一行杨辉三角形

50分？？

哦，1000000太大了，递推会出锅

好吧，Lucas来一发

还是50分？？

好吧，TLE出锅了

怎么办呢？
看来只能预处理阶乘了。。。

心累。。

递推版：

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,p,t,ans[1000010],ny[1000010],out;
void qny()
{
    ny[1]=1;
    for(register int a=2;a<=n;a++)
    {
        ny[a]=(p-(p/a))*ny[p%a]%p;
    }
}
int main()
{
    scanf("%d",&n);
    p=10007;
    qny();
    m=(n+1)/2;
    ans[0]=1;
    for(register int i=1;i<=m-1;i++)
    {
        ans[i]=ans[i-1]*(n-i)*ny[i]%p;
    }
    for(register int i=2;i<=n;i+=2)
    {
        long long ltt=i+i-1;
        ltt%=p;
        ltt*=ans[i/2-1];
        ltt%=p;
        out+=ltt;
        out%=p;
    }
    if(n%2==1)
    {
        long long ltt=n*ans[m-1]%p;
        out+=ltt;
        out%=p;
    }
    cout<<out;
}

Lucas朴素版：

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#define rii register int i
using namespace std;
unsigned long long n,m,p,t,ny[100010],out;
void qny()
{
    ny[1]=1;
    for(register int a=2;a<=p;a++)
    {
        ny[a]=(p-(p/a))*ny[p%a]%p;
    }
}
int zhs(int q,int x)
{
    if(q==0)
    {
        return 1;
    }
    long long ltt=1;
    for(register int a=1;a<=q;a++)
    {
        ltt*=ny[a];
        ltt%=p;
    }
    for(register int a=1;a<=q;a++)
    {
        ltt*=(x-a+1);
        ltt%=p;
    }
    return ltt;
}
long long lucas(int s,int t)
{
    if(t==0)
    {
        return 1;
    }
    else
    {
        return (lucas(s/p,t/p)*zhs(s%p,t%p))%p;
    }
}
int main()
{
    scanf("%d",&n);
    p=10007;
    qny();
    for(rii=1;i<=n;i+=2)
    {
        if(i==n)
        {
            out+=lucas(i/2,n-1)*(i);
        }
        else
        {
            out+=lucas(i/2,n-1)*(i*2+1);
        }
        out%=p;
    }
    cout<<out;
}

正解：

#include<iostream>
#include<cstring>
#define rii register int i
using namespace std;
int p=10007;  
long long jc[10010],ny[10010],n,ans;  
void ycl()  
{  
    jc[0]=1;
    jc[1]=1;
    ny[0]=1;
    ny[1]=1; 
    for(rii=2;i<=p-1;i++)
    {
        jc[i]=jc[i-1]*i%p;
    }
    for(rii=2;i<=p-1;i++)
    {
        ny[i]=(p-p/i)*ny[p%i]%p; 
    }
    for(rii=1;i<=p-1;i++)
    {
        ny[i]=ny[i-1]*ny[i]%p;
    }
}
long long lucas(long long h,long long j)  
{  
    if(h<j)
    {
        return 0;
    }
    if(h<p&&j<p)
    {
        return jc[h]*ny[j]%p*ny[h-j]%p; 
    } 
    return lucas(h/p,j/p)*lucas(h%p,j%p)%p;  
}  
int main()  
{  
    ycl();
    cin>>n;
    for(rii=1;i<=n;i++)
    {
        if(i%2==0)
        {
            ans=(ans+(i*lucas(n-1,n-i/2))%p)%p;
            if(ans<0)
            {
                ans+=p;
            }
        }
        else
        {
            ans=(ans+(lucas(n-1,(i+1)/2-1)*i)%p)%p;
            if(ans<0)
            {
                ans+=p;
            }
        }
    }
    cout<<ans;
}