专栏首页ACM小冰成长之路51Nod-1149-Pi的递推式

51Nod-1149-Pi的递推式

ACM模版

描述

题解

image.png

代码

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;
typedef double db;

const db PI = M_PI;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;

int n, m, ans;
int fac[MAXN];
int inv[MAXN];

int QPow(int x, int y)
{
    if (!y)
    {
        return 1;
    }

    int ret = QPow(x, y >> 1);
    ret = (ll)ret * ret % MOD;
    if (y & 1)
    {
        ret = (ll)ret * x % MOD;
    }

    return ret;
}

int C(int n, int m)
{
    return (ll)fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

//  预处理阶乘逆元
void init()
{
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        fac[i] = (ll)fac[i - 1] * i % MOD;
    }
    inv[n] = QPow(fac[n], MOD - 2);
    for (int i = n - 1; i >= 0; i--)
    {
        inv[i] = (ll)inv[i + 1] * (i + 1) % MOD;
    }
}

int main()
{
    scanf("%d", &n);
    if (n < 4)
    {
        printf("1\n");
        return 0;
    }

    init();

    n -= 4;
    int tmp = (int)(n / PI);
    //  最后一个超越的是 1,枚举 PI
    for (int i = 0, t; i <= tmp; i++)
    {
        t = (n - i * PI);
        ans += C(t + i, i);
        ans %= MOD;
    }
    //  最后一个超越的是 PI,枚举 1
    for (int i = 0, t; i <= n; i++)
    {
        t = (n - i) / PI;
        ans += C(t + i, i);
        ans %= MOD;
    }

    printf("%d\n", ans);

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Go语言探险思考笔记(1)

    最近接触对象存储,国际上鼎鼎有名的Amazon S3还有Google Cloud Service在国内由于防火墙还有机房过远的问题,并不能投入生产使用。国内有名...

    干货满满张哈希
  • 强化学习(二)马尔科夫决策过程(MDP)

        在强化学习(一)模型基础中,我们讲到了强化学习模型的8个基本要素。但是仅凭这些要素还是无法使用强化学习来帮助我们解决问题的, 在讲到模型训练前,模型的简...

    刘建平Pinard
  • 递推算法的核心——公式(按照公式写递归) 顶

    以此我们得出兔子生崽的递推算法:其中有1对兔子,每个月都可以生一对兔子,但是任何的兔子都必须2个月大,即第3个月才有生育能力。

    算法之名
  • 【优雅的避坑】不安全!别再共享SimpleDateFormat变量了-日期时间处理的正确姿势

    JDK文档中已经明确表明了「SimpleDateFormat不应该用在多线程场景」中:

    行百里er
  • Golang 学习笔记-1:变量&函数

    最近在学习golang,写下学习笔记提升记忆。为了看起来不是那么枯燥,本学习笔记采用分析代码的形式。

    goodspeed
  • Raspberry Pi 推出 Zero W

    Raspberry Pi 基金会 推出了 Pi Zero W。作为 Pi Zero 的一个新型号,Pi Zero W 在主板上新集成了 WiFi 和蓝牙,其 1...

    Debian中国
  • 隐马尔科夫-维特比算法

    概念介绍:   继上篇贝叶斯(https://cloud.tencent.com/developer/article/1056640)后,一直想完成隐马尔科夫这...

    知然
  • 10.动态规划(3)——0-1背包问题

      在上一篇《9.动态规划(2)——子集和问题》中,谈到了什么是子集和问题,以及实现。背包问题实际也是子集和问题的一种,不过背包问题不是“判断问题”而是一个“最...

    用户1148394
  • Hadoop分布式集群环境搭建

    之前我们已经介绍了如何在单机上搭建伪分布式的Hadoop环境,而在实际情况中,肯定都是多机器多节点的分布式集群环境,所以本文将简单介绍一下如何在多台机器上搭建H...

    端碗吹水

扫码关注云+社区

领取腾讯云代金券