hdu5793 A Boring Question（推公式or迷之找规律）

思路：比赛时候是迷之手玩了很多个样例然后大胆猜测了一发公式...

正解：

A Boring Question

\sum_{0\leq k_{1},k_{2},\cdots k_{m}\leq n}\prod_{1\leq j< m}\binom{k_{j+1}}{k_{j}}∑​0≤k​1​​,k​2​​,⋯k​m​​≤n​​∏​1≤j<m​​(​k​j​​​k​j+1​​​​) =\sum_{0\leq k_{1}\leq k_{2}\leq\cdots \leq k_{m}\leq n}\prod_{1\leq j< m}\binom{k_{j+1}}{k_{j}}=∑​0≤k​1​​≤k​2​​≤⋯≤k​m​​≤n​​∏​1≤j<m​​(​k​j​​​k​j+1​​​​) =\sum_{k_{m}=0}^{n}\sum_{k_{m-1}=0}^{k_{m}}\cdots \sum_{k_{1}=0}^{k_{2}}\prod_{1\leq j< m}\binom{k_{j+1}}{k_{j}}=∑​k​m​​=0​n​​∑​k​m−1​​=0​k​m​​​​⋯∑​k​1​​=0​k​2​​​​∏​1≤j<m​​(​k​j​​​k​j+1​​​​) =\sum_{k_{m}=0}^{n}\left { \binom{k_{m}}{k_{m-1}} \sum_{k_{m-1}=0}^{k_{m}} \left { \binom{k_{m-1}}{k_{m-2}} \cdots \sum_{k_{1}=0}^{k_{2}}\binom{k_{2}}{k_{1}} \right } \right }=∑​k​m​​=0​n​​{(​k​m−1​​​k​m​​​​)∑​k​m−1​​=0​k​m​​​​{(​k​m−2​​​k​m−1​​​​)⋯∑​k​1​​=0​k​2​​​​(​k​1​​​k​2​​​​)}} =\sum_{k_{m}=0}^{n}\left { \binom{k_{m}}{k_{m-1}} \sum_{k_{m-1}=0}^{k_{m}} \left { \binom{k_{m-1}}{k_{m-2}} \cdots \sum_{k_{1}=0}^{k_{2}}\binom{k_{2}}{k_{1}} \right } \right }=∑​k​m​​=0​n​​{(​k​m−1​​​k​m​​​​)∑​k​m−1​​=0​k​m​​​​{(​k​m−2​​​k​m−1​​​​)⋯∑​k​1​​=0​k​2​​​​(​k​1​​​k​2​​​​)}} =\sum_{k_{m}=0}^{n}\left { \binom{k_{m}}{k_{m-1}} \sum_{k_{m-1}=0}^{k_{m}} \left { \binom{k_{m-1}}{k_{m-2}} \cdots \sum_{k_{2}=0}^{k_{3}}\binom{k_{3}}{k_{2}}2^{k_{2}} \right } \right }=∑​k​m​​=0​n​​{(​k​m−1​​​k​m​​​​)∑​k​m−1​​=0​k​m​​​​{(​k​m−2​​​k​m−1​​​​)⋯∑​k​2​​=0​k​3​​​​(​k​2​​​k​3​​​​)2​k​2​​​​}} =\sum_{k_{m}=0}^{n}m^{k_{m}}=∑​k​m​​=0​n​​m​k​m​​​​ =\frac{m^{n+1} - 1}{m - 1}=​m−1​​m​n+1​​−1​​

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
#define LL long long

template<class T1,class T2>
T1 quick_mod(T1 t,T2 n)
{
	T1 ans=1;
	while(n)
	{
		if(n&1) ans=ans*t%mod;
		t=t*t%mod;
		n>>=1;
	}
	return ans;
}
LL Inv(LL x)
{
	return quick_mod(x, mod-2);
}
int main()
{
    int T;
	scanf("%d",&T);
	while(T--)
	{
		LL n,m;
		scanf("%lld%lld",&n,&m);
		if(n==0)
		{
			printf("1\n");
			continue;
		}
		LL inv = Inv(m-1);
		LL ans = ((quick_mod(m,n+1)-1)*inv)%mod;
		printf("%lld\n",ans);
	}
}

  

   2
1 2
2 3
  

  

   3
13