【题解】CF1312D Count the Arrays

简单计数

题目链接:CF1312D 【Count the Arrays】

刚开始菜鸡 $\texttt{CXY07}$ 以为这是一道什么 $dp$,瞎想了好久好久......

首先我们可以发现,这个东西是一个单峰的数组,并且里面有且仅有一个数字出现了两次。

很快发现实际上一个这样的长度为 $n$ 的数组,实际上一共有 $n - 1$ 个不同的数字

那我们就先从 $m$ 个数字中拿 $n - 1$ 个,共 $C_{m}^{n-1}$ 种情况

那么显然中间有一个数字是最大的 废话,这个数字必须放在峰顶(?)的位置,其他的 $n - 2$ 个数字自然可以放在峰顶的左侧或者右侧

这里一共多少种情况呢?当然是 $2^{n-2}$ 种(每一个数字可以在左右中任意选择一边)

不难发现只要我们定下这 $n-2$ 个数字分别在峰顶的左边或者右边,整个数组就只有一种构造的方法了,而距离我们完成整个数组,就只差那个重复的值了

然后我们来定这个重复的值是谁,首先这个数字肯定不能是峰顶(题中是严格大于/小于)所以我们只能从剩下 $n-2$ 个值中间选择,并且无论你选择了哪一个值,它一定就已经在数组中出现了一次了。

那么,我们如果选择一个值,那么这个值已经出现在了峰顶的一侧,为了满足 严格大于/小于 的条件,我们只能把这个重复的值放在另外一边了

所以这里我们任意从 $n-2$ 个值中选择都是可行的,这里方案有 $n-2$ 种

但是有一个问题,这里可能会出现重复的情况:

比如:

如果现在我们需要构造一个长度为 $6$ 的序列,我们已经选择了 $1$ ~ $ 5$ 这几个值了,现在有这样两种方案:

1 2 5 4 3

1 5 4 3 2

如果我们想要再加入一个 $2$,那两个序列会同时变成:1 2 5 4 3 2 ,但是我们把他计算了两遍......

容易发现无论你选择哪一个值,都会出现这个情况,所以我们再 $\times \frac{1}{2}$ 就好了

所以最后答案为:

$$C_m^{n-1} \times 2^{n-2} \times (n-2) \times \frac{1}{2}$$

也就是:

$$C_m^{n-1} \times 2^{n-3} \times (n-2)$$

容易发现当 $n < 3$ 时无解,特判即可,我是在判断 $2$ 的幂的时候处理的

用了费马小定理求逆元,所以复杂度貌似带个 $log$

$Code:$

//Code By CXY
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define inv(x) ksm(x,mod - 2)

const int MAXN = 2e5 + 10;
const int INF = 2e9;
const int mod = 998244353;

int n,m;

inline int ksm(int a,int b) {
    if(b < 0) return 0;//判断一下即可
    if(a == 1) return 1;
    int res = 1;
    while(b) {
        if(b & 1) (res *= a) %= mod;
        (a *= a) %= mod;
        b >>= 1;
    }
    return res;
}

inline int C(int a,int b) {
    int res = 1;
    for(register int i = a;i >= a - b + 1; --i)
        (res *= i) %= mod;
    for(register int i = 1;i <= b; ++i)
        (res *= inv(i)) %= mod;
    return res;
}

signed main () {
    cin >> n >> m;
    cout << ksm(2,n - 3) % mod * C(m,n - 1) % mod * (n - 2) % mod << endl;
    return 0;//End.
}

初三的 $OIer$,请多关照

仅有 1 条评论
  1. 好强啊!!

添加新评论