题面

题解

由于每个元素是独立的, 所以我们只用对于每个元素都算一次就行了

对于单一的一个元素, 可以看成从最左下角引一条向右或向上的折线, 折线左上方这个元素都被选, 折线右下方都不选

因为总共向右或向上只能走 \(k\) 步, 每次向右或向上均可, 所以是 \(2 ^ k\)

再来个 \(n\) 次幂代表元素之间互相独立即可

注意欧拉定理

Code

#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>const int mod = 1e9 + 7; using namespace std;int n, k; template < typename T >inline T read(){ T x = 0, w = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * w; }int fpow(int x, int y){ int res = 1; for( ; y; y >>= 1, x = 1ll * x * x % mod) if(y & 1) res = 1ll * res * x % mod; return res; }int main(){ n = read <int> (), k = read <int> (); printf("%d\n", fpow(2, 1ll * n * k % (mod - 1))); return 0; }