牛客网-小白月赛6-J-洋灰三角
题目链接https://www.nowcoder.com/acm/contest/136/J
这题我还是不找规律了，老老实实推吧，传说找规律也可以，我还是算了
递推式:f(n)=k*f(n-1)+p
是的，你没有看错，这玩意是什么？？？是高中的数列求和啊，什么你没看出来，这玩意外号——一阶线性递推
等式两边同时加p/k-1 f(n)+p/(k-1) = k(f(n-1)+p/k-1);不信你可以推一下试试
那么f(n)可以通过等比数列求出f(n)=p/(k-1)*(k^(n-1))-p/(n-1);
再用分组求和那么前n项和公式为T(n)=(k^n-1)/(k-1)+p*(k^n-1)/(k-1)^2-p*n/(k-1)=(1+p/(k-1))*(k^n-1)/(k-1)-p*n/(k-1)
注意当n==1时T(n)=p*n*(n-1)/2+n;
有分数。求一下(k-1) % 1e9+7的逆元inv=pow(k-1,mod-2);
#include<iostream>
#include<string.h> #include<algorithm> #include<stdio.h> #define ll long long using namespace std;; const ll mod = 1e9+7; ll pow(ll a,ll b) { ll ans = 1; while(b) { if (b&1) { ans = ans*a%mod; } a = a*a%mod; b/=2; } return ans; } int main() { ios::sync_with_stdio(0); ll n,k,p; ll ans=0; while(~scanf("%lld%lld%lld",&n,&k,&p)) { if (k==1) { ans=(n*(n-1)%mod/2*p+n)%mod; printf("%lld\n",ans); } else { ll inv=pow(k-1,mod-2); ans=(1+p*inv%mod)%mod*((pow(k,n)-1+mod)%mod)%mod*inv%mod; ans=(ans-p*inv%mod*n%mod+mod)%mod; printf("%lld\n",ans); } } return 0; }
百威成长空间 50人发布
投递中国南方电网等公司10个岗位 >