题目: 输入n,k求\(\sum_{i = 1}^{n} i^k\) 。
题解: 这个和是k+1次的多项式,我们用k+2个值就可以唯一确定这个多项式,计算f(n)即可
int main()
{
scanf("%lld%lld",&n,&k);
pre[0] = suf[k + 3] = fac[0] = 1;
for(int i = 1; i <= k + 2; ++ i) pre[i] = pre[i - 1] * (n - i) % mod;
for(int i = k + 2; i >= 1; -- i) suf[i] = suf[i + 1] * (n - i) % mod;
for(int i = 1; i <= k + 1; ++ i) fac[i] = fac[i - 1] * i % mod;
for(int i = 1, y = 0; i <= k + 2; ++ i){
y = (y + qpow(i, k)) % mod;
ll s1 = pre[i - 1] * suf[i + 1] % mod;
ll s2 = fac[i - 1] * ((k - i) & 1 ? -1ll : 1ll) * fac[k + 2 - i] % mod;
res = (res + y * s1 % mod * qpow(s2, mod - 2) % mod) % mod;
}
printf("%lld\n",res);
return 0;
}
原文链接: https://www.cnblogs.com/A-sc/p/12785686.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/344836
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!