E - Everything on It | AtCoder Regular Contest 096
公式解説動画のとおりに実装。
ちなみに22k mod p (pは素数)はフェルマーの小定理より 22k mod (p-1) mod p で求まる。
vector<vi> dp; int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); int N, M; while (cin >> N >> M) { MOD = M; dp = vector<vi>(N + 1, vi(N + 1)); dp[0][0] = 1; for (int a = 1; a <= N; ++a)for (int b = 0; b <= a; ++b) { sadd(dp[a][b], dp[a - 1][b]); if (b > 0) { sadd(dp[a][b], dp[a - 1][b - 1]); sadd(dp[a][b], mul(dp[a - 1][b], b)); } } vi A(N + 1); rep(a, N + 1) { MOD = M - 1; int p = powm(2, N - a); MOD = M; int q = powm(2, p); rep(b, a + 1) { int r = powm(2, (ll)(N - a)*b); int s = mul(q, mul(dp[a][b], r)); sadd(A[a], s); } } auto C = combinations(N, M); int re = 0; rep(a, N + 1) { int p = mul(C[N][a], A[a]); if (a % 2)p = mul(p, -1); sadd(re, p); } cout << re << endl; } }