【CZY选讲·Hja的棋盘】

题目描述

Hja特别有钱，他买了一个×的棋盘，然后Yjq到这个棋盘来搞事。一开始所有格子都是白的，Yjq进行次行操作次列操作，所谓一次操作，是将对应的行列上的所有格子颜色取反。现在Yjq希望搞事之后棋盘上有个黑色格子，问Yjq 有多少种搞事的方法。

数据范围

1≤,,,≤100000,0≤≤×M

题解：
①先不考虑冗余操作(冗余操作定义:对同一个地方进行2次及以上操作)

②设对行进行x操作,对列进行y次操作,那么得到等式：

mx+ny-2xy=S ----->枚举x,则y=(S-mx)/(n-2x)

③那么行上剩余(R-x)次操作，列上剩余(C-y)次操作。

④为了使这些不影响答案,那么必须偶数地添加到任意位置，可以添加的次数为：

Times=(R-x)/2 Times=(C-y)/2

⑤剩下的就是组合数问题了,问题转化为：将m个小球放入n个盒子里，盒子可以多放,可以不放。

⑥此类组合数问题解法：先讲小球扩大为(n+m)个,那么问题转化为每个盒子至少放一个小球的方案数——转化为将(n+m)个数分成非空的n组的问题(插隔板问题)。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#ifdef unix

#define LL "%lld"

#else

#define LL "%I64d"

#endif

const int maxn=100010;

const int mo=1000000007;

int n,m,r,c,ans,v0[maxn],v1[maxn],v2[maxn],v3[maxn],v4[maxn];

long long s;

int multi(long long a,int b)

{

	a*=b;

	if (a>=mo) a%=mo;

	return (int)a;

}

void inc(int &a,int b)

{

	a+=b;

	if (a>=mo) a-=mo;

}

int mul(int a,int b)

{

	int ans=1;

	while (b)

	{

		if (b&1) ans=multi(ans,a);

		a=multi(a,a);

		b>>=1;

	}

	return ans;

}

int main()

{

	//freopen("c.in","r",stdin);

	//freopen("c.out","w",stdout);

	scanf("%d%d%d%d" LL,&n,&m,&r,&c,&s);

	v1[0]=1;

	for (int a=1;a<=100000;a++)

		v0[a]=mul(a,mo-2);

	int tmp=1;

	for (int a=0;a<=(r>>1);a++)

	{

		v1[a]=tmp;

		tmp=multi(tmp,multi(a+n,v0[a+1]));

	}

	tmp=1;

	for (int a=0;a<=(c>>1);a++)

	{

		v2[a]=tmp;

		tmp=multi(tmp,multi(a+m,v0[a+1]));

	}

	tmp=1;

	for (int a=0;a<=n;a++)

	{

		v3[a]=tmp;

		tmp=multi(tmp,multi(n-a,v0[a+1]));

	}

	tmp=1;

	for (int a=0;a<=m;a++)

	{

		v4[a]=tmp;

		tmp=multi(tmp,multi(m-a,v0[a+1]));

	}

	for (int a=r&1;a<=min(n,r);a+=2)

		if (a*2!=n)

		{

			if (((s-(long long)a*m))%(n-a*2)) continue;

			int b=(int)((s-(long long)a*m)/(n-a*2));

			if (b>c || b<0 || ((c-b)&1)) continue;

			int nowans=v3[a];

			nowans=multi(nowans,v1[(r-a)>>1]);

			nowans=multi(nowans,v4[b]);

			nowans=multi(nowans,v2[(c-b)>>1]);

			inc(ans,nowans);

		}

		else

		{

			if ((long long)a*m!=s) continue;

			int nowans=v3[a];

			nowans=multi(nowans,v1[(r-a)>>1]);

			int cnt=0;

			for (int b=(c&1);b<=min(r,c);b+=2)

				inc(cnt,multi(v4[b],v2[(c-b)>>1]));

			inc(ans,multi(ans,cnt));

		}

	printf("%d\n",ans);

	return 0;

}//czy020202(代码有点丑)

别害怕我就站在你身边，心在一起爱会让我们勇敢。

别害怕我就站在你身边，看黑夜无法吞没黎明的天。——————汪峰《直到永远》

yjq

【CZY选讲·Hja的棋盘】