当前位置: 代码迷 >> 综合 >> Gym 101194H - The 2016 ACM-ICPC Asia China-Final (Shanghai) Contest - H. Great Cells - (组合计数,思维)
  详细解决方案

Gym 101194H - The 2016 ACM-ICPC Asia China-Final (Shanghai) Contest - H. Great Cells - (组合计数,思维)

热度:29   发布时间:2024-01-12 14:54:53.0

题解来自

https://blog.csdn.net/infinity_edge/article/details/79090391   

https://blog.csdn.net/martayang/article/details/54862753

题目链接

https://vjudge.net/problem/UVALive-7904

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5926

题意:有一个 N行 M 列的矩阵,每一个格子是 [1,k]之间的一个整数。
定义一个格子是吼的,当且仅当该格子的值严格大于与其同行同列的所有格子种的值。定义 Ag为恰好有 g个吼的格子的互不相同的矩阵数目,求:

                                                                         \sum_{g = 0}^{NM} (g + 1) A_g \mod \ 10^9 + 7

解析
先把式子拆一下:

                                                                                  \sum_{g = 0}^{NM} g A_g + \sum_{g = 0}^{NM} A_g
后者为所有矩阵的数目。

                                                                                   \sum_{g = 0}^{NM} g A_g + k^{NM}
前者可以看成所有的矩阵的吼的格子的数目之和。
如果一个格子是吼的,那么该行该列所有的数都要严格小于该格子中的数。剩余 N?1 行 M?1 列的格子可以随便填,那么我们枚举这个数就可以了。

最后的答案为:

                                                            NM \sum_{i = 0}^k(i - 1)^{N - 1+ M - 1}k^{(N - 1)(M - 1)}+ k^{NM}

另一个思路:

这题乍一看需要用组合数学 容斥原理计算A-g,但是这样做比较麻烦复杂。但其实这题是(g+1)的套路。。。简便做法是观察整体,把问题转化成每个位置是great格子对最终答案的贡献和,这样就绕开了A-g的计算。

首先,考虑整体的填法:K^(M×N)——这个是容易计算的,那么我们先企图用整体填法数化简待求式!我们发现将待求式展开,后面的ΣA-g的和便是整体的填法数。(一般都需要先拿整体化简一把!)

于是现在只需着手计算Σg*A-g,这个就用贡献和的思想转化,因为有g个great格的填法数乘了个g相当于摊到了这g个位置上,也就是说每个great格独立了,也即每一个格是great格对Σg*A-g贡献=使这个格是great的所有填法总数:

Contrib=Σ(i=1到i=K-1)i^(N-1+M-1)×K^[(N-1)×(M-1)]       (转化为贡献和,有点智力题的感觉orz..)

这里注意一点:以上公式没有考虑n=m=1的情况,因为这时填1也算是great格(而以上公式从填2开始考虑的)

从而最后:ans=Contrib×N×M+K^(M×N)

代码

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
typedef long long ll;
inline ll fpow(ll n,ll k)
{ll res=1;while(k>0){if(k&1)res=res*n%mod;n=n*n%mod;k>>=1;}return res;
}
inline ll solve(ll k,ll p)
{ll res=0;for(ll i=1;i<=k-1;i++){res+=fpow(i,p);res%=mod;}return res;
}
int N,M,K,T,cas;
int main()
{scanf("%d",&T);while(T--){scanf("%d%d%d",&N,&M,&K);cas++;ll ans=0;ans=solve(K,N+M-2);ans*=fpow(K,N*M-N-M+1);ans%=mod;ans*=N*M;ans%=mod;ans+=fpow(K,N*M);ans%=mod;printf("Case #%d: %lld\n",cas,ans);}return 0;
}

 

 

  相关解决方案