[Fortuna OJ]Aug 13th – Group A 解题报告

A – Count

真难。

简单来讲,题目要求满足\(\{x_i \mod m \in [1, m – 1]\}\)的\(k\)元组个数。我们可以先把\(x_i\)全部模上一个\(m\),然后令\(A = \sum_{i = 1}^k (x_i \mod m)\)(注意,\(A\)并没有被整体取模,只是各项余数之和),可知\(A \mod m = n \mod m\),且\(A\)的上限就是\(A = k(m – 1)\)(各项上限)。

我们做了这样一个设置之后,问题就可以转换为:对于每一个不同的\(A\),满足\(A \mod m = n \mod m\)且\(A = \sum_{i = 1}^k (x_i \mod m), \forall i, x_i \in [1, m – 1]\)的\(k\)元组方案数。首先,我们可以先枚举每一个\(A\)来缩小问题的范围,根据\(A\)所满足的条件,可以这样遍历\(i\)来获得每一个\(A\):

继续阅读[Fortuna OJ]Aug 13th – Group A 解题报告

BZOJ4361:isn 题解

解法

这道题很有意思。首先搞一个 \(DP\) 来算出不同长度的不降子序列的个数,方程为:

\[ f[i, j] = \sum_{k < i, a_k \leq a_i} f[k, j – 1] \]

发现可以用树状数组优化,所以这里的复杂度为\(O(n^2 \log n)\)。设\(g[i] = \sum_{i = 1} f[i, n]\),考虑对答案的贡献。对于一个\(i\),有\(g[i] * (n – i)!\)种方案做变换,但是考虑这\((n – i)!\)中包含了提前变换完成的可能,也就是在我们从合法序列中删去了合法元素的可能,这样肯定是不行的。考虑进行容斥,贡献就是\(g[i](n-i)! – g[i+1](n – i – 1)!(i + 1)\),表示在这些里选择\(i+1\)个合法元素的方案。

继续阅读BZOJ4361:isn 题解

Codeforces Round #539 (Div. 2) 解题报告 (CF1113)

C – Sasha and a Bit of Relax

其实这道题是一道大水题。我们知道成立条件为\(x_l \text{ xor } x_{l+1} \dots x_{mid} = x_{mid+1} \text{ xor } x_{mid+2} \dots x_{r}\),然而这个运算可以直接移项:因为\(xor\)是自己本身的逆运算。然后为了保证\(r-l+1\)为偶数,我们只需要在 Trie 树末端维护奇偶计数即可。

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

P2154:[SDOI2009]虔诚的墓主人题解

解法

这道题很有意思啊。如果暴力枚举,答案式子:

\[ans = \sum_{x}^n \sum_{y}^m {up_{x,y} \choose k} {left_{x,y} \choose k} {right_{x,y} \choose k} {down_{x,y} \choose k}\]

其中\(up, left, right, down\)代表上下左右的常青树棵树。如何降低复杂度?

首先,我们可以考虑进行离散化:上下左右只要有为\(0\)的情况是不可能对答案有贡献的。然后,发现空隙中上下的部分:

继续阅读P2154:[SDOI2009]虔诚的墓主人题解

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