【CF1312D】Count the Arrays（计数）

676 浏览 0 回复 2020-03-12

_奶酪

+关注

题目：
思路：
n个元素有一对相同的，那么n个数***有n-1个不同的数，从m个数中选n-1，方法数： $C_{m}^{n - 1}$
从n-1个不同的数中选择一个数使其在要构造的数组中出现两次，最大的数是唯一的，不能选它，所以方法数为：n-2
除了重复出现的数一个在最大数的左边，一个在右边外，其他n-3个数可以出现在最大数的左边/右边，方法数为： $2^{n - 3}$
故 $a n s = C_{m}^{n - 1} * (n - 2) * 2^{n - 3}$ ，注意用逆元求解。
ac代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
const ll mod = 998244353;
ll n, m;
ll fac[maxn], p2[maxn];
ll qpow(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b&1) ans = ans*(a%mod)%mod;
        a = (a%mod)*(a%mod)%mod;
        b >>= 1;
    }
    return ans%mod;
}
void pre()
{
    fac[0] = p2[0] = 1;
    for(ll i = 1; i <= 2e5; i++)
    {
        fac[i] = fac[i-1]*i%mod;
        p2[i] = p2[i-1]*2%mod;
    }
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%lld %lld", &n, &m);
    if(n==2) printf("0");
    else
    {
        pre();
        ll di = fac[n-1]*fac[m-n+1]%mod;
        ll ans = fac[m]*(n-2)%mod*p2[n-3]%mod*qpow(di, mod-2)%mod;
        printf("%lld", ans);
    }
    return 0;
}