2021牛客国庆集训派对day6 C Generation I

Oak is given N empty and non-repeatable sets which are numbered from 1 to N.

Now Oak is going to do N operations. In the i-th operation, he will insert an integer x between 1 and M to every set indexed between i and N.

Oak wonders how many different results he can make after the N operations. Two results are different if and only if there exists a set in one result different from the set with the same index in another result.

Please help Oak calculate the answer. As the answer can be extremely large, output it modulo 998244353.

本文参考了文章牛客网暑期ACM多校训练营(第六场) C （简单排列组合+逆元）_Jiandong-CSDN博客

给定n行，每行具有n个数字，我们需要对这个三角形进行填写数字的操作，对于每一列，我们都需要填写相同的数字，但是这些数字是从1--m，每行作为一个集合，请问我们可以构造出多少个集合的数量

首先我们通过题目可以得出以下几个性质：

1.对于任意第i(i <= n - 1)行，第i行构成的集合必定是第(i + 1)行的子集

2.在最后一行填入数字相同的情况下，填入数字的顺序会影响集合的构成

比如以下两个数字三角形

1                                       1

1    2                                 1   3

1    2    3                           1   3   2

他们所构成的集合是不一样的

因此我们可以知道，最后一行的数字的顺序会影响相应集合的构成

我们对最后一行需要取的数字个数考虑

假设我们需要取K个，然后对这K个相对出现位置进行排序

排序完之后我们需要考虑这些数字第一次出现的位置，则是C（K - 1,N - 1）;

对应的式子如下所示

化简之后得到

然后对于带有除数的式子，进行乘法逆元的操作，接下来就可以解决了

乘法逆元：替代mod 中除以A，用乘以A的逆元来替代

一个数A的逆元（p为质数）数的（p - 2）次方

求逆元更普遍的方式是采用扩展欧几里得的方式

void exgcd(ll a,ll b,ll& d,ll& x,ll& y)
{
    if(!b) { d = a; x = 1; y = 0; }
    else{ exgcd(b, a%b, d, y, x); y -= x*(a/b); }
}

ll inv(ll a, ll p)
{
    ll d, x, y;
    exgcd(a, p, d, x, y);
    return d == 1 ? (x+p)%p : -1;
}