传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6467
简单数学题
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 308 Accepted Submission(s): 150
Problem Description
已知
F(n)=∑i=1n(i×∑j=inCij)
求 F(n) mod 1000000007
Input
多组输入，每组输入占一行，包含一个整数n（1 <= n <= 1e18)。
数据不超过300000组。
数据不超过300000组。
Output
对于每组输入，输出一行，包括一个数代表答案。
Sample Input
5
100
100
Sample Output
129
660756544
660756544
Source
解题思路：
但是这道题只推出递推公式是不行的，因为普通的乘法运算会导致溢出。
但是log2的优化乘法又会超时，所以需要O(1)的优化乘法防止溢出：
inline long long multi(long long x,long long y)
{
long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
return tmp< ? tmp+mod : tmp;
}
AC code：
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const LL mod = ; inline long long multi(long long x,long long y)
{
long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
return tmp< ? tmp+mod : tmp;
} LL qpow(LL a, LL n)
{
LL res = ;
while(n){
if(n&) res = multi(res, a)%mod;
a = multi(a, a);
n>>=;
}
return res%mod;
} int main()
{
// freopen("result.out", "w", stdout);
LL N, p, ans;
while(~scanf("%lld", &N)){
p = qpow(, N);
ans = (multi((N-), p)%mod+)%mod;
printf("%lld\n", ans);
} return ;
}