[C++知识库]2018EcFinal-Pastoral Life in Stardew Valley-(思维+组合数)

G

题意：
就是给你一个n*m的田地，这个田地的所有子矩阵，对于每个矩阵可以放多少个稻草人，稻草人放置的条件是必须周围都是草，但是占地大小随意。

思考：
当时我就是想只扫一维n，然后对于列m就是直接一个等差数列之类的，但是怎么推都推不出来。害，实际上不要考虑那么复杂，既然说稻草人周围必须有草，那么从n行里选4行，其中两行是草的边界，其中两行是稻草人的大小，然后同理m也是。但是还有一个就是从n行选3个，也就是只有中间一行作为稻草人。转化成这样确实太简单了，思维要多转化一下，多多思考。

int T,n,m,k;
int va[N];
int fact[N],infact[N];

int ksm(int a,int b)
{
	int sum = 1;
	while(b)
	{
		if(b&1) sum = sum*a%mod;
		a = a*a%mod;
		b >>= 1;
	}
	return sum;	
}

void init(int x)
{
	fact[0] = infact[0] = 1;
	for(int i=1;i<=x;i++) fact[i] = fact[i-1]*i%mod;
	infact[x] = ksm(fact[x],mod-2)%mod;
	for(int i=x-1;i>=1;i--) infact[i] = infact[i+1]*(i+1)%mod;
}

int C(int a,int b)
{
	if(a<b) return 0;
	return fact[a]*infact[b]%mod*infact[a-b]%mod;
}

signed main()
{
	IOS;
	init(1e5);
	cin>>T;
	for(int cs=1;cs<=T;cs++)
	{
		cin>>n>>m;
		int suml = (C(n,4)+C(n,3))%mod;
		int sumr = (C(m,4)+C(m,3))%mod;
		int ans = suml*sumr%mod;
		ans = (ans%mod+mod)%mod;
		cout<<"Case "<<cs<<": "<<ans<<"\n";	
	}
	return 0;
}

总结：
多多思考，换一种思考方式。