HDU 5793 A Boring Question (找规律+快速幂)

HDU 5793 A Boring Question (找规律+快速幂)

A Boring Question

​

Source

​​2016 Multi-University Training Contest 6 ​​

题意：用m个不大于n的数构成一个序列，对每个序列求C(kj+1,kj)的连乘积。求出所有可能的序列，累加这些连乘积。

题解：打表找规律啊。f(n,m)

f(1,2)=3; f(1,6)=7; f(2,2)=7; f(2,6)=43; f(3,2)=15 f(1,3)=4; f(1,7)=8; f(2,3)=13; f(2,7)=57; f(3,3)=40 f(1,4)=5; f(1,8)=9; f(2,4)=21;  f(2,8)=73;  f(3,4)=85 f(1,5)=6; f(1,10)=11; f(2,5)=31; f(2,9)=91;  f(3,5)=156

然后找规律：

f(n,m) = f(n-1,m) + m^n = m^0 + m^1 + m^2 + ... + m^n; (等比数列求和) = (1 - m^(n+1)) / (1 - m);

官方题解：

AC代码：

#includeusing namespace std;typedef long long ll;const int mod=1e9+7;ll q_mod(ll a,ll n){ ll ans=1; while(n){ if(n&1)ans=ans*a%mod; n>>=1; a=a*a%mod; } return ans;}int main(){ int t; scanf("%d",&t); while(t--){ ll n,m; scanf("%lld%lld",&n,&m); printf("%lld\n",(q_mod(m,n+1)-1)*q_mod(m-1,mod-2)%mod); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。