TopCoder SRM502 TheCowDivOne

2016.03.29 20:53 Tue| 35 visits oi_2016| 2016_刷题日常| Text

题目大意

求从 0、1、2、...、N-1 这 N 个数中选出不同的 k 个数,使得它们的和是 N 的倍数的方案数。

知识储备

对于方程 $cx \equiv b \mod n$,有解当且仅当 $\gcd(c, n)|b$,且方程在区间 [0, n-1] 内解的个数恰好等于 $\gcd(c, n)$。

算法分析

设 F(p, k) 表示在 [0, n] 的范围内选取 k 个互不相同的整数,使得它们的和是 p 的倍数的方案数。如果我们直接计算,无法处理“互不相同”的条件。考虑使用容斥解决。

设 D(p, k, i) 表示选取 k 个整数,其中恰有 i 或 i+1 个元素相同,使得它们的和是 p 的倍数的方案数,这样就相当于将问题转化为了关于 i 个相同的整数和 k-i 个互不相同的正数的两个部分。由上面的知识储备,我们需要保证 k-i 个互不相同的正数的和是 $\gcd(i, p)$ 的倍数;而对于它们的每一个和,相同的整数的可能性也恰好会有 gcd(i, p) 种。这样,可以得到 $D(p, k, i) = F(\gcd(i, p), k - i) * \gcd(i, p)$。

回到上面的问题,通过容斥可以得到 $F(p, k) =\frac{1}{k} \sum_{i = 1}^k (-1)^{i + 1} * D(p, k, i)$,这样就可以很方便地利用记忆化搜索递归求解啦。

代码

 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
#include <bits/stdc++.h>
using namespace std;

#define mod 1000000007

class TheCowDivOne
{
    map<int, int> mp[1005];
    int power(int a, int b)
    {
        int re = 1;
        while (b)
        {
            if (b & 1) re = 1ll * re * a % mod;
            a = 1ll * a * a % mod; b >>= 1;
        }
        return re;
    }
    int dfs(int n, int p, int k)
    {
        if (k == 0)
            return 1;
        if (mp[k].find(p) != mp[k].end())
            return mp[k][p];
        int re = 0;
        for (int i = 1; i <= k; ++i)
            re = re + (i & 1 ? 1ll : -1ll) * (n / p)
                    * dfs(n, __gcd(i, p), k - i) % mod * __gcd(i, p) % mod,
            re = (re % mod + mod) % mod;
        return mp[k][p] = 1ll * re * power(k, mod - 2) % mod;
    }
public:
    int find(int N, int K)
    {
        return dfs(N, N, K);
    }
};