关键词:数学-数论   斯特林数   伯努利数 相关题目:[WZOJ] 次方和

Sum Of Powers

题目描述

给定两个整数 nnkk ,请你给出 i=1nik\sum_{i=1}^{n}i^{k}998244353998244353 取模的值。

输入输出格式

输入格式: 一个整除 ,表示测试组数。 对于每一组测试,对应一行的两个正整数

输出格式: 对于每一组测试,输出答案占一行。

样例输入:

1
2
1
4 4

样例输出:

1
354

解决方案

请参考博文:简单常用的几种计算自然数幂和的方法 请参考博文:伯努利数与自然数幂和 正解:by Massimo

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//-----------------------------------------
#include<cstdio>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define N 1002
typedef long long ll;
const ll p=998244353;
ll C[N][N],B[N],inv[N],nk[N];
int n,k;

inline void init(){
C[0][0]=1;
rep(i,1,N-1){
C[i][0]=C[i][i]=1;
rep(j,1,i-1){
C[i][j]=C[i-1][j]+C[i-1][j-1];
if(C[i][j]>=p) C[i][j]-=p;
}
}//处理组合数

inv[1]=1;
rep(i,2,N-1)
inv[i]=(p-p/i)*inv[p%i]%p;//处理数论倒数

B[0]=1;
rep(i,1,N-1){
ll res=0;
if(i==N-1) break;
rep(j,0,i-1)
res=(res+C[i+1][j]*B[j])%p;
res*=-inv[i+1];
res=res%p+p;
if(res>=p) res-=p;
B[i]=res;
}//处理伯努利数
}
inline void init_nk(){
nk[0]=1;
rep(i,1,k+1)
nk[i]=nk[i-1]*(n+1)%p;
}
inline void solve(){
ll ans=inv[k+1],sum=0;
rep(i,1,k+1){
sum+=C[k+1][i]*nk[i]%p*B[k+1-i]%p;
sum%=p;
}
ans*=sum;
printf("%lld",ans%p);
}

int main(){
init();
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
n%=p;
init_nk();
solve();
if(T) putchar('\n');
}
return 0;
}
//-----------------------------------------
/*
problem: Sum Of Powers
from: https://wzoi.cc/s/1450/2446
solved by: ZqlwMatt
题解用Stirling numbers.求解
而我偏偏喜欢用伯努利数(2333)
解题过程参考了某神犇的方法
*/