ACM模版

描述

题解

这个题最后结果的意义其实就是从 n 开始，可以选择 −1 或者 −PI ，最终到达 [0,4] 的方案数模 MOD 的结果。

稍微转化一下变成从 0 开始，可以选择 +1 或者 +PI 两种一直加到不小于 n−4 为止的所有方案数，所以这里我们需要考虑两种情况，在最后不小于 n−4 这个临界值时的操作是什么，自然是有两种：
1、最后一次是选择 +1 操作，所以我们可以枚举 +PI 操作的次数，这样很容易获取到对应的 +1 操作的次数；
2、最后一次是选择 +PI 操作，同理，我们可以枚举 +1 操作的次数，并获取对应的 +PI 操作次数。
根据这两种情况，我们可以通过组合原理来累计统共有多少种方案。

是不是感觉并不像想象中那么难，其实这个有些像斐波那契数列，我们如果按照这种思路的话，斐波那契数列可以理解为从 0 开始，可以选择 +1 或者 +2 两种操作，最终达到 n <script type="math/tex" id="MathJax-Element-1784">n</script> 的方案种数。

代码

#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;
}