【HDU】5793 A Boring Question

2024-03-09 06:38

文章标签 hdu question boring 5793

本文主要是介绍【HDU】5793 A Boring Question，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A Boring Question

题目链接

A Boring Question

题目大意

要你求如下式子的值

\sum 0 \leq k 1, k 2 . . . k m \leq n \prod 1 \leq j < m (k j + 1 k j) mod 1000000007

$\sum_{0\leq k_1,k_2...k_m\leq n}\prod_{1\leq j<m}\binom{k_{j+1}}{k_j}\mod 1000000007$

题解

    这个题只是看上去吓人而已…
    比赛的时候大部分都是找规律过的，后来看官方题解才茅塞顿开。
    首先可以分析出来：这个和要是不为0，序列k必须非减，所以我们考虑非减的情况就行了。
    接下来开始化简：

∵ 序 列 非 减 ∴ \sum 0 \leq k 1, k 2 . . . k m \leq n \prod 1 \leq j < m (k j + 1 k j) = \sum k m n \sum k m - 1 k m . . . \sum k 1 = 0 k 2 (k 2 k 1) (k 3 k 2) . . . (k m k m - 1)

$\because 序列非减\\ \therefore \sum_{0\leq k_1,k_2...k_m\leq n}\prod_{1\leq j<m}\binom{k_{j+1}}{k_j}=\sum_{k_m}^n\sum_{k_{m-1}}^{k_m}...\sum_{k_1=0}^{k_2}\binom{k_2}{k_1}\binom{k_3}{k_2}...\binom{k_m}{k_{m-1}}$
注意到后面的积可以分别提到和式的前面。

\sum k m n \sum k m - 1 k m (k m k m - 1) \sum k m - 2 k m - 1 (k m - 1 k m - 2) . . . \sum k 1 = 0 k 2 (k 2 k 1)

$\sum_{k_m}^n\sum_{k_m-1}^{k_m}\binom{k_m}{k_{m-1}}\sum_{k_{m-2}}^{k_{m-1}}\binom{k_{m-1}}{k_{m-2}}...\sum_{k_1=0}^{k_2}\binom{k_2}{k_1}$
这时，我们发现最里面的一项就是

2k2 $2^{k_2}$ ，所以有：

\sum k m n \sum k m - 1 k m (k m k m - 1) \sum k m - 2 k m - 1 (k m - 1 k m - 2) . . . \sum k 2 k 3 (k 3 k 2) \cdot 2 k 2

$\sum_{k_m}^n\sum_{k_m-1}^{k_m}\binom{k_m}{k_{m-1}}\sum_{k_{m-2}}^{k_{m-1}}\binom{k_{m-1}}{k_{m-2}}...\sum_{k_2}^{k_3}\binom{k_3}{k_2}·2^{k_2}$
这时我们又发现此时的最后一项又可以由二项式展开来化简：

\sum k 2 k 3 (k 3 k 2) \cdot 2 k 2 = (2 + 1) k 3 = 3 k 3

$\sum_{k_2}^{k_3}\binom{k_3}{k_2}·2^{k_2}=(2+1)^{k_3}=3^{k_3}$
这样一直进行化简，最后可以得到：

\sum k m n \sum k m - 1 k m (k m k m - 1) \cdot (m - 1) k m - 1 = \sum k m n m k m

$\sum_{k_m}^n\sum_{k_m-1}^{k_m}\binom{k_m}{k_{m-1}}·(m-1)^{k_{m-1}}=\sum_{k_m}^nm^{k_m}$
这样在最后就是一个等比数列求和了。
最终结果：

a n s = m n + 1 - 1 m - 1

$ans=\frac{m^{n+1}-1}{m-1}$

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#define mod 1000000007
#define LL long longusing namespace std;int T;
LL n,m;LL pow_mod(LL a,LL b,LL c)
{LL ans=1;while (b){if (b&1) ans=(ans*a)%c;b>>=1;a=(a*a)%c;}return ans;
}int main()
{scanf("%d",&T);while (T--){scanf("%lld%lld",&n,&m);LL ans=(pow_mod(m,n+1,mod)-1)*pow_mod(m-1,mod-2,mod);ans=(ans+mod)%mod;printf("%I64d\n",ans);}return 0;
}