牛客练习赛76 C-CG的通关秘籍 组合+数学推导

传送门：https://ac.nowcoder.com/acm/contest/10845/C

题意

有n个位置，[1..m]中的数无穷多个，构造所有可能的序列。 每个序列的贡献取决于，若$a_i>a_{i-1}$，贡献+1，若$a_i<a_{i-1}$，贡献-1.相等没有贡献。

问：构造完所有可能的序列之后的贡献和，请$mod\;1e9+7$

思路

因为贡献只取决于第i位和第i-1位，然后其他位置随便取，则为该贡献$*m^{n-2}.$

然后从第二个位置开始枚举，假设枚举到了第i位。

第i位上可以取[1,m]之间的所有数，假设取一个j，则对于前一位来说有j-1个比它小,m-j个比它大。

所以贡献为$(j-1)+2*(m-j)。$

所以该位置上的总贡献为$[\sum_{j=1}^m(j-1)+(m-j)]*m^{n-2}$

最后结合一下所有位置(注意是从第二位开始取)，贡献和为$$\sum_{i=2}^n[\sum_{j=1}^m(j-1)+2*(m-j)]*m^{n-2}$$

整理一下得： $$\frac{3m^2-3m}{2}*m^{n-2}*(n-1)$$

Code（702MS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

ll quick_pow(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}

void solve() {
    int _; scanf("%d",&_);
    ll inv2 = quick_pow(2, mod - 2);
    while(_--) {
        ll n, m; scanf("%lld%lld",&n,&m);
        if(m == 1) {
            printf("0\n");
            continue;
        }
        ll ans = m * (3 * m - 3) % mod * inv2 % mod;
        ans = ans * quick_pow(m, n - 2) % mod * (n - 1) % mod;
        printf("%lld\n",(ans + mod) % mod);
    }
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/01/15/nowcoder-practice76-c/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！