Count the Arrays-codeforce 1312D

Posted by

Count the Arrays-codeforce 1312 D

Count the Arrays

排列组合

n个数中有两个是相同的,那其余的n-1个数的选择方案就是\binom{m}{n-1}
n-1个数里选择一个数让它重复出现,但是不能选最大的,就有了n-1-1=n-2

对于一个长度为n的数组,让它满足a_ja_{j+2},其方案数一共有2^{n-1}
除了最大的数无法移动,其余的数都可以移动到最大的数的左边或者右边,在这里是2^{n-3}.
最终答案就是\binom{m}{n-1} * (n-2) * 2^{n-3}

其中x^{MOD – 2}这个操作是求x关于MOD的逆元,因为在次数无法用除法,所以用逆元来表示,相当于\frac{1}{x}

#include <bits/stdc++.h>

using namespace std;

typedef long long int  ll;
const int MOD = 998244353;
ll n, m;
ll a[200010];

ll square ( ll x ) { return x * x; }

ll fast_expt( ll b, ll n )
{
    if ( n == 0 ) return 1;
    else if ( n % 2 == 0 ) return square( fast_expt_and_mod( b, n >> 1 ) ) % MOD;
    return b * fast_expt_and_mod( b, n - 1 ) % MOD;
}


ll C( ll up, ll down )
{
    a[1] = 1;
    for ( ll i = 2; i <= down; i ++ ) a[i] = a[i-1] * i % MOD;
    return a[m] * fast_expt_and_mod(a[down - up], MOD - 2) % MOD * fast_expt_and_mod( a[up], MOD - 2 ) % MOD;
}

int main()
{
    scanf("%lld %lld", &n, &m);
    if ( n == 2 ) printf("0\n");
    else printf( "%lld\n",  (fast_expt(2, n - 3) % MOD * ( n - 2 )  % MOD) % MOD * C( n - 1, m ) % MOD  );

    return 0;
}

Leave a Reply

邮箱地址不会被公开。 必填项已用*标注