SRM 573

朝するめは参加するとレーティングが必ず大暴落する。

250：チームコンペティション
読んでない

450：スキー
読んでない

850：オオカミ
https://speakerdeck.com/tozangezan/srm573-div1hard-div2hard-jie-shuo
45度回転させてcombinationする。

public class WolfPack{
	public int calc(int[]x,int[]y,int m){
		int p=0;
		int n=x.length;
		long mod=1000000007;
		for(int i=0;i<n;i++)if((x[i]+y[i])%2!=0)p++;
		if(p!=0&&p!=n)return 0;
		if(p==n)for(int i=0;i<n;i++)x[i]--;
		int X[]=new int[n];
		int Y[]=new int[n];
		for(int i=0;i<n;i++)X[i]=(x[i]+y[i])/2;
		for(int i=0;i<n;i++)Y[i]=(x[i]-y[i])/2;
		int minX=99999999;int minY=99999999;
		for(int i=0;i<n;i++){
			minX=Math.min(minX,X[i]);
			minY=Math.min(minY,Y[i]);
		}
		int W=0;
		int H=0;
		for(int i=0;i<n;i++){
			X[i]-=minX;
			W=Math.max(W,X[i]);
			if(X[i]>m)return 0;
		}
		for(int i=0;i<n;i++){
			Y[i]-=minY;
			H=Math.max(H,Y[i]);
			if(Y[i]>m)return 0;
		}
		long []C=new long[m+1];
		long []left=new long[m+2];
		long []right=new long[m+2];
		left[0]=1;
		for(int i=1;i<m+2;i++){
			left[i]=(left[i-1]*i)%mod;
		}
		right[m+1]=m+1;
		for(int i=m;i>=0;i--){
			right[i]=(right[i+1]*i)%mod;
		}
		long s=left[m+1];
		long t=1;
		int c=(int)(mod-2);
		while(c>0){
			if(c%2==1)t=t*s%mod;
			c/=2;
			s=s*s%mod;
		}
		long at=1;
		long val=1;
		for(int i=0;i<=m;i++){
			C[i]=at;
			if(i==m)break;
			at=at*(m-i)%mod;
			at=at*left[i]%mod*right[i+2]%mod*t%mod;
		}
		long A=0;
		long B=0;
		for(int i=0;i<=m-W;i++){
			long V=1;
			for(int j=0;j<n;j++){
				V=V*C[i+X[j]]%mod;
			}
			A=(A+V)%mod;
		}
		for(int i=0;i<=m-H;i++){
			long V=1;
			for(int j=0;j<n;j++){
				V=V*C[i+Y[j]]%mod;
			}
			B=(B+V)%mod;
		}
		return (int)(A*B%mod);
	}
}

challenge phase
眺めていた
system test
通るもなにもない
result: なし