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
AC × 3
TLE × 1
AC × 23
AC × 25
TLE × 19
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