TopCoder SRM 781 : Div2 Hard PolygonalRegions

久々にDiv2 Hardが固有の問題。
https://community.topcoder.com/stat?c=problem_statement&pm=16034&rd=17857

問題

凸N多角形があるとする。
各対角線は3本以上が1点で交わることはない。

頂点を時計回りに1～Nまで番号を付けたとする。
この時、各頂点iは確率i/Vで良いと判定される。

良いと判定された2頂点間に対角線を引くとき、元の図形はいくつの領域に分割されるか、期待値を求めよ。

解法

頂点(u,v)間に対角線を引いたとすると、まずその時点で領域が1個増える。
その時、1≦x＜u＜ｙ＜vであるような(x,y)間にもすでに対角線があるなら、追加で領域が増える。
なのでu,v,x,yを総当たりすればO(N^4)で数え上げることができる。
u,vを総当たりして、x,yのループは累積和を取るようにすればO(N^3)にもなるが、Nの上限が小さいので今回はそこまでいらない。

const ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

class PolygonalRegions {
	public:
	int expectedRegions(int N) {
		ll ret=1;
		ll rev=modpow(N);
		int i,j,x,y;
		for(i=1;i<=N;i++) {
			for(j=1;j<i-1;j++) {
				if(i==N&&j==1) continue;
				ll prob=i*rev%mo*j%mo*rev%mo;
				ret+=prob;
				for(x=1;x<j;x++) for(y=j+1;y<i;y++) {
					ll prob2=x*rev%mo*y%mo*rev%mo;
					ret+=prob*prob2%mo;
				}
			}
		}
		return ret%mo;
		
	}
}

まとめ

確率をテーブルで明に与えるとか、N=500程度にするとかしてもいいと思うんだけどな。