P8557 题解

· · 题解

这道题需要用到排列组合的知识，不会的建议去看我的博客。

我们可以先从这 n 种金属入手。

对于任意一种金属，它可以被任意 1 \sim k 个熔炉所造出来，方案总数为：

C^1_k+C^2_k+C^3_k+\cdots\cdots+C^{k-1}_k+C^k_k = 2^k-1

现在有 n 种金属，每一种金属有 2^k-1 种方法，总方案数为 (2^k-1)^n，配上快速幂模板即可。

#include<bits/stdc++.h>
#define int unsigned long long
#define endl '\n'
using namespace std;
const int mod = 998244353;

int ksm(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1)
            ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, k, ans = 0;
    cin >> n >> k;
    cout << ksm(ksm(2, k)-1, n) << endl;
    return 0;
}