题解 [牛客挑战赛39E] 牛牛与序列

• 牛牛与序列

先口胡一下做法，明天再来补充一下吧。

主要问题其实是求单调不降的序列个数。

考虑把原序列转化成差分序列。

然后就是一个插板的事情了。

#include <bits/stdc++.h>
#define N 1000005

using namespace std;

const int mod = 998244353;

int n, k;
int fac[N + 3], ifac[N + 3];

inline int perm(int x, int y) { return 1LL * fac[x] * ifac[x - y] % mod; }
inline int comb(int x, int y) { return 1LL * perm(x, y) * ifac[y] % mod; }

inline int fpm(int x, int y) {
    int r = 1;
    while(y) {
        if(y & 1) r = 1LL * r * x % mod;
        x = 1LL * x * x % mod, y >>= 1;
    }
    return r;
}

inline int calc(int x, int y) {
    int res = ifac[y - 1];
    for(int i = x + y - 1; i > x; --i)
        res = 1LL * i * res % mod;
    return res;
}

int main() {
    fac[0] = 1;
    for(int i = 1; i <= N; ++i) fac[i] = 1LL * i * fac[i - 1] % mod;
    ifac[N] = fpm(fac[N], mod - 2);
    for(int i = N; i; --i) ifac[i - 1] = 1LL * i * ifac[i] % mod;

    int Case;
    scanf("%d", &Case);
    while(Case--) {
        scanf("%d %d", &n, &k);
        int ans = (0LL + fpm(k, n) - (calc(n, k) << 1) % mod + k + mod) % mod;
        printf("%d\n", ans);
    }
    return 0;
}