题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5926
文章图片
文章图片
题意：在一个n*m的矩阵内填整数，数字在[1...K]范围内。矩阵中某格的数为great number当且仅当与它同行同列的数字都严格比它小。即Ag为矩阵中恰有g个great number的填数方案数，求
文章图片
(n,m,k<=200n,m,k<=200)
我感觉网上的题解说的比较粗略，根本就很难看懂，虽然看似简单，但是讲的不够详细。
例：
【其他（思维|2016年ACM/ICPC Asia China-Final (Shanghai) Contest H题（思维））】
文章图片
实际上，除去k^(n*m)的任意填法（即g+1那个1）之后只要有一个great number出现，我们就统计一次答案。因为刚好是g*Ag。
对于每个格子，是great number ，假设这个格子填i，则其所在行、列的共n+m-2个格子只有(i-1)种选择，其他的(n-1)*(m-1)个格子就可以随便填了（对于这些格子，每个格子有k种选择）（因为每个出现g个great number的矩阵会被统计g次）。
所以枚举i从2到k如上式那样统计，最后再加上k^(n*m)取模，就是答案。这样就很容易理解了。
代码：
#include
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const ll mo=1e9+7;
ll n,m,k;
ll power(ll a,ll n) //a的n次方mod
{
ll ans=1;
a=a%mo;
while (n)
{
if(n&1) ans=(ans*a)%mo;
n>>=1;
a=(a*a)%mo;
}
return ans;
}
int main()
{
int T,cas=1;
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%lld",&n,&m,&k);
ll ans=0;
for(ll i=2;
i<=k;
i++)
{
ans=(ans+n*m%mo*power(i-1,n+m-2)%mo*power(k,(n-1)*(m-1))%mo)%mo;
}
ans=(ans+power(k,n*m))%mo;
printf("Case #%d: %lld\n",cas++,ans);
//if(flag) puts("Yes");
else puts("No");
}
return 0;
}
推荐阅读
- ACM|HDU 5322 Hope (CDQ分治+NTT)
- 牛客算法周周练15——A、B
- Codeforces Round #609 (Div. 2)——C. Long Beautiful Integer（思维）
- FZU - 2107题解
- ACM OJ 2036 多边形面积计算
- #|【牛客】牛客练习赛67-E-牛妹游历城市——位运算优化
- ACM|回文树（自动机）（练习和总结）
- acm|扩展欧几里德算法(附证明)
- ACM|[dsu] codeforces 375D. Tree and Queries
- ACM|codeforces 732-D. Exams （二分）