提出 #41647634

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
const int N = 3010;
int n, MOD, C[N][N], S[N][N], pw2[N], pw22[N], ans;
int power(int x, int y = MOD - 2) {
	int ans = 1;
	for (; y; x = (ll) x * x % MOD, y >>= 1)
		if (y & 1) ans = (ll) ans * x % MOD;
	return ans;
}
signed main() {
	read(n), read(MOD);
	pw22[0] = pw2[0] = S[0][0] = C[0][0] = 1;
	F(i, 1, n + 1) {
		pw2[i] = (pw2[i - 1] + pw2[i - 1]) % MOD;
		pw22[i] = (pw22[i - 1] + pw22[i - 1]) % (MOD - 1);
		C[i][0] = 1;
		F(j, 1, i)
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD,
			S[i][j] = ((ll) j * S[i - 1][j] + S[i - 1][j - 1]) % MOD;
	}
	F(a, 0, n) {
		int t1 = (ll) C[n][a] * ((a & 1) ? MOD - 1 : 1) % MOD * power(2, pw22[n - a]) % MOD;
		F(b, 0, a) {
			int t2 = (ll) S[a + 1][b + 1] * power(pw2[n - a], b) % MOD;
			// cout << t1 << " " << t2 << " " << (ll) S[a + 1][b + 1] * power(pw2[n - a], b) % MOD << endl;
			ans = (ans + (ll) t1 * t2) % MOD;
		}
	} cout << ans;
	return 0;
}

提出情報

ジャッジ結果