There are an equation.
∑0≤k1,k2,?km≤n∏1?j<m(kj+1kj)%1000000007=?
We define that (kj+1kj)=kj+1!kj!(kj+1?kj)! . And (kj+1kj)=0 while kj+1<kj.
You have to get the answer for each n and m that given to you.
For example,if n=1,m=3,
When k1=0,k2=0,k3=0,(k2k1)(k3k2)=1;
Whenk1=0,k2=1,k3=0,(k2k1)(k3k2)=0;
Whenk1=1,k2=0,k3=0,(k2k1)(k3k2)=0;
Whenk1=1,k2=1,k3=0,(k2k1)(k3k2)=0;
Whenk1=0,k2=0,k3=1,(k2k1)(k3k2)=1;
Whenk1=0,k2=1,k3=1,(k2k1)(k3k2)=1;
Whenk1=1,k2=0,k3=1,(k2k1)(k3k2)=0;
Whenk1=1,k2=1,k3=1,(k2k1)(k3k2)=1.
So the answer is 4.
Input
The first line of the input contains the only integer T,(1≤T≤10000)
Then T lines follow,the i-th line contains two integers n,m,(0≤n≤109,2≤m≤109)
Output
For each n and m,output the answer in a single line.
Sample Input
2
1 2
2 3
Sample Output
3
13
打表很容易看出規律是$m^0+m^1+...+m^n$(鬼扯，我看了好幾個小時愣是沒看出有什么規律，看完題解還是不知道怎么推出來的，我太難了，這公式推的我服氣）
下面是題解，我服我服了，臥槽。

推導公式結束后，你看直接一個逆元完事了，這個題我哭了，比我看到莫比烏斯反演還絕望，臥槽。

#include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7;long long ksm(long long a, long long n) {long long ans = 1;for (; n; n >>= 1){if (n & 1)ans = ans * a % mod;a = a * a % mod;}return ans; } int main() {int T;scanf("%d", &T);while (T--){long long n, m;scanf("%lld%lld", &n, &m);printf("%lld\n", (ksm(m, n + 1) - 1) * ksm(m - 1, mod - 2) % mod);}return 0; }

總結

以上是生活随笔為你收集整理的数学--数论--Hdu 5793 A Boring Question （打表+逆元）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。