两个序列（数论）

两个序列

Problem:B

Time Limit:1000ms

Memory Limit:65535K

Description

Gugu 有两个长度无限长的序列A,B
A0=a^0/0!,A1=a^1/1!,A2=a^2/2!,A3=a^3/3!….
B0=0, B1=b^1/1!,B2=0,B3=b^3/3!,B4=0, B5=b^5/5! …
Douge 看到这道这两个序列很觉得很麻烦，所以他想到一个好点子，他想把这两个序列结合一个序列C
Cn= n! * sigma Ai*B(n-i) (n-i)>=0 i>=0
当Douge 把C序列写到纸上觉得好多呀！！！所以他只想知道Cn，但是Douge 要去打游戏，所以想寻求你来帮助他

Input

T组数据         （T<=1e5）
给出 a,b,n   0<=a,b,n<=1e9

Output

Cn%1e9+7

Sample Input

1
1 1 1

Sample Output

Hint

大约1e5组数据，推荐使用scanf
样例解释：
C1=1!*((A0*B1)+(A1*B0))=1!((1/0! * 1/1!) + (1/1! * 0)) = 1

思路：

写出来，化简一下是 $(a+b)^{n}$ 取b为奇数次项

答案为( $(a+b)^{n}$ - $(a-b)^{n}$ )/2;

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<unordered_map>
#include<map>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
#define per(i,a,b) for(int i=a;i<=b;i++)
#define ber(i,a,b) for(int i=a;i>=b;i--)
const int N = 1e5;
const long long mod = 1e9+7;
const double eps = 1e-2;
int T;
LL a, b, n,ni,ans;
LL quick(LL a, LL b,LL mod)
{
   LL ans = 1;
   while (b)
   {
       if (b & 1)
           ans = ans * a % mod;
       b >>= 1;
       a = a * a % mod;
   }
   return ans;
}
int main()
{
   cin >> T;
   ni = quick(2, mod - 2, mod);
   while (T--)
   {
       ans = 0;
       scanf("%lld%lld%lld", &a, &b, &n);
       ans = (ans + quick(a + b, n, mod)) % mod;
       ans = (ans-quick(a - b, n, mod)) % mod;
       ans = ans * ni % mod;
       printf("%lld\n", (ans%mod+mod)%mod);
   }
   return 0;
}