Cydiater

「BZOJ 4314」倍数?倍数!

在$[0, N)$中选择$K$个互不相同的数字,满足其和在模$N$的意义下为$0$,求方案数。

首先,因为是$K$个互不相同的数字,而且往往序列的计数比集合更加方便,所以我们考虑按照一个长度为$K$的序列来计算,最后答案除以$K!$的即可。

然后我们发现,如果前$K - 1$个数任意选,那么最后一个数的取值也就固定了,即通过最后一个数的取值来修正前面的和的偏差。这样做唯一可能存在的问题就是最后这个数的有可能和前面的数发生重复。我们考虑如何剔除这些方案。

同样的,我们考虑把前面那个相同的数移到最后面,也就是前$K - 2$个数和为$S$,后两个数都是$x$。也就是说求$S + 2x \equiv 0 \pmod N$,即$-S \equiv 2x \pmod N$。我们要求的是这个式子的解的数量,先考虑更一般的形式,即$ax \equiv d \pmod N$,我们可以发现,如果$(a, N) = d$,那么当$x \in [0, N)$时,$ax\ mod\ N$的取值可以取遍$[0, N)$内所有$d$的倍数,且每个数都会被$d$次。简单画一画就能发现,挺显然的。

然后,我们就把这个问题转化成了一个规模更小的问题,即$K - 1$个数随便选,有多少个数是$(2, N)$的倍数。我们考虑用更一般形式,用$f(n, m, k)$来表示在$[0, N)$内选择$n$个数,同时最后一个数重复$k$次,和是$m$的倍数的方案数。由上面证明的可以得知,对于$f(n - 1, (m, k), 1)$的每个方案,最后一个数在$[0, m)$内都有$(m, k)$种选择,又因为$m$是$N$的因数,所以总的方案数就是$\frac{N}{m}(m, k)\times f(n - 1, (m, k), 1)$,但是还有可能出现最后这$k$个数和前面的数重复的情况出现,所以我们直接减掉$(n - 1)\times f(n - 1, m, k + 1)$即可。

然后我们考虑一下时空复杂度,因为这个处理的是$N$与$K$以内的公因数,所以下降是非常快的,复杂度可以看作是$K^2\sqrt K$的,然后空间上,可以发现除了$k = 1$的情况下,其他的情况都不会多次访问,所以我们只记忆化$k = 1$的情况即可,空间也是$K^2$的。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline void cmax(T & x, T y){y > x ? x = y : 0;}
template<typename T> inline void cmin(T & x, T y){y < x ? x = y : 0;}

const int MAXN = 1005;
const int mod = 1e9 + 7;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}

int qpow(int a, int b){
    int c = 1;
    while (b) {
        if (b & 1) cmul(c, a);
        cmul(a, a); b >>= 1;
    }
    return c;
}

int gcd(int a, int b){return !b ? a : gcd(b, a % b);}

int N, K, f[MAXN][MAXN], fac[MAXN], inv[MAXN];

int DFS(int n, int m, int k){
    int o = (m == N ? 0 : m), d = gcd(m, k);
    if (k == 1 && f[n][o] != -1) return f[n][m];
    if (n == 1) return N / m * d;
    if (m == 1) return fac[n]; 
    int sum = mul(N / m * d, DFS(n - 1, d, 1));
    cpop(sum, mul(n - 1, DFS(n - 1, m, k + 1)));
    if (k == 1) f[n][o] = sum;
    return sum;
}

int main(){
    scanf("%d%d", &N, &K);
    memset(f, -1, sizeof(f));
    fac[0] = 1;
    up (i, 1, K) fac[i] = mul(fac[i - 1], N - i + 1);
    int ans = DFS(K, N, 1);
    up (i, 2, K) cmul(ans, qpow(i, mod - 2));
    printf("%d\n", ans);
    return 0;
}