本文共 1401 字，大约阅读时间需要 4 分钟。
给每个格子填 [ 1 , k ] [1,k] [1,k]的数字,如果一个格子在这一行这一列是严格最大,说这个格子是好各自
求 ∑ i = 0 n m ( g i + 1 ) ∗ A i \sum\limits_{i=0}^{nm}(g_i+1)*A_i i=0∑nm(gi+1)∗Ai
其中 A i A_i Ai代表有 g i g_i gi个好格子的方案数
拆开式子得到 ∑ i = 0 n m g i ∗ A i + ∑ i = 0 n m A i \sum\limits_{i=0}^{nm}g_i*A_i+\sum\limits_{i=0}^{nm}A_i i=0∑nmgi∗Ai+i=0∑nmAi
后一项明显是所有的方案数,为 k n m k^{nm} knm
前一项不好解,单独考虑每个格子的贡献
∑ i = 0 n m g i ∗ A i \sum\limits_{i=0}^{nm}g_i*A_i i=0∑nmgi∗Ai这个式子可以看成,每当一个格子成为好格子,答案加一
所以我们单独考虑每个好格子的方案数累加即可
答案是
n m ∗ ∑ v a l = 2 k ( v a l − 1 ) n + m − 2 ∗ k n ∗ m − n − m + 1 nm*\sum\limits_{val=2}^k(val-1)^{n+m-2}*k^{n*m-n-m+1} nm∗val=2∑k(val−1)n+m−2∗kn∗m−n−m+1
首先每个格子都可能成为好格子,方案是 n m nm nm
选了这个格子后,我们枚举这个格子的值 v a l val val
那么这一列这一行需要比 v a l val val小,方案是 ( v a l − 1 ) n + m − 2 (val-1)^{n+m-2} (val−1)n+m−2
然后其余的格子不受影响,方案数是 k n ∗ m − n − m + 1 k^{n*m-n-m+1} kn∗m−n−m+1
做完了
总结
做题的时候老是想着枚举几个好格子,但其实明显不可做
转化思维从式子的意义上考虑就好些很多了
#includeusing namespace std;#define int long longconst int mod = 1e9+7;int t,n,m,k,casenum;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;}signed main(){ cin >> t; while( t-- ) { cin >> n >> m >> k; int ans1 = quick(k,n*m), ans2 = 0; for(int i=2;i<=k;i++) ans2 = ( ans2+quick(i-1,n+m-2)*quick(k,n*m-n-m+1)%mod )%mod; int ans = (( ans1+ans2*n%mod*m%mod )%mod+mod)%mod; cout << "Case #" << ++casenum << ": "; cout << ans << endl; }}
转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116045061 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
