[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 解题报告

二项式反演

对称的反演

二项式反演的主要内容就是:

\[ f_n = \sum_{i = 0}^n (-1)^i {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^i {n \choose i} f_i \]

这个反演的式子非常的优美:在这种形式下,它们是对称的。当然,亦可以写作:

\[ f_n = \sum_{i = 0}^n {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^{n – i} {n \choose i} f_i \]

继续阅读二项式反演

[Fortuna OJ]Aug 1st – Group A 解题报告

A – 水叮当的舞步

真的是玄妙重重。

我们先思考正常的暴力搜索:枚举每一次按下的颜色,然后检查继续更新。考虑用 IDA* 优化这个过程,首先估值函数就是剩下的颜色个数,因为至少需要更新这些颜色才有可能到达最终状态。然后注意控制 BFS 求连通块的个数的优化就行了。很好的一道题。

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

P3773:[CTSC2017]吉夫特题解

神仙思路

有一个“显然”的定理:如果满足\(n\&k==k\),那么\(C^k_n\)为奇数。具体感性证明:litble 的证明。所以,直接上代码。

代码

// P3773.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_N = 233393, mod = 1000000007;
int n, arr[MAX_N], bucket[MAX_N], f[MAX_N], ans;
int getMod(int num) { return num >= mod ? num - mod : num; }
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]), bucket[arr[i]] = i;
    for (int i = n; i >= 1; i--)
    {
        f[i] = 1;
        for (int j = (arr[i] & (arr[i] - 1)); j; j = arr[i] & (j - 1))
            if (bucket[j] > i)
                f[i] = getMod(f[i] + f[bucket[j]]);
        ans = getMod(ans + f[i]);
    }
    ans = (ans - n + mod) % mod;
    printf("%d", ans);
    return 0;
}