随机序列 [思维题, 组合数]

$随机序列$

---

$color{red}{正解部分}$

首先要发现一个性质, 将序列分为若干 极长不上升子段 后,

• 每段长度 小于等于 $2$ .
• 第 $i$ 段的 最大值 小于 第 $i+1$ 段 的 最小值 .

题目要求将每个位置填上 $[1, K]$ 之间的数字 且 需要满足上述性质,

每个长度为 $2$ 的子段 中的数字可以相同, 也可以不同, 于是

$Answer = sumlimits_{i=0}^{lfloor frac{n}{2} floor} egin{pmatrix} n-i \ i end{pmatrix} egin{pmatrix} k+i \ n end{pmatrix}$ .

---

$color{red}{实现部分}$

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 10000005;
const int mod = 998244353;

int N;
int K;
int fac[maxn];

int Ksm(int a, int b){
        int s = 1;
        while(b){ if(b&1) s=1ll*s*a%mod; a=1ll*a*a%mod; b >>= 1; }
        return s;
}

int C(int n, int m){ 
        if(n < m) return 0;
        return 1ll*fac[n]*Ksm(fac[m], mod-2)%mod*Ksm(fac[n-m], mod-2)%mod;
}

int main(){
//        freopen("data.in", "r", stdin);
//        freopen("data.out", "w", stdout);
        N = read(), K = read();
        fac[0] = 1; for(reg int i = 1; i < maxn; i ++) fac[i] = 1ll*fac[i-1]*i % mod;
        ll Ans = 0;
        int half = N >> 1;
        for(reg int i = 0; i <= half; i ++){
                Ans += 1ll*C(N-i, i)*C(K+i, N)%mod;
                Ans %= mod;
        }
        printf("%lld
", 1ll*Ans*Ksm(Ksm(K, N), mod-2)%mod);
        return 0;
}