本文主要是介绍HDU 5793 A Boring Question，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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 ;
When k1=0,k2=1,k3=0,(k2k1)(k3k2)=0 ;
When k1=1,k2=0,k3=0,(k2k1)(k3k2)=0 ;
When k1=1,k2=1,k3=0,(k2k1)(k3k2)=0 ;
When k1=0,k2=0,k3=1,(k2k1)(k3k2)=1 ;
When k1=0,k2=1,k3=1,(k2k1)(k3k2)=1 ;
When k1=1,k2=0,k3=1,(k2k1)(k3k2)=0 ;
When k1=1,k2=1,k3=1,(k2k1)(k3k2)=1 .
So the answer is 4.
∑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 ;
When k1=0,k2=1,k3=0,(k2k1)(k3k2)=0 ;
When k1=1,k2=0,k3=0,(k2k1)(k3k2)=0 ;
When k1=1,k2=1,k3=0,(k2k1)(k3k2)=0 ;
When k1=0,k2=0,k3=1,(k2k1)(k3k2)=1 ;
When k1=0,k2=1,k3=1,(k2k1)(k3k2)=1 ;
When k1=1,k2=0,k3=1,(k2k1)(k3k2)=0 ;
When k1=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)
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
Author
UESTC
Source
2016 Multi-University Training Contest 6
Recommend
wange2014
题意：
求
∑0≤k1,k2...km≤n∏1≤j<m(kj+1kj)mod1000000007
题解：
这个题只是看上去吓人而已…
比赛的时候大部分都是找规律过的，后来看官方题解才茅塞顿开。
首先可以分析出来：这个和要是不为0，序列k必须非减，所以我们考虑非减的情况就行了。
接下来开始化简：
∵序列非减∴∑0≤k1,k2...km≤n∏1≤j<m(kj+1kj)=∑kmn∑km−1km...∑k1=0k2(k2k1)(k3k2)...(kmkm−1)
注意到后面的积可以分别提到和式的前面。
∑kmn∑km−1km(kmkm−1)∑km−2km−1(km−1km−2)...∑k1=0k2(k2k1)
这时，我们发现最里面的一项就是 2k2 ，所以有：
∑kmn∑km−1km(kmkm−1)∑km−2km−1(km−1km−2)...∑k2k3(k3k2)⋅2k2
这时我们又发现此时的最后一项又可以由二项式展开来化简：
∑k2k3(k3k2)⋅2k2=(2+1)k3=3k3
这样一直进行化简，最后可以得到：
∑kmn∑km−1km(kmkm−1)⋅(m−1)km−1=∑kmnmkm
这样在最后就是一个等比数列求和了。
最终结果：
ans=mn+1−1m−1
代码：
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;ll quickmod(ll a,ll b){ll ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b/=2;}return ans;
}void exgcd(ll a,ll b,ll &x,ll &y){if(!b) {x=1,y=0;return ;}else {exgcd(b,a%b,y,x);y-=a/b*x;}
}int main(){ll t,m,n;cin>>t;while(t--){cin>>n>>m;///cout<<(quickmod(m,n+1)-1)*quickmod(m-1,mod-2)%mod<<endl;ll x,y;exgcd(m-1,mod,x,y);x=(x+mod)%mod;cout<<(quickmod(m,n+1)-1)*x%mod<<endl;}
}
这篇关于HDU 5793 A Boring Question的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
