Submission #3013641
Source Code Expand
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define int long long
using namespace std;
typedef pair<int, int> Pii;
template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);
int calcmod(int x, int M){
if(x >= 0) return x % M;
int n = -1 * (x / M) + 1;
return (x + n * M) % M;
}
int extgcd(int a, int b, int &x, int &y){
int d = a;
if(b != 0){
d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
}else{
x = 1;
y = 0;
}
return d;
}
int mod_inverse(int a, int m){
int x, y;
extgcd(a, m, x, y);
return (m + x % m) % m;
}
signed main(){
int N, M;
cin >> N >> M;
vector< vector<int> > dp(N + 1, vector<int>(N + 1, 0));
FOR(i, 0, N + 1){
dp[i][0] = 1;
}
FOR(j, 1, N + 1){
dp[0][j] = 0;
}
FOR(i, 1, N + 1){
FOR(j, 1, N + 1){
dp[i][j] = (dp[i - 1][j - 1] + (j + 1) * dp[i - 1][j]) % M;
}
}
//2^(i*j)
vector< vector<int> > pow1(N + 1, vector<int>(N + 1, 1));
FOR(i, 1, N + 1){
pow1[i][1] = (2 * pow1[i - 1][1]) % M;
}
FOR(i, 1, N + 1){
FOR(j, 2, N + 1){
pow1[i][j] = (pow1[i][j - 1] * pow1[i][1]) % M;
}
}
//2^(2^i)
vector<int> pow2(N + 1, 1);
REP(i, N + 1){
//2^(M-1)=1(mod M)
//2^i mod(M-1)を知りたい
int t = 1;
for(int j = 50; j >= 0; j--){
t = (t * t) % (M - 1);
if(((i >> j) & 1) == 1){
t = (t * 2) % (M - 1);
}
}
//2^t mod Mを求める
for(int j = 50; j >= 0; j--){
pow2[i] = (pow2[i] * pow2[i]) % M;
if(((t >> j) & 1) == 1){
pow2[i] = (pow2[i] * 2) % M;
}
}
}
vector<int> ways(N + 1);
vector< vector<int> > ways2(N + 1, vector<int>(N + 1));
FOR(i, 0, N + 1){
ways[i] = 0;
FOR(j, 0, i + 1){
ways2[i][j] = dp[i][j];
//j杯に他のトッピング載せる?(*2^(j*(N-i)))
ways2[i][j] = (ways2[i][j] * pow1[j][N - i]) % M;
//残りのN-i種類のトッピングのみで作る2^(N-i)種類のそれぞれ食べる?(*2^(2^(N-i)))
ways2[i][j] = (ways2[i][j] * pow2[N - i]) % M;
ways[i] = (ways[i] + ways2[i][j]) % M;
}
}
vector<int> fact(N + 1, 1);
FOR(i, 1, N + 1){
fact[i] = (fact[i - 1] * i) % M;
}
int ans = 0;
REP(i, N + 1){
int tmp = fact[N] * mod_inverse(fact[i], M) * mod_inverse(fact[N - i], M);
if(i % 2 == 0){
tmp = calcmod(tmp, M);
}else{
tmp = calcmod(-1 * tmp, M);
}
tmp = tmp * ways[i];
ans = (ans + tmp) % M;
}
cout << ans;
return 0;
}
template<typename T>
void readvec(vector<T> &a){
REP(i, a.size()){
cin >> a[i];
}
}
void readindex(vector<int> &a){
REP(i, a.size()){
cin >> a[i];
a[i]--;
}
}
Submission Info
Submission Time |
|
Task |
E - Everything on It |
User |
sumitacchan |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3259 Byte |
Status |
WA |
Exec Time |
659 ms |
Memory |
211712 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
0 / 600 |
0 / 300 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
a01, a02, a03, a04 |
Subtask1 |
a01, a02, a03, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24 |
Subtask2 |
a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, c25, c26, c27, c28, c29, c30, c31, c32, c33, c34, c35, c36, c37, c38, c39, c40, c41, c42, c43, c44 |
Case Name |
Status |
Exec Time |
Memory |
a01 |
AC |
1 ms |
256 KB |
a02 |
AC |
1 ms |
256 KB |
a03 |
WA |
1 ms |
256 KB |
a04 |
WA |
658 ms |
211712 KB |
b05 |
AC |
1 ms |
256 KB |
b06 |
AC |
1 ms |
256 KB |
b07 |
WA |
1 ms |
256 KB |
b08 |
WA |
1 ms |
256 KB |
b09 |
WA |
1 ms |
256 KB |
b10 |
WA |
1 ms |
256 KB |
b11 |
WA |
1 ms |
256 KB |
b12 |
WA |
1 ms |
256 KB |
b13 |
WA |
1 ms |
256 KB |
b14 |
WA |
1 ms |
256 KB |
b15 |
WA |
1 ms |
256 KB |
b16 |
WA |
1 ms |
256 KB |
b17 |
WA |
1 ms |
256 KB |
b18 |
WA |
1 ms |
256 KB |
b19 |
WA |
1 ms |
256 KB |
b20 |
WA |
1 ms |
256 KB |
b21 |
WA |
1 ms |
256 KB |
b22 |
WA |
1 ms |
256 KB |
b23 |
WA |
1 ms |
256 KB |
b24 |
WA |
1 ms |
256 KB |
c25 |
WA |
1 ms |
256 KB |
c26 |
WA |
2 ms |
384 KB |
c27 |
WA |
3 ms |
768 KB |
c28 |
WA |
5 ms |
1536 KB |
c29 |
WA |
12 ms |
3968 KB |
c30 |
WA |
25 ms |
8832 KB |
c31 |
WA |
50 ms |
17152 KB |
c32 |
WA |
111 ms |
37888 KB |
c33 |
WA |
256 ms |
82560 KB |
c34 |
WA |
466 ms |
150656 KB |
c35 |
WA |
623 ms |
200448 KB |
c36 |
WA |
643 ms |
205440 KB |
c37 |
WA |
653 ms |
208256 KB |
c38 |
WA |
651 ms |
209920 KB |
c39 |
WA |
655 ms |
210816 KB |
c40 |
WA |
655 ms |
211072 KB |
c41 |
WA |
658 ms |
211328 KB |
c42 |
WA |
658 ms |
211328 KB |
c43 |
WA |
659 ms |
211584 KB |
c44 |
WA |
659 ms |
211712 KB |