牛客小白月赛B-k-size字符串——逆元求组合数

传送门：https://ac.nowcoder.com/acm/contest/5600/B

题意

思路

不要看它是以字符串的形式呈现，其实本质上是组合数学（自己细品），这就是我为什么不喜欢字符串的原因了，太能花哨了…

思路：因为连续段是和k有关的，所以k是要分==奇偶==的。首先先把最少的a和b根据k个排列好，在把剩下的a和b塞进去，可用高中知识的隔板法，可用大神拉马努金的整数拆分（这可是个神人啊！），关于整数拆分，可以看我上篇博客，这次就用排列组合就好了。

==k为偶==：那么最基本的形式就是abab…ab和baba….ba，这里用了k/2个的a和b，所以之前要判断一下，如果n-k/2或者m-k/2中有一个小于0，那答案不就是0了吗？好，如果都大于等于0的话，继续往下操作，a剩下n-k/2个，b剩下m-k/2个，这里就用简单的思路：

● △ ● △ ● △ ● △ ● △ ● △ ● △ (这里小圆圈代表a，小三角形代表b)

有k/2个a和k/2个b，所以只要把剩下的a和剩下的b插进去，如上图有k/2-1个插入位置，剩下的a有几种插法呢？我们给剩下的a+k/2，这样都让每个位置都能插一个，避免了有一个位置没有插进去的a，所以有$C_(n - 1, k / 2 - 1)$中插法，请仔细思考一下。那么b的插法不也是和a一样的吗？所以当k为偶时，组合数=$2*C_(n-1, k / 2 - 1)*C_(m - 1, k / 2 -1)$。为什么要乘2呢？有没有忘记上面的abab和baba两种形式？

==k为奇==：根据上面的思路，最基本的形式就是abab…baba和baba…bab，这里就又要判断一下，用了多少个a和b，这里就交给你们自己推导一下了，最后的组合数为$C_(n-1, k / 2) * C_(m - 1,k / 2 -1) + C_(n - 1,k / 2 - 1)*C_(m - 1, k / 2)$。

最后这个组合数怎么求呢？因为分子分母太大可能会爆longlong，比如C(10000,5000)，那么该怎么求呢？有没有想起逆元的定义，如果想不起来了可以看我以前的博客乘法逆元。

因为组合也是分子/分母的形式，所以可以用逆元把除法转换成乘法，这样就可以用mod了。然后p是什么呢，1e9+7，这是一个素数啊，就可以知道用费马小定理求解逆元了，费马小定理可以用快速幂的方法。

思路大概就是这样，代码如下：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

##define INF 0x7f7f7f
##define mem(a,b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)
const ll mod = 1e9 + 7;
// const int maxn = 100005;

ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}

ll FPM(ll x,ll power)
{
    ll ans = 1;
    while(power)
    {
        if(power & 1)
        {
            ans = (ans % mod * x % mod) % mod;
        }
        x = (x % mod * x % mod) % mod;
        power >>= 1;
    }
    return ans % mod;
}

ll C(ll m, ll n)
{
    if(n * 2 > m)
        n = m - n;
    ll t = n;
    ll a = m, b = 1;
    ll ans = 1;
    while(t--)
    {
        ans = (ans % mod * (FPM(b, mod - 2) % mod * a % mod) % mod) % mod;
        a--;
        b++;
    }
    return ans % mod;
}

void solve()
{
    ll n, m, k;
    cin >> n >> m >> k;
    if(k == 1)
    {
        cout << "0";
        return ;
    }
    if(k % 2 == 0)
    {
        if((n - k / 2) < 0  (m - k / 2) < 0)
        {
            cout << "0";
            return ;
        }
        cout << ((2 * C(n - 1, k / 2 - 1) % mod) % mod * C(m - 1, k / 2 - 1) % mod) % mod;
    }
    else
    {
        ll a = 0, b = 0;
        if((n - (k + 1) / 2) >= 0 && (m - k / 2) >= 0)
        {
            a = (C(n - 1, (k + 1) / 2 - 1) % mod * C(m - 1, k / 2 - 1) % mod) % mod;
        }
        if((n - k / 2) >= 0 && (m - (k + 1) / 2) >= 0)
        {
            b = (C(n - 1, k / 2 - 1) % mod * C(m - 1, (k + 1) / 2 - 1) % mod) % mod;
        }
        cout << (a % mod + b % mod) % mod;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
##else
    ios::sync_with_stdio(false);
    int T = 1;
    //cin >> T;
    while(T--)
        solve();
##endif
    return 0;
}

不得不说，我还是太菜了，这应该是我的部分，比赛的时候看到字符串就扔了，实在不应该，对不起我的队友。

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