数学题

也许更好的阅读体验

$Description$Description

给 $n,b,k$n,b,k,求
$\begin{array}{c}{\displaystyle \sum _{i=1}^n\left(\begin{array}{c}i\\ k\end{array}\right)b^i}\end{array}$i=1∑n​(ik​)bi​

答案对 $998244353$998244353取模

$1\le k\le 500000,1\le n\le 10^{18},2\le b\le 998244353$1≤k≤500000,1≤n≤1018,2≤b≤998244353

$Solution$Solution

设
$\begin{array}{c}{\displaystyle f_k=\sum _{i=1}^n\left(\begin{array}{c}i\\ k\end{array}\right)b^i}\end{array}$fk​=i=1∑n​(ik​)bi​
则有
$\begin{array}{c}{\displaystyle f_{k-1}=\sum _{i=1}^n\left(\begin{array}{c}i\\ k-1\end{array}\right)b^i}\end{array}$fk−1​=i=1∑n​(ik−1​)bi​

$\begin{array}{c}{\displaystyle b{f}_k=\sum _{i=2}^{n+1}\left(\begin{array}{c}i-1\\ k\end{array}\right)b^i}\end{array}$bfk​=i=2∑n+1​(i−1k​)bi​

$\begin{array}{c}{\displaystyle b{f}_{k-1}=\sum _{i=2}^{n+1}\left(\begin{array}{c}i-1\\ k-1\end{array}\right)b^i}\end{array}$bfk−1​=i=2∑n+1​(i−1k−1​)bi​

$\begin{array}{c}{\displaystyle b{f}_k+b{f}_{k-1}=\sum _{i=2}^{n+1}(\left(\begin{array}{c}i-1\\ k\end{array}\right)+\left(\begin{array}{c}i-1\\ k-1\end{array}\right))b^i=\sum _{i=2}^{n+1}\left(\begin{array}{c}i\\ k\end{array}\right)b^i=f_k+\left(\begin{array}{c}n+1\\ k\end{array}\right)b^{n+1}-\left(\begin{array}{c}1\\ k\end{array}\right)b}\end{array}$bfk​+bfk−1​=i=2∑n+1​((i−1k​)+(i−1k−1​))bi=i=2∑n+1​(ik​)bi=fk​+(n+1k​)bn+1−(1k​)b​

移项得

$(b-1)f_k=\left(\begin{array}{c}n+1\\ k\end{array}\right)b^{n+1}-\left(\begin{array}{c}1\\ k\end{array}\right)b-b{f}_{k-1}$(b−1)fk​=(n+1k​)bn+1−(1k​)b−bfk−1​

$f_k={\displaystyle \frac{\left(\begin{array}{c}n+1\\ k\end{array}\right)b^{n+1}-\left(\begin{array}{c}1\\ k\end{array}\right)b-b{f}_{k-1}}{b-1}}$fk​=b−1(n+1k​)bn+1−(1k​)b−bfk−1​​

当 $k=0$k=0时，要求的就是一个等比数列，我们用等比数列求和公式直接算就可以了

$f_0={\displaystyle \frac{b^{n+1}-b}{b-1}}$f0​=b−1bn+1−b​

总复杂度 $O\left(k\right)$O(k)

$Code$Code

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年09月17日 星期二 10时54分50秒 *******************************/
#include <cstdio>
#include <fstream>
#define ll long long
using namespace std;
const int mod = 998244353;
const int maxn = 500005;
ll n,b,k,ans;
ll invb,mi,C;
ll inv[maxn];
//{{{ksm
ll ksm (ll a,ll b)
{
	a%=mod;
	ll s=1;
	for (;b;b>>=1,a=a*a%mod)
		if (b&1)	s=s*a%mod;
	return s;
}
//}}}
int main()
{
	scanf("%lld%lld%lld",&n,&b,&k);
	C=(n+1)%mod,inv[1]=1,invb=ksm(b-1,mod-2);
	for (int i=2;i<=k;++i)	inv[i]=(-mod/i*inv[mod%i]%mod+mod)%mod;
	ans=(ksm(b,n+1)-b+mod)%mod*invb%mod;
	mi=ksm(b,n+1);
	if (n<k){	printf("0\n");return 0;}
	if (n==k){	printf("%lld\n",ksm(b,n));return 0;}
	for (int i=1;i<=k;++i){
		ll t=0;
		if (i<=1)	t=b;
		ans=((C*mi%mod-t-b*ans%mod)%mod+mod)%mod*invb%mod;
		C=(n-i+1)%mod*C%mod*inv[i+1]%mod;
	}
	printf("%lld\n",ans);
	return 0;
}

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧