Submission #3382047
Source Code Expand
#include<bits/stdc++.h>
#define For(i,l,r) for(int i = (l),i##end = (r);i <= i##end;i++)
#define Fordown(i,r,l) for(int i = (r),i##end = (l);i >= i##end;i--)
#define debug(x) cout << #x << " = " << x << endl
using namespace std;
typedef long long ll;
template <typename T> inline bool chkmin(T &x,T y) { return y < x ? x = y,1 : 0; }
template <typename T> inline bool chkmax(T &x,T y) { return x < y ? x = y,1 : 0; }
const int INF = 0x3f3f3f3f;
const int N = 3e3 + 10;
int S[N][N],Sum[N],ans[N][N],fac[N],inv[N];
inline int read() {
int x = 0,flag = 1;
char ch = getchar();
while(!isdigit(ch) && ch != '-')ch = getchar();
if(ch == '-')flag = -1,ch = getchar();
while(isdigit(ch))x = (x << 3) + (x << 1) + (ch - '0'),ch = getchar();
return x * flag;
}
inline int fpm(int a,int b,int mod) {
int res = 1;
while(b) {
if(b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod,b /= 2;
}
return res;
}
inline void init(int n,int mod) {
fac[0] = 1;
For(i,1,n) fac[i] = 1ll * fac[i - 1] * i % mod;
inv[n] = fpm(fac[n],mod - 2,mod);
Fordown(i,n,1) inv[i - 1] = 1ll * inv[i] * i % mod;
}
inline int C(int n,int m,int mod) {
return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {
int n = read(),mod = read();
init(n,mod);
S[0][0] = 1;
For(i,1,n) For(j,1,i)
S[i][j] = (S[i - 1][j - 1] + 1ll * S[i - 1][j] * j) % mod;
For(i,0,n) For(j,0,n - i) For(k,0,j){
int &res = ans[i][j];
res = (res + 1ll * S[j][k] * fpm(2,fpm(2,n - i - j,mod - 1) + 1ll * (n - i - j) * k % (mod - 1),mod)) % mod;
}
Fordown(i,n,0) Fordown(j,n - i,0) {
ans[i][j] = 1ll * ans[i][j] * C(n,i,mod) % mod * C(n - i,j,mod) % mod;
For(Ni,i,n) For(Nj,j,n) {
if(Ni == i && Nj == j) continue;
ans[i][j] = (ans[i][j] - 1ll * ans[Ni][Nj] * C(Ni,i,mod) % mod * C(Nj,j,mod) % mod + mod) % mod;
}
}
printf("%d\n",ans[0][0] % mod);
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Everything on It |
User |
ShichengXiao |
Language |
C++14 (GCC 5.4.1) |
Score |
600 |
Code Size |
1927 Byte |
Status |
TLE |
Exec Time |
4203 ms |
Memory |
36224 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
600 / 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 |
2 ms |
2304 KB |
a02 |
AC |
2 ms |
2304 KB |
a03 |
AC |
131 ms |
2560 KB |
a04 |
TLE |
4203 ms |
36224 KB |
b05 |
AC |
2 ms |
2304 KB |
b06 |
AC |
2 ms |
2304 KB |
b07 |
AC |
2 ms |
2304 KB |
b08 |
AC |
2 ms |
2304 KB |
b09 |
AC |
2 ms |
2304 KB |
b10 |
AC |
2 ms |
2304 KB |
b11 |
AC |
3 ms |
2304 KB |
b12 |
AC |
7 ms |
2432 KB |
b13 |
AC |
20 ms |
2432 KB |
b14 |
AC |
57 ms |
2432 KB |
b15 |
AC |
62 ms |
2432 KB |
b16 |
AC |
68 ms |
2432 KB |
b17 |
AC |
74 ms |
2432 KB |
b18 |
AC |
81 ms |
2432 KB |
b19 |
AC |
88 ms |
2432 KB |
b20 |
AC |
96 ms |
2432 KB |
b21 |
AC |
104 ms |
2432 KB |
b22 |
AC |
113 ms |
2560 KB |
b23 |
AC |
122 ms |
2560 KB |
b24 |
AC |
131 ms |
2560 KB |
c25 |
AC |
142 ms |
2560 KB |
c26 |
AC |
1030 ms |
2688 KB |
c27 |
TLE |
4203 ms |
4992 KB |
c28 |
TLE |
4203 ms |
7168 KB |
c29 |
TLE |
4203 ms |
7040 KB |
c30 |
TLE |
4203 ms |
8704 KB |
c31 |
TLE |
4203 ms |
12672 KB |
c32 |
TLE |
4203 ms |
16768 KB |
c33 |
TLE |
4203 ms |
24832 KB |
c34 |
TLE |
4203 ms |
30976 KB |
c35 |
TLE |
4203 ms |
35200 KB |
c36 |
TLE |
4203 ms |
35712 KB |
c37 |
TLE |
4203 ms |
35840 KB |
c38 |
TLE |
4203 ms |
35968 KB |
c39 |
TLE |
4203 ms |
36096 KB |
c40 |
TLE |
4203 ms |
36096 KB |
c41 |
TLE |
4203 ms |
36096 KB |
c42 |
TLE |
4203 ms |
36096 KB |
c43 |
TLE |
4203 ms |
36224 KB |
c44 |
TLE |
4203 ms |
36224 KB |