Submission #2559798


Source Code Expand

#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
lint mo;
lint dp[3010][3010];
lint co[3010][3010];
lint zyo[9001001];
lint zy2[3010];
int main()
{
	int n;
	cin>>n>>mo;
	rep(i,3005){
		co[i][0]=co[i][i]=1;
		REP(j,1,i) co[i][j]=(co[i-1][j]+co[i-1][j-1])%mo;
	}
	memset(dp,0,sizeof(dp));dp[0][0]=1;
	rep(i,3005) rep(j,3005){
		if(i>0 && j>0) dp[i][j]+=dp[i-1][j-1];
		if(i>0) dp[i][j]+=dp[i-1][j]*(j+1);
		dp[i][j]%=mo;
	}
	zyo[0]=1;rep(i,9001000) zyo[i+1]=(zyo[i]*2)%mo;
	zy2[0]=2;rep(i,3005) zy2[i+1]=(zy2[i]*zy2[i])%mo;
	lint out=0;
	rep(i,n+1) rep(j,i+1){
		lint t=(dp[i][j]*co[n][i])%mo;
		t*=zyo[j*(n-i)];t%=mo;
		t*=zy2[n-i];
		//cout<<i<<' '<<j<<' '<<t<<endl;
		if(i%2==0) out+=t;else out-=t;out%=mo;
	}
	out%=mo;out+=mo;out%=mo;cout<<out<<endl;
}

Submission Info

Submission Time
Task E - Everything on It
User sky58
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1450 Byte
Status AC
Exec Time 627 ms
Memory 212224 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 600 / 600 300 / 300
Status
AC × 4
AC × 23
AC × 44
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 319 ms 212096 KB
a02 AC 319 ms 212096 KB
a03 AC 319 ms 212096 KB
a04 AC 627 ms 212096 KB
b05 AC 319 ms 212096 KB
b06 AC 317 ms 212096 KB
b07 AC 318 ms 212096 KB
b08 AC 319 ms 212096 KB
b09 AC 319 ms 212096 KB
b10 AC 318 ms 212096 KB
b11 AC 317 ms 212096 KB
b12 AC 317 ms 212096 KB
b13 AC 317 ms 212096 KB
b14 AC 317 ms 212096 KB
b15 AC 317 ms 212096 KB
b16 AC 319 ms 212096 KB
b17 AC 318 ms 212096 KB
b18 AC 319 ms 212096 KB
b19 AC 318 ms 212096 KB
b20 AC 318 ms 212096 KB
b21 AC 319 ms 212224 KB
b22 AC 318 ms 212224 KB
b23 AC 319 ms 212096 KB
b24 AC 317 ms 212096 KB
c25 AC 324 ms 212096 KB
c26 AC 319 ms 212096 KB
c27 AC 318 ms 212096 KB
c28 AC 318 ms 212096 KB
c29 AC 321 ms 212096 KB
c30 AC 326 ms 212096 KB
c31 AC 334 ms 212096 KB
c32 AC 355 ms 212096 KB
c33 AC 402 ms 212096 KB
c34 AC 486 ms 212096 KB
c35 AC 570 ms 212096 KB
c36 AC 551 ms 212096 KB
c37 AC 575 ms 212096 KB
c38 AC 588 ms 212096 KB
c39 AC 593 ms 212096 KB
c40 AC 551 ms 212096 KB
c41 AC 591 ms 212096 KB
c42 AC 567 ms 212096 KB
c43 AC 552 ms 212096 KB
c44 AC 552 ms 212096 KB