提出 #2394693


ソースコード 拡げる

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

提出情報

提出日時
問題 E - Everything on It
ユーザ samjia2000
言語 C++14 (GCC 5.4.1)
得点 600
コード長 1501 Byte
結果 TLE
実行時間 4204 ms
メモリ 69120 KB

ジャッジ結果

セット名 Sample Subtask1 Subtask2
得点 / 配点 0 / 0 600 / 600 0 / 300
結果
AC × 3
TLE × 1
AC × 23
AC × 27
TLE × 17
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
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