AT_arc147_d [ARC147D] Sets Scores 题解

w9095 · 2025-12-13 19:56:15 · 题解

AT_arc147_d [ARC147D] Sets Scores

组合意义好。

考虑得分的组合意义。我们从 1 到 n 依次从包含这个数的集合中选择一个，方案数即为得分。

对这个东西做组合意义。考虑对某一个固定的选取的集合的序列，统计有多少满足要求整数集合序列。这样的选取的集合的序列有 n^m 个。

我们发现，对称差中恰好有 1 个元素等价于序列中除第一个集合，之后每一个集合和前一个相差且仅相差一个元素。也就是说，利用第一个集合和 n-1 个元素，我们就可以唯一确定这个整数集合序列，形成双射。

考虑对第一个集合和 n-1 个元素计数。选取的集合的序列本质上是要求某个集合中存在某一个元素。注意到，如果 n-1 个元素已经确定，我们可以使用第一个集合满足所有性质，因为在第一个集合中所有元素互不影响，且此时第一个集合是唯一确定的。

因此，方案数即为 n-1 个元素任意选择，方案数为 m^{n-1}。利用乘法原理，最后的答案为 n^mm^{n-1}。

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int mod=998244353;
int power(int a,int p)
{
    int x=a,ans=1;
    while(p)
       {
        if(p&1)ans=1ll*ans*x%mod;
        p>>=1;
        x=1ll*x*x%mod;
       }
    return ans;
}

int main()
{
    scanf("%d%d",&n,&m);
    printf("%lld\n",1ll*power(n,m)*power(m,n-1)%mod);
    return 0;
}