topcoder SRM 567 Div2 1000

1000:MountainsEasy

题意:

给你一个山的横切图。。。已知这个图中有n座山,然后问你所有山的排列种数。。。

分析:

emmm,你们自己去看。。。

代码:

 

int fac[ArSize], inv[ArSize];
class MountainsEasy
{
  private:
	int H, W;
	void init()
	{
		int i;
		for (fac[0] = i = 1; i = 0; i--) inv[i] = (LL)(i + 1) * inv[i + 1] % mod;
	}
	int fast_pow(int bs, int ex)
	{
		int res = 1;
		for (; ex > 0; ex >>= 1, bs = (LL)bs * bs % mod)
			if (ex & 1) res = (LL)res * bs % mod;
		return res;
	}
	int C(int n, int r){return (LL)fac[n] * inv[r] % mod * inv[n - r] % mod;}

  public:
	int countPlacements(vector picture, int N);
};
int MountainsEasy::countPlacements(vector picture, int N)
{
	H = picture.size(), W = picture[0].length();
	int x, y, N0 = N;
	for (x = 0; x < W && picture[H - 1][x] == '.'; x++);
	if (x == W) return 0;
	else
	{
		int tot = 0;
		for (; x < W; x++)
		{
			for (y = 0; y < H && picture[y][x] == '.'; y++);
			if (y == H) continue;
			if (!y ||
				(!x && (x + 1 == W || picture[y - 1][x + 1] == '.')) ||
				(x + 1 == W && (!x || picture[y - 1][x - 1] == '.')) ||
				(x && x + 1 < W && picture[y - 1][x - 1] == '.' && picture[y - 1][x + 1] == '.'))
				--N;
			tot += H - y;
		}
		if (N < 0) return 0;
		init();
		int peaks = N0 - N;
		LL res = 0;
		for (int i = 0; i <= peaks; i++)
			if (i & 1) res = (res + mod - (LL)C(peaks, i) * fast_pow(tot - i, N0) % mod) % mod;
			else res = (res + (LL)C(peaks, i) * fast_pow(tot - i, N0) % mod) % mod;
		return (int)res;
	}
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注