Loading [MathJax]/extensions/tex2jax.js

Codeforces 451E:Devu and Flowers 题解

主要思路

这道题需要多重集的知识,如果没有学习请看这篇博客的多重集部分。

很明显,题意要求我们求出多重集的组合数,且为“增强版组合数”。所以,我们根据公式,使用二进制分解的方法来求出即可。这是一道比较裸的多重集组合数问题。

代码

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// CF451E.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7, MAX_N = 25;
ll arr[MAX_N], n, inv[MAX_N], m;
ll quick_power(ll bas, ll tim)
{
ll ans = 1;
while (tim)
{
if (tim & 1)
ans = ans * bas % mod;
bas = bas * bas % mod;
tim >>= 1;
}
return ans;
}
ll C(ll a, ll b)
{
if (a < 0 || b < 0 || a < b)
return 0;
a %= mod;
if (a == 0 || b == 0)
return 1;
ll ans = 1;
for (int i = 0; i < b; i++)
ans = ans * (a - i) % mod;
for (int i = 1; i <= b; i++)
ans = ans * inv[i] % mod;
return ans;
}
int main()
{
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%lld", &arr[i]);
inv[0] = 1;
for (int i = 1; i < MAX_N; i++)
inv[i] = quick_power(i, mod - 2);
ll ans = 0;
for (int stat = 0; stat < (1 << n); stat++)
if (stat == 0)
ans = (ans + C(n + m - 1, n - 1)) % mod;
else
{
ll t = n + m, p = 0;
for (int i = 0; i < n; i++)
if ((stat >> i) & 1)
p++, t -= arr[i + 1];
t -= (p + 1);
if (p & 1)
ans = (ans - C(t, n - 1)) % mod;
else
ans = (ans + C(t, n - 1)) % mod;
}
ans = (ans + mod) % mod;
printf("%lld", ans);
return 0;
}
// CF451E.cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int mod = 1e9 + 7, MAX_N = 25; ll arr[MAX_N], n, inv[MAX_N], m; ll quick_power(ll bas, ll tim) { ll ans = 1; while (tim) { if (tim & 1) ans = ans * bas % mod; bas = bas * bas % mod; tim >>= 1; } return ans; } ll C(ll a, ll b) { if (a < 0 || b < 0 || a < b) return 0; a %= mod; if (a == 0 || b == 0) return 1; ll ans = 1; for (int i = 0; i < b; i++) ans = ans * (a - i) % mod; for (int i = 1; i <= b; i++) ans = ans * inv[i] % mod; return ans; } int main() { scanf("%lld%lld", &n, &m); for (int i = 1; i <= n; i++) scanf("%lld", &arr[i]); inv[0] = 1; for (int i = 1; i < MAX_N; i++) inv[i] = quick_power(i, mod - 2); ll ans = 0; for (int stat = 0; stat < (1 << n); stat++) if (stat == 0) ans = (ans + C(n + m - 1, n - 1)) % mod; else { ll t = n + m, p = 0; for (int i = 0; i < n; i++) if ((stat >> i) & 1) p++, t -= arr[i + 1]; t -= (p + 1); if (p & 1) ans = (ans - C(t, n - 1)) % mod; else ans = (ans + C(t, n - 1)) % mod; } ans = (ans + mod) % mod; printf("%lld", ans); return 0; }
// CF451E.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7, MAX_N = 25;
ll arr[MAX_N], n, inv[MAX_N], m;
ll quick_power(ll bas, ll tim)
{
    ll ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas % mod;
        bas = bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}
ll C(ll a, ll b)
{
    if (a < 0 || b < 0 || a < b)
        return 0;
    a %= mod;
    if (a == 0 || b == 0)
        return 1;
    ll ans = 1;
    for (int i = 0; i < b; i++)
        ans = ans * (a - i) % mod;
    for (int i = 1; i <= b; i++)
        ans = ans * inv[i] % mod;
    return ans;
}
int main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    inv[0] = 1;
    for (int i = 1; i < MAX_N; i++)
        inv[i] = quick_power(i, mod - 2);
    ll ans = 0;
    for (int stat = 0; stat < (1 << n); stat++)
        if (stat == 0)
            ans = (ans + C(n + m - 1, n - 1)) % mod;
        else
        {
            ll t = n + m, p = 0;
            for (int i = 0; i < n; i++)
                if ((stat >> i) & 1)
                    p++, t -= arr[i + 1];
            t -= (p + 1);
            if (p & 1)
                ans = (ans - C(t, n - 1)) % mod;
            else
                ans = (ans + C(t, n - 1)) % mod;
        }
    ans = (ans + mod) % mod;
    printf("%lld", ans);
    return 0;
}

source:Page 172,《算法竞赛进阶指南》李煜东著

Leave a Reply

Your email address will not be published. Required fields are marked *