Submission #71623

---

Source Code Expand

#include<cstdio>
#include<cstdlib>
#include<utility>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

const int N_MAX=100001;

template<class T>
class Fenwick_tree_dual{
	int n;
	T a[N_MAX];

public:
	void build(int n){
		this->n=n;
		rep(i,n) a[i]=0;
	}

	void add(int i,int j,T v){
		if(i==0){
			for(;j>=0;j=(j&(j+1))-1) a[j]+=v;
			return;
		}
		add(0,j,v);
		add(0,i-1,-v);
	}

	T sum(int i){
		T s=0;
		for(;i<n;i|=i+1) s+=a[i];
		return s;
	}
};

ll modpow(ll a,ll n,ll m){
	ll r=1;
	for(ll x=a%m;n;n>>=1,x=(x*x)%m) if(n&1) r=(r*x)%m;
	return r;
}

Fenwick_tree_dual<int> F;

bool set(int d1,int d2,int T){
	int d=d1+d2;
	if(d%2!=T%2 || d>T) return false;

	int a=(T-d)/2;

	// * C(T,a)
	F.add(1,T,1);
	F.add(1,a,-1);
	F.add(1,T-a,-1);

	// * C(T,d1+a)
	F.add(1,T,1);
	F.add(1,d1+a,-1);
	F.add(1,T-d1-a,-1);

	return true;
}

int main(){
	int n,T,M; scanf("%d%d%d",&n,&T,&M);

	F.build(100001);

	bool ok=true;
	rep(_,n){
		int x,y; scanf("%d%d",&x,&y);
		ok&=set(abs(x),abs(y),T);
	}

	if(!ok) return puts("0"),0;

	ll ans=1;
	for(int a=100000;a>=2;a--){
		int tmp=a;

		// a を素因数分解
		int sz=0;
		pair<int,int> pf[10];
		for(int p=2;p*p<=a;p++) if(a%p==0) {
			int e=0;
			do{ a/=p; e++; }while(a%p==0);
			pf[sz++]=make_pair(p,e);
		}
		if(a>1) pf[sz++]=make_pair(a,1);

		a=tmp;

		if(sz==1 && pf[0].second==1){
			ans=ans*modpow(a,F.sum(a),M)%M;
		}
		else{
			int num=F.sum(a);
			rep(i,sz){
				int p=pf[i].first,e=pf[i].second;
				F.add(p,p,e*num);
			}
		}
	}
	printf("%lld\n",ans);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:68:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:74:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result