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 |
|
|
|
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 |