2018 ccpc final G. Pastoral Life in Stardew Valley(组合数学)

组合数学)"/>

2018 ccpc final G. Pastoral Life in Stardew Valley(组合数学)

LINK

题意

给定 n ∗ m n*m n∗m的网格,从中选出两个矩形,求大矩形完全包含小矩形的方案数

(小矩形不能碰到大矩形!!!)

设选出来的大矩形是 r ∗ c r*c r∗c的,那么外围一圈都不能放置小矩形

也就是小矩形可以在内部的 ( r − 2 ) ∗ ( c − 2 ) (r-2)*(c-2) (r−2)∗(c−2)范围内任选

可以先固定 y y y轴上的两个端点,再固定 x x x轴上的两个端点

这部分方案是 C r − 1 2 ∗ C c − 1 2 C_{r-1}^2*C_{c-1}^2 Cr−12​∗Cc−12​

于是我们枚举大矩形的宽和高得到总方案数是

∑ r = 3 n ∑ c = 3 m ( n − r + 1 ) ∗ ( m − c + 1 ) ∗ C r − 1 2 ∗ C c − 1 2 \sum\limits_{r=3}^n\sum\limits_{c=3}^m(n-r+1)*(m-c+1)*C_{r-1}^2*C_{c-1}^{2} r=3∑n​c=3∑m​(n−r+1)∗(m−c+1)∗Cr−12​∗Cc−12​

其中 ( n − r + 1 ) ∗ ( m − c + 1 ) (n-r+1)*(m-c+1) (n−r+1)∗(m−c+1)是大矩形的方案数,表示右下角的点必须落在这个范围内

令 f ( x ) = ∑ i = 3 x ( x − i + 1 ) ∗ C i − 1 2 f(x)=\sum\limits_{i=3}^x(x-i+1)*C_{i-1}^2 f(x)=i=3∑x​(x−i+1)∗Ci−12​

那么答案即为 f ( n ) ∗ f ( m ) f(n)*f(m) f(n)∗f(m)

考虑如何快速计算 f ( x ) f(x) f(x)

f ( x ) = x ∗ ∑ i = 3 x C i − 1 2 + ∑ i = 3 x ( − i + 1 ) ∗ C i − 1 2 f(x)=x*\sum\limits_{i=3}^xC_{i-1}^2+\sum\limits_{i=3}^x(-i+1)*C_{i-1}^2 f(x)=x∗i=3∑x​Ci−12​+i=3∑x​(−i+1)∗Ci−12​

考虑到前后两项可以暴力预处理,所以单次询问可以 O ( 1 ) O(1) O(1)

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5+10;
const int mod = 1e9+7;
int quick(int x,int n)
{int ans = 1;for( ; n ; n>>=1,x=x*x%mod )if( n&1 )   ans = ans*x%mod;return ans;
}
int fac[maxn],pre1[maxn],pre2[maxn],casenum;
int C(int n,int m)
{if( m>n )   return 0ll;return fac[n]*quick( fac[m]*fac[n-m]%mod, mod-2 )%mod;
}
int F(int x)
{int ans = x*pre1[x]%mod+pre2[x];return ( ans%mod+mod )%mod;
}
signed main()
{fac[0] = 1;for(int i=1;i<=200000;i++)  fac[i] = fac[i-1]*i%mod;for(int i=3;i<=200000;i++)  pre1[i] = ( pre1[i-1]+C(i-1,2) )%mod;for(int i=3;i<=200000;i++)  pre2[i] = ( pre2[i-1]+(-i+1)*C(i-1,2)%mod )%mod;int t; cin >> t;while( t-- ){int n,m; cin >> n >> m;printf("Case %lld: %lld\n",++casenum,F(n)*F(m)%mod );}
}