【题目来源】https://www.luogu.com.cn/problem/P8557【题目描述】铃是一个爱玩游戏的女孩子。她在游戏中想要炼制一种稀有合金 —— 这需要 n 种金属来合成。她准备好矿石后建造了 k 个不同的熔炉当熔炉启动时会随机炼出这 n 种金属中的一些也可能什么都没有。如果把每个熔炉炼出的金属收集起来有了全部 n 种金属就能造出合金了。澪对此很好奇对铃说「我考考你有多少种情况可以炼出合金呢」这个简单的问题铃很快就会做了你能求出结果吗答案可能很大请对 998244353 取模即除以 998244353 的余数后输出。【输入格式】输入一行两个正整数 n,k。【输出格式】输出一行一个整数表示答案。​​​​​​​【输入样例】233 123​​​​​​​【输出样例】81633405​​​​​​​【数据范围】对于 30% 的数据1≤n,k≤10对于 80% 的数据1≤n,k≤10^6对于 100% 的数据1≤n,k≤10^9。【算法分析】● 对于任意一种金属它可以被任意 1∼k 个熔炉所造出来方案总数为C(k,1)C(k,2)C(k,3)⋯⋯C(k,k−1)C(k,k)2^k-1现在有 n 种金属每一种金属有 2^k-1 种方法总方案数为 (2^k-1)^n配上快速幂模板即可。● 快速幂经典代码#include bits/stdc.h using namespace std; typedef long long LL; int fastPow(LL a,LL n) { LL ans1; while(n){ if(n 1) ansans*a; n1; aa*a; } return ans; } int main() { int a,n; cinan; coutfastPow(a,n)endl; } /* in:6 8 out:1679616 */● 带取模的快速幂代码计算过程中为了防止溢出需要进行“取模”运算其运算规则如下(ab)%p(a%pb%p)%p(a-b)%p(a%p-b%p)%p(a*b)%p(a%p*b%p)%p【算法代码】#include bits/stdc.h using namespace std; typedef long long LL; const int p998244353; LL fastPow(LL a,LL n) { LL ans1; while(n) { if(n 1) ansans*a%p; aa*a%p; n1; } return ans; } int main() { int n,k; scanf(%d%d,n,k); printf(%lld,fastPow(fastPow(2,k)-1,n)); return 0; } /* in:233 123 out:81633405 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/143135845