题目地址：51Nod：多项式？ 问题 – 51Nod

题目描述

现在有一个n次多项式F,
我们把将i代入时这个多项式的值记为F（i）
F(i)=i/(i+1) 其中i=0,1,2,…,n
现在试问对于F(n+1)是否唯一确定。
若确定，输出F(n+1)（如果为整数,直接输出；如果是分数(p/q) p与q互质，则输出p * q(%1e9+7)；否则输出至小数点后6位）
否则输出No
n<=10^15

输入输出格式

输入格式：
一个数n，即次数为n的多项式F。n<=10^15

输出格式：
对于F(n+1)是否唯一确定。
若确定，输出答案（如果是有理数(p/q) p与q互质，则输出p * q(%1e9+7)；否则输出至小数点后6位）
否则输出No

输入输出样例

输入样例#1：

1

输出样例#1：

1

题解

喜闻乐见的推式子题。
本题需要的数学姿势：

1. 拉格朗日插值法：拉格朗日插值法及其应用 | KSkun’s Blog
2. 本题不需要高中以上的数学姿势，因为插值是O(n^2)的显然没法做这题

我们知道，n+1个互不等价的方程能解出n个未知数，也就是说，n次多项式可以由n+1个互不相同的点值来确定，因此本题已经有解，接下来分析解法。
首先我们对前面的多项式变个形，变成下面这样
(x+1) \cdot F(x) - x = 0
然后我们发现，其实0, 1, \ldots, n是这个n+1次方程的n+1个解。既然是解，我们考虑引入一个系数k，把这个方程写成这样
(x+1) \cdot F(x) - x = k(x-0)(x-1)\cdots(x-n) = 0
令x=-1，把原来的F多项式搞掉，就得到了k的取值，即
k = (-1)^{n+1} \frac{1}{(n+1)!}
那么F多项式就能直接写出来了，即
F(x) = \frac{1}{x-1} \cdot [(-1)^{n+1} \frac{1}{(n+1)!} \cdot x(x-1)(x-2)\cdots(x-n) + x]
把x=n+1代进去，我们会发现分母的阶乘和旁边的连乘能消掉，接着还能发现一些神奇的事实，首先是这个：
当n+1是个偶数的时候？化简以后变成了F(n+1)=1！
奇数没法化简，就是F(n+1) = \frac{n}{n+2}
注意这里n和n+2都是2的倍数，要除以2以后再计算答案哦。

代码

// Code by KSkun, 2018/3
#include <cstdio>

typedef long long LL;

const int MO = 1e9 + 7;

LL n;

int main() {
    scanf("%lld", &n);
    printf("%lld", n & 1 ? 1 : (n / 2) % MO * ((n / 2 + 1) % MO) % MO);
    return 0;
}