ARC147D Sets Scores

题目大意

定义一个长度为$n$的数集序列 S : { s 1 , ⋯   , s n } S:\{s_1,\cdots,s_n\} S:{s1​,⋯,sn​}是好的，当且仅当$\forall i\in [1,n-1],|s_i/s_{i-1}|=1或|s_{i-1}/s_i|=1$，$s_i\subset [1,m]$，定义一个数集序列$S$的贡献为${\prod }_{i=1}^m{\sum }_{j=1}^n[i\in s_j]$，求所有数集序列的贡献的和，对$998244353$取模
$$n,m\le 200000$$

题解

设$x_i$表示只在$s_i$和$s_{i+1}$中出现一次的元素
现在考虑已知$x_i,i\in [1,n-1]$，怎么求答案，需要考虑每个元素一开始是否在$s_1$中，发现各个元素之间互不影响，且若$a_i$为$s_1$中有$i$，$i$在所有集合中出现的个数，则$s_1$中没$i$，$i$在所有集合中出现的个数为$n-a_i$，所以有贡献和为${\prod }_{i=1}^m(a_i+n-a_i)=n^m$，可以发现$x$是什么与答案并无关系，故再乘上$x$的方案数$m^{n-1}$即为答案

$\text{code}$

#include
#define ll long long
using namespace std;
const ll mod=998244353;
ll ksm(ll a,ll b)
{
	if(b==0) return 1;
	ll tmp=ksm(a,b>>1);
	if(b&1) return tmp*tmp%mod*a%mod;
	else return tmp*tmp%mod;
}
int n,m;
int main()
{
	scanf("%d %d",&n,&m);
	printf("%lld\n",ksm(n,m)*ksm(m,n-1)%mod);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18