Alice and the List of Presents

· · 题解

解析

我们先考虑 1 种物品放进 m 个背包的方法。

很显然，这个物品对于每个背包，都有放与不放两种选择，所以可以想到有 2^m 种方案。如果你不知道为什么的话，建议你从头开始学数学。

但是呢，因为必须要求这个物品在 m 个背包内至少出现一次，所以不能让这个物品在 m 个背包内一次都不出现，即让 m 个背包都为空，所以方案数变为 2^m - 1。

接下来，我们考虑 n 种物品。

因为每种物品都和上面讲的一样，有 2^m - 1 种方案，并且没有其他任何限制，所以我们可以得出总方案数为 (2^m - 1)^n。

这题 n 和 m 都比较大，暴力算幂妥妥的TLE，所以考虑使用快速幂统计答案，时间复杂度 O(\log(n + m))，空间复杂度 O(1)。

另外，这题其实是个双倍经验，另一道题为神鱼的炼金术，只要改个模数就能过了，切完这题后可以顺便把炼金术也切了。

code

#include<bits/stdc++.h>
#define mod 1000000007
#define int1 long long
using namespace std;
int1 n,k;
int1 read(){
    int1 x = 0,f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-'){
            f = -1;
        }
        ch = getchar();
    }
    while(isdigit(ch)){
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return x * f;
}
void print(int1 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9){
        print(x / 10);
    }
    putchar(x % 10 + 48);
    return ;
}
int1 quick_pow(int1 a,int1 b,int1 p){//快速幂。
    int1 s = 1;
    while(b){
        if(b & 1){
            s = (s % p) * (a % p) % p;
        }
        a = (a % p) * (a % p) % p;
        b >>= 1;
    }
    return s;
}
int main(){
    n = read(),k = read();
    print(quick_pow(quick_pow(2,k,mod) - 1,n,mod));//直接套公式。
    return 0;
}