20180516模拟赛T1—

题解

这题显然是\(总方案数不可行方案数总方案数-不可行方案数\)（直接算是无规则的）。总方案数是\(n^2m^2\)，于是问题就在于不可行的方案数。

若queen落在一个点上，则横竖是十分好求的（\(n+m\)），如果能求出斜的两条就完美了。

我们发现，这种方法Q的位置会加三次，于是我们可以在最后统一减\(3nm\)。

然后比较困难的是求斜的边。

假定我们求从左上到右下线的总长度。钦定\(n\le m\)。于是就得到这样一张图：

绿色区域的点和竖线是等效的，主要是白色区域。

对于每一条斜线，我们发现第\(i\)线上的点的个数是\(i\)，于是我们就可以很容易地得出不可行方案数的总和为，\(\sum_{i=1}^n i^2\)有于有4块（反着还有两块），故要乘4。

于是就是要快速求出\(\sum_{i=1}^n i^2\)。。\(\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}\)由于我太菜了，只会归纳法，本想看一下如何现场手推（想看如何现场推的可以点这里）。

于是最后就是高精的问题了，可以不压位。

代码

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

const int width = 4;

const int mod = 1e4;

typedef long long LL;

struct HugeInt

{

	int a[50];

	int len;

	inline void clear()

	{

		memset(a, 0, sizeof(a));

		len = 0;

	}

};

HugeInt operator + (HugeInt a, HugeInt b)

{

	HugeInt c;

	c.clear();

	int maxlen = max(a.len, b.len);

	for(int i = 0; i < maxlen; ++i)

	{

		c.a[i] += a.a[i]+b.a[i];

		c.a[i+1] += c.a[i]/mod;

		c.a[i] %= mod;

	}

	c.len = maxlen;

	while(c.a[c.len])

		c.len++;

	return c;

}

HugeInt operator - (HugeInt a, HugeInt b)

{

	HugeInt c;

	c.clear();

	c.len = a.len;

	for(int i = 0; i < c.len; ++i)

	{

		c.a[i] += a.a[i]-b.a[i];

		if(c.a[i]<0)

		{

			a.a[i+1]--;

			c.a[i] += mod;

		}

	}

	while(!c.a[c.len-1] && c.len>=1)

		c.len--;

	return c;

}

HugeInt operator * (HugeInt a, HugeInt b)

{

	HugeInt c;

	c.clear();

	for(int i = 0; i < a.len; ++i)

		for(int j = 0; j < b.len; ++j)

			c.a[i+j] += a.a[i] * b.a[j];

	c.len = a.len + b.len - 1;

	for(int i = 0; i < c.len; ++i)

	{

		c.a[i+1] += c.a[i]/mod;

		c.a[i] %= mod;

	}

	while(c.a[c.len])

		c.len++;

	return c;

}

bool operator < (HugeInt a, HugeInt b)

{

	if(a.len != b.len)

		return a.len < b.len;

	else

	{

		for(int i = a.len-1; i >= 0; --i)

		{

			if(a.a[i] != b.a[i])

				return a.a[i] < b.a[i];

		}

	}

	return false;

}

HugeInt give(long long a)

{

	HugeInt re;

	re.clear();

	while(a)

	{

		re.a[re.len++] = a%mod;

		a /= mod;

	}

	return re;

}

HugeInt operator + (HugeInt a, LL b)

{

	return a + give(b);

}

HugeInt operator + (LL a, HugeInt b)

{

	return b + a;

}

HugeInt operator * (HugeInt a, LL b)

{

	return a * give(b);

}

HugeInt operator * (LL a, HugeInt b)

{

	return b * a;

}

HugeInt operator - (HugeInt a, LL b)

{

	return a - give(b);

}

HugeInt operator / (HugeInt a,LL b)

{

	HugeInt ans;

	ans.clear();

	ans=a;

	LL my=0;

	for(int i=ans.len-1; i>=0; i--)

	{

		ans.a[i]+=my;

		my=ans.a[i]%b*mod;

		ans.a[i]/=b;

	}

	while(!ans.a[ans.len-1])

		ans.len--;

	return ans;

}

void print(HugeInt a)

{

	printf("%d", a.a[a.len-1]);

	for(int i = a.len-2; i>=0; --i)

		printf("%04d", a.a[i]);

}

void solve(LL n, LL m)

{

	if(m < n)

		swap(n, m);

	HugeInt nn = give(n);

	HugeInt mm = give(m);

	print(nn*nn*mm*mm-(nn*(nn+1)*(nn*2+1)/3*2+nn*nn*2*(mm-nn-1)+(nn+mm)*nn*mm-3*nn*mm));

	puts("");

}

int main()

{

	freopen("queen.in", "r", stdin);

	freopen("queen.out", "w", stdout);

	int nmn;

	long long a, b;

	scanf("%d", &nmn);

	while(nmn--)

	{

		scanf("%lld%lld", &a, &b);

		solve(a, b);

	}

	return 0;

}

巴特西

20180516模拟赛T1——queen

题解

代码

最新文章

热门文章