solution
考虑求答案的补集。也就是计算有多少个序列不是反复横跳的。
这样的序列肯定是单调不降序列或者是单调不升序列。
又因为所有数字不超过k。
以单调不降序列为例(单调不升序列个数与其相等)。我们枚举最后一个数字的大小。然后对这个序列做一下差分,也就是令。这样就转化成了有多少个满足条件的序列,满足什么条件呢?只要满足。这是经典的组合问题,相当于把x个物品分为b份,每份可以为空,用隔板法可以看出答案就是
所以这种序列的个数就是
因为题目要求,所以只要将上面的变为所给的k-1即可。
因为有种序列是既单调不升又单调不降的,所以要减去k。
综上,答案就是
将那个组合数拆开,发现复杂度是可以接受的。
code
/* * @Author: wxyww * @Date: 2020-04-17 20:59:52 * @Last Modified time: 2020-04-17 22:01:07 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int mod = 998244353; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } ll qm(ll x,ll y) { ll ret = 1; for(;y;y >>= 1,x = x * x % mod) { if(y & 1) ret = ret * x % mod; } return ret; } int main() { int T = read(); while(T--) { ll n = read(),K = read(); ll ans = (qm(K,n) + K) % mod,now = 1; --K; for(ll i = n + 1;i <= n + K;++i) now = now * i % mod; ll tmp = 1; for(int i = 1;i <= K;++i) tmp = tmp * i % mod; now = now * qm(tmp,mod - 2) % mod; now = (now + now) % mod; cout<<(ans - now + mod) % mod<<endl; } return 0; }