BZOJ4665:小 w 的喜糖题解

解法

这道题是 DP + 容斥,正好是我不怎么会的类型。设状态\(f[i][j]\)为「考虑了前\(i\)个状态之后有\(j\)个颜色与原来一样的方案数(注意这里颜色不一样不是本质不同的)」。可以推出式子:

\[ dp[i][j] = \sum_{k = 0}^j dp[i – 1][j – k] {cnt[i] \choose k} \frac{cnt[i]!}{(cnt[i] – k)!} \]

继续阅读BZOJ4665:小 w 的喜糖题解

Codeforces Round #548 (Div. 2) 解题报告 (CF1139)

A – Even Substrings

很简单,扫描的时候如果所在数位为偶数位,向答案添加当前数位即可。

// A.cpp
#include <bits/stdc++.h>
using namespace std;
char str[66000];
int main()
{
    int ans = 0, len;
    scanf("%d", &len), scanf("%s", str + 1);
    for (int i = 1; i <= len; i++)
        if (((str[i] - '0') & 1) == 0)
            ans += i;
    printf("%d", ans);
    return 0;
}

继续阅读Codeforces Round #548 (Div. 2) 解题报告 (CF1139)

P1450:[HAOI2008]硬币购物题解

主要思路

我们先来考虑无限制的版本,也就是不考虑询问的硬币数量限制。我们可以用一个完全背包搞一搞,复杂度为线性。

dp[0] = 1;
for (int i = 0; i < 4; i++)
    for (int j = ci[i]; j < MAX_N; j++)
        dp[j] += dp[j - ci[i]];

继续阅读P1450:[HAOI2008]硬币购物题解

P3327:[SDOI2015]约数个数和题解

主要思路和推导

这道题还是比较有意思的(啊呀看了好久的题解才会写,真菜),主要就是把\(d\)转换成了:

\[ d(xy) = \sum_{i|x}^x \sum_{j|y}^y [\gcd(i,j) = 1] \]

可以感性理解一下:每一次约数被枚举出来的时候,只有互质的情况下才会被计数,避免了重复计数。 继续阅读P3327:[SDOI2015]约数个数和题解

Codeforces 451E:Devu and Flowers 题解

主要思路

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

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

代码

// 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,《算法竞赛进阶指南》李煜东著