题目大意
给定 \(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;
}
标签:10,洛谷,int,题解,return,熔炉,ksm,P8557,binom
From: https://www.cnblogs.com/AllWeKnow/p/16751035.html