2018深圳

深圳"/>

2018深圳

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;
}

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