【51nod】1149 Pi的递推式

题解

我们把这个函数的递归形式画成一张图，会发现答案是到每个出度为0的点的路径的方案数

这个可以用组合数算

记录一下P[i]为i减几次PI减到4以内

如果P[i + 1] > P[i]，那么转向的路径走P[i]次，否则走P[i] - 1次

代码

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <vector>

#include <set>

#include <cmath>

#include <bitset>

#define enter putchar('\n')

#define space putchar(' ')

//#define ivorysi

#define pb push_back

#define mo 974711

#define pii pair<int,int>

#define mp make_pair

#define fi first

#define se second

#define MAXN 1000005

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 - '0' + c;

	c = getchar();

    }

    res = res * f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) out(x / 10);

    putchar('0' + x % 10);

}

const int MOD = 1000000007;

const db PI = acos(-1.0);

int N,fac[MAXN],inv[MAXN],invfac[MAXN],P[MAXN];

int mul(int a,int b) {

    return 1LL * a * b % MOD;

}

int inc(int a,int b) {

    return a + b >= MOD ? a + b - MOD : a + b;

}

int C(int n,int m) {

    if(n < m) return 0;

    return mul(mul(fac[n],invfac[m]),invfac[n - m]);

}

void Init() {

    read(N);

    fac[0] = 1;

    for(int i = 1 ; i <= N ; ++i) fac[i] = mul(fac[i - 1],i);

    inv[1] = 1;

    for(int i = 2 ; i <= N ; ++i) inv[i] = mul(inv[MOD % i],MOD - MOD / i);

    invfac[0] = 1;

    for(int i = 1 ; i <= N ; ++i) invfac[i] = mul(invfac[i - 1],inv[i]);

}

void Solve() {

    for(int i = 4 ; i <= N ; ++i) {

	P[i] = floor((i - 4) / PI) + 1;

    }

    if(N < 4) {out(1);enter;return;}

    int ans = 0;

    for(int i = N ; i >= 3 ; --i) {

	int s = N - i,t = P[i] - (P[i + 1] <= P[i]);

	ans = inc(ans,C(s + t,s));

    }

    out(ans);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Init();

    Solve();

}