Problem A
Chess Queen
Input: Standard Input

Output: Standard Output

王后互相攻击的前提是在一行，一列，或一对角线。:

在 (NxM) 的棋盘上 2 王后互相攻击，求方案数.

Input

输入数据不超过 5000 行 ，每行为M and N (0< M, N£10⁶) ,数据以0 0结尾.

Output

每行一个整数表示方案数，保证它在u64范围内.

Sample Input                              Output for Sample Input

Problemsetter: Shahriar Manzoor

Special Thanks to: Mohammad Mahmudur Rahman

首先，一个矩形的长宽若为m,n(m>=n)

那么它一个方向的对角线应为1..(n-1)各2条,n有(m-n+1)条

知道这个的化，本题就转化为，在一列一行或一对角线任取2点，有几种取法。

#include<cstdio>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
#define MAXN (1000000+10)
unsigned long long n,m;
int main()
{
	while (cin>>n>>m&&n&&m)
	{
		if (n>m) swap(n,m);
		cout<<n*m*(n+m-2)+2*n*(n-1)*(3*m-n-1)/3<<endl;
	}
	return 0;
}

0
9
999999999
1000000000
-1

0
34
626
6875

正宗矩阵幂练手题。

做了这题就差不多理解矩阵乘法了。

补充：递归一般能用矩阵乘法，如f[i]=g(f[i-1],f[i-2])...

    但是规划不行，如f[i]=max(....)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<functional>
using namespace std;
#define MAXN (1000000000)
#define F (10000)
struct M
{
	int a[3][3];
	M(int i){a[1][1]=a[1][2]=a[2][1]=1;a[2][2]=0;	}
	M(){memset(a,0,sizeof(a));	}
	friend M operator*(M a,M b)
	{
		M c;
		for (int i=1;i<=2;i++)
			for (int j=1;j<=2;j++)
				for (int k=1;k<=2;k++)
				{
					c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%F;
				}
		return c;
	}
	friend M pow(M a,int b)
	{
		if (b==1)
		{
			M c(1);
			return c;
		}
		else
		{
			M c=pow(a,b/2);
			c=c*c;
			if (b%2) return c*a;
			return c;
		}
	}
};
int n;
int main()
{
	while (cin>>n&&n!=-1)
	{
		if (n==0) printf("0n");
		else
		{
			M a=pow(M(1),n);
			printf("%dn",a.a[1][2]);
		}
	}
}

3 4 4
aabb
baab
baab

2

4 5 1
ababa
ccaca
ccacb
cbabc

1

这题是状态压缩问题。

用s[i][j]=∑a[1][j]+a[2][j]+..+a[i][j]

那么我们只需要枚举3个量

行的上下，还有列的

显然r列的关系可以由r-1的关系推出。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXN (400+10)
#define MAXM (400+10)
int n,m,k;
char a[MAXN][MAXM];
int s[MAXN][MAXM];  //表示s[i][j]=a[1][j]+a[2][j]+..a[i][j]
int c[1<<8];
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);


	memset(s,0,sizeof(s));
	scanf("%d%d%dn",&n,&m,&k);
	for (int i=1;i<=n;i++)
	{
		gets(a[i]+1);
		for (int j=1;j<=m;j++)
		{
			s[i][j]=s[i-1][j]+(a[i][j]=='a');
		}
	}
	long long ans=0;
	/*
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
			cout<<s[i][j]<<' ';
		cout<<endl;
	}
	*/
	;
	for (int i=1;i<n;i++)
	{
		for (int j=i+1;j<=n;j++)
		{
			int l=1,tot=0;
			memset(c,0,sizeof(c));
			for (int r=1;r<=m;r++)
			{
				tot+=s[j][r]-s[i-1][r];
				while (tot>k)
				{
					tot-=s[j][l]-s[i-1][l];
					c[a[i][l]]-=(a[i][l]==a[j][l]);
					l++;
				}
				if (l<r&&a[i][r]==a[j][r]) ans+=c[a[i][r]];
				if (a[i][r]==a[j][r]) c[a[i][r]]++;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}