Submission #2394693


Source Code Expand

Copy
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 3005;

int n,mo;

LL quickmi(LL x,LL tim){
	LL ret=1;
	for(;tim;tim/=2,x=x*x%mo)
	if (tim&1)ret=ret*x%mo;
	return ret;
}

LL add(LL x,LL y){return x+y>=mo?x+y-mo:x+y;}
LL dec(LL x,LL y){return x<y?x-y+mo:x-y;}

LL js[N],inv[N];

LL calc(int n,int m){return js[n]*inv[m]%mo*inv[n-m]%mo;}

LL f[N][N];

int main(){
	n=get();mo=get();
	js[0]=js[1]=1;
	fo(i,2,n)js[i]=js[i-1]*i%mo;
	inv[0]=inv[1]=1;
	fo(i,2,n)inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo;
	fo(i,2,n)inv[i]=inv[i]*inv[i-1]%mo;
	LL ans=0;
	f[0][0]=1;
	fo(i,1,n)
		fo(j,1,i)f[i][j]=add(f[i-1][j-1],f[i-1][j]*j%mo);
	fo(A,0,n){
		LL v=2;
		fo(B,0,n){
			LL tmp=js[n]*inv[A]%mo*inv[B]%mo*inv[n-A-B]%mo;
			tmp=tmp*v%mo;
			LL sum=0;
			fo(i,0,A)sum=add(sum,quickmi(quickmi(2,B),i)*f[A][i]%mo);
			tmp=tmp*sum%mo;
			v=v*v%mo;
			if(B&1)ans=dec(ans,tmp);else ans=add(ans,tmp);
		}
	}
	if (n&1)ans=dec(0,ans);
	cout<<ans<<endl;
	return 0;
}

Submission Info

Submission Time
Task E - Everything on It
User samjia2000
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1501 Byte
Status TLE
Exec Time 4204 ms
Memory 69120 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 × 27
TLE × 17
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 AC 13 ms 512 KB
a04 TLE 4204 ms 69120 KB
b05 AC 1 ms 256 KB
b06 AC 1 ms 256 KB
b07 AC 1 ms 256 KB
b08 AC 1 ms 256 KB
b09 AC 1 ms 256 KB
b10 AC 1 ms 256 KB
b11 AC 2 ms 384 KB
b12 AC 2 ms 384 KB
b13 AC 4 ms 384 KB
b14 AC 7 ms 384 KB
b15 AC 8 ms 384 KB
b16 AC 8 ms 384 KB
b17 AC 9 ms 384 KB
b18 AC 9 ms 384 KB
b19 AC 10 ms 384 KB
b20 AC 11 ms 384 KB
b21 AC 11 ms 512 KB
b22 AC 12 ms 512 KB
b23 AC 13 ms 512 KB
b24 AC 13 ms 512 KB
c25 AC 14 ms 512 KB
c26 AC 68 ms 640 KB
c27 AC 335 ms 2688 KB
c28 AC 1645 ms 4736 KB
c29 TLE 4203 ms 8832 KB
c30 TLE 4203 ms 12928 KB
c31 TLE 4203 ms 19072 KB
c32 TLE 4203 ms 29312 KB
c33 TLE 4203 ms 43648 KB
c34 TLE 4203 ms 60032 KB
c35 TLE 4203 ms 68224 KB
c36 TLE 4203 ms 68224 KB
c37 TLE 4203 ms 68480 KB
c38 TLE 4203 ms 68736 KB
c39 TLE 4204 ms 68864 KB
c40 TLE 4203 ms 68992 KB
c41 TLE 4204 ms 68992 KB
c42 TLE 4204 ms 68992 KB
c43 TLE 4203 ms 68992 KB
c44 TLE 4203 ms 69120 KB