洛谷 P8557 炼金术 题解

题目大意

给定 \(n\) 种金属，放进 \(k\) 个熔炉，要求最终每种金属都要能从熔炉里拿出来，求熔炉炼金的方案数对 \(998244353\) 取模。

分析

从金属角度考虑。

不难发现对于每一种金属因为一定在某一熔炉中被炼金，所以其一共有 \(\binom{k}{1}+\binom{k}{2}+\binom{k}{3}+...+\binom{k}{k}=2^k-1\) 种放入熔炉的方法。

对于每一种金属都有这么多种方法，乘法原理乘起来即可。因此答案是 \((2^k-1)^n\)。

实现

由于 \(2^k\operatorname{mod}998244353\not=0\)，因此不用担心 \(2^k-1\) 出现负数的情况，直接大胆的使用快速幂将其算出来即可。

#define int long long
inline int read(){
	int s=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) s=s*10+c-'0';
	return s*f;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar('0'+x%10);
}
const int MOD=998244353;
inline int ksm(int x,int y){
	if(y==0) return 1;
	else if(y%2==1) return x*ksm(x,y-1)%MOD;
	else{
		int tmp=ksm(x,y/2)%MOD;
		return tmp*tmp%MOD;
	}
}
int n,k;
//ans: (2^k-1)^n
signed main()
{
	n=read(),k=read();
	write(ksm(ksm(2,k)-1,n)),puts("");
	return 0;
}