LUOGU P2675 《瞿葩的数字游戏》T3-三角圣地

解题思路

手推可以得出，最后每个数字的贡献其实就是第n行杨辉三角数，然后直接卢卡斯直接算（今天才找到lucas定理时间复杂度是log n,log以模数为底）。代码略麻烦，不想改了。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#define LL long long

using namespace std;

const int MAXN = 1000005;

const int mod = 10007;

int n,num;

LL inv[MAXN],to[MAXN];

LL ans;

inline LL lucas(int n,int m){

    if(n<m) return 0;

    if(n<mod && m<mod) return to[n]*inv[m]%mod*inv[n-m]%mod;

    return lucas(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;

}

int main(){

    scanf("%d",&n);

    if(n==0) {puts("0");return 0;}

    if(n==1) {puts("1");return 1;}

    to[1]=1;

    for(register int i=2;i<=n;i++)

        to[i]=to[i-1]*i%mod;

    inv[mod-1]=mod-1;

    for(register int i=mod-2;~i;i--)

        inv[i]=inv[i+1]*(i+1)%mod;

    num=2;

    ans=3;

    for(register int i=1;i<=(n/2)+1;i++){

        LL k=lucas(n-1,i);

        ans=(ans+(++num)*k%mod)%mod;

        if(num==n) break;

        ans=(ans+(++num)*k%mod)%mod;

        if(num==n) break;

    }

    printf("%lld",ans);

    return 0;

}

巴特西

LUOGU P2675 《瞿葩的数字游戏》T3-三角圣地

解题思路

代码

最新文章

热门文章