OJ Board

Code: Select all

#include <iostream>

using namespace std;

int a[128], n;
long long m, c[101][101];

void perm(){
	int i, j;
	for(i=0; i<101; i++){ c[i][0]=1; c[i][i]=1;}
	for(i=1; i<101; i++) for(j=1; j<i; j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%m;
}

long long f(int k, int r){
	int i;
	long long ans;
	for(ans=1, i=0; i<r; i++) ans=(ans*(k-i))%m;
	return ans;
}

long long pow2(int p){
	long long ans=1, c=2;
	while(p>0){ if(p%2==1) ans=(ans*c)%m; p>>=1; c=(c*c)%m;}
	return ans;
}

long long doit(int i){
	int j=i+1, r, s, lim;
	long long l=0;
	lim=a[j]<a[i]-a[j]?a[j]:a[i]-a[j];
	for(r=0; r<=lim; r++){
		//l+=c(a[j], r)*f(a[i])/f(lim-r)*(1<<(a[j]-r);
		l+=(((f(a[i], a[j]+r)*pow2(a[j]-r))%m)*c[a[j]][r])%m;
	}
	return l;
}

int main(){
	int i, j;
	long long l;
	while(cin>>n>>m){
		perm();
		memset(a, 0, (n+1)*sizeof(int));
		for(i=0; i<n; i++){ cin>>j; a[j]++;}
		for(l=1, i=1; i<n; i++) l=(l*doit(i))%m;
		cout<<l<<endl;
	}
	return 0;
}