Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

P4491 [HAOI2018]染色

Posted on

多项式太弱了，每日一题。

题目传送门

考虑只有k个颜色满足条件，令其方案数为$G[k]$，则答案为：$\sum_{k=0}^{\min{m}{\frac{n}{S}}}G[k]W[0]$，经过简单的数学分析我们可以推出一个假的$G[k]$，$G[k] = \dbinom{m}{k}\dfrac{n!}{(S!)^k(n-Sk)!}(n-S*k)^{m-k}$

可以发现这玩意儿绝对不可能是答案（不然这就是送分题了），不过为了下文打的简单，我们令其为 $F[k]$。

再次经过分类讨论可得（主要是不会）：$F[k]=\sum\limits_{i=k}^{n}\dbinom{i}{k}*G[i]$

又进行一次二项式反演：$G[k]=\sum\limits_{i=k}^n(-1)^{i-k}\dbinom{i}{k}F[i]$

暴力展开组合数可得：

$G[k]=\sum\limits_{i=k}^n(-1)^{i-k}\dfrac{i!}{k!(i-k)!}F[i]$

$G[k]*k!=\sum\limits_{i=k}^n\dfrac{(-1)^{i-k}}{(i-k)!}i!F[i]$

这可以明显地看到差卷积形式了。

设 $A[i]=i!*F[i],\ B[i]=\dfrac{(-1)^i}{i!}$

则有$G[k]=\frac{1}{k!}\sum\limits_{i=k}^nA[i]B[i-k]$

Code

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
#define int long long
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void write(T res)
{
    if(res > 9) write(res / 10);
    putchar(res % 10 + '0');
}
const int N = 1e7 + 5, mod = 1004535809;
int n, m, s;
int qpow(int x, int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = x * res % mod;
        k >>= 1;
        x = x * x % mod;
    }
    return res;
}
int inv[N], p[N], a[N], b[N];
inline int C(int x, int y)
{
    return p[x] * inv[y] % mod * inv[x - y] % mod; 
}
inline void init()
{
    inv[0] = inv[1] = 1, p[0] = p[1] = 1;
    for(int i = 2;i <= max(n, m);i ++)
        p[i] = p[i - 1] * i % mod, inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for(int i = 2;i <= max(n, m);i ++) inv[i] = inv[i] * inv[i - 1] % mod;

    for(int i = 0;i <= min(m, n / s);i ++)
    {
        a[i] = C(m, i) * p[n] % mod * qpow(inv[s], i) % mod * inv[n - s * i] % mod * qpow(m - i, n - s * i) % mod * p[i] % mod;
        b[i] = (mod + (i & 1 ? -1 : 1) * inv[i]) % mod;
    }
}
int len, tot, bit, r[N];
inline void NTT(int x[], int op)
{
    for(int i = 0;i < tot;i ++)
        if(i < r[i]) swap(x[i], x[r[i]]);
    for(int mid = 1, gn, len;mid < tot;mid <<= 1)
    {
        len = mid << 1;
        gn = qpow(3, (mod - 1) / len);
        if(~op) gn = qpow(gn, mod - 2);
        for(int i = 0;i < tot;i += len)
            for(int j = 0, g = 1, a, b;j < mid;j ++, g = g * gn % mod)
            {
                a = x[i + j], b = g * x[i + j + mid] % mod;
                x[i + j] = (a + b) % mod;
                x[i + j + mid] = (a - b + mod) % mod;
            }
    }
    if(~op) return ;
    op = qpow(tot, mod - 2);
    for(int i = 0;i < tot;i ++) x[i] = x[i] * op % mod;
}
int ans;
signed main()
{
    read(n, m, s);
    init();
    len = min(m, n / s);
    tot = 1;
    while(tot <= len * 2 + 2) tot <<= 1, bit ++;
    for(int i = 0;i < tot;i ++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (bit - 1));
    reverse(a, a + len + 1);
    NTT(a, 1), NTT(b, 1);
    for(int i = 0;i < tot;i ++) a[i] = a[i] * b[i] % mod;
    NTT(a, -1);
    reverse(a, a + len + 1);
    for(int i = 0, o;i <= len;i ++)
        read(o), ans = (ans + a[i] * o % mod * inv[i]) % mod;
    write(ans);
    return 0;
}