LibreOJ 2271 「SDOI2017」遗忘的集合

发表于 | 分类于 | 12

所以其实解是唯一的……
所以字典序什么的根本不存在……
迷惑行为……

令 ai=[i∈S]，则 f 的生成函数 F(x)=∞∑i=0f(i)xi=n∏i=1(11−xi)ai

两边取 ln，得 lnF(x)=−n∑i=1ailn(1−xi)

对右边泰勒展开，得 lnF(x)=n∑i=1ai∞∑j=1xijj

根据某些莫反套路，换元，令 T=ij，得 lnF(x)=∞∑T=1xTT∑d|Tadd

听说要莫反，然而其实直接枚举倍数减掉贡献就行了。
然后就能求出 ai 了。
然后这题就切了。

代码： 

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define add(a,b) (a + b >= mod ? a + b - mod : a + b)
#define dec(a,b) (a < b ? a - b + mod : a - b)
using namespace std;
const int N = 1 << 19;
const double pi = acos(-1);
const int W = 1 << 15;
int len,mod,n,ans;
int lg2[N + 5],rev[N + 5];
int fac[N + 5],ifac[N + 5],inv[N + 5];
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
struct poly
{
    int a[N + 5];
    inline const int &operator[](int x) const
    {
        return a[x];
    }
    inline int &operator[](int x)
    {
        return a[x];
    }
    inline void clear(int x = 0)
    {
        memset(a + x,0,(N - x + 1) << 2);
    }
} f;
struct cp
{
    double a,b;
    inline void operator+=(const cp &o)
    {
        a += o.a,b += o.b;
    }
    inline cp operator+(const cp &o) const
    {
        return (cp){a + o.a,b + o.b};
    }
    inline cp operator-(const cp &o) const
    {
        return (cp){a - o.a,b - o.b};
    }
    inline cp operator*(const cp &o) const
    {
        return (cp){a * o.a - b * o.b,a * o.b + b * o.a};
    }
    inline void operator*=(const cp &o)
    {
        *this = *this * o;
    }
    inline cp operator*(const double &o) const
    {
        return (cp){a * o,b * o};
    }
    inline cp operator~() const
    {
        return (cp){a,-b};
    }
} rt[N + 5];
inline void init(int len)
{
    for(n = 1;n < len;n <<= 1);
    for(register int i = 2;i <= n;++i)
        lg2[i] = lg2[i >> 1] + 1;
    for(register int i = 0;i <= (n >> 1);++i)
        rt[(n >> 1) + i] = (cp){cos(2 * pi * i / n),sin(2 * pi * i / n)};
    for(register int i = (n >> 1) - 1;i;--i)
        rt[i] = rt[i << 1];
    fac[0] = 1;
    for(register int i = 1;i <= n;++i)
        fac[i] = (long long)fac[i - 1] * i % mod;
    ifac[n] = fpow(fac[n],mod - 2);
    for(register int i = n;i;--i)
        ifac[i - 1] = (long long)ifac[i] * i % mod;
    for(register int i = 1;i <= n;++i)
        inv[i] = (long long)ifac[i] * fac[i - 1] % mod;
}
inline void fft(cp *a,int type,int n)
{
    type == -1 && (reverse(a + 1,a + n),1);
    int lg = lg2[n] - 1;
    for(register int i = 0;i < n;++i)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << lg),
        i < rev[i] && (swap(a[i],a[rev[i]]),1);
    for(register int w = 2,m = 1;w <= n;w <<= 1,m <<= 1)
        for(register int i = 0;i < n;i += w)
            for(register int j = 0;j < m;++j)
            {
                cp t = rt[m | j] * a[i | j | m];
                a[i | j | m] = a[i | j] - t,a[i | j] += t;
            }
    if(type == -1)
        for(register int i = 0;i < n;++i)
            a[i].a /= n,a[i].b /= n;
}
inline void mul(poly &a,const poly &b,int n)
{
    static cp f[N + 5],g[N + 5],h[N + 5];
    int lim = 1;
    memset(f,0,sizeof f),memset(g,0,sizeof g);
    for(;lim < (n << 1);lim <<= 1);
    for(register int i = 0;i < n;++i)
        f[i] = (cp){a[i] / W,a[i] % W},g[i] = (cp){b[i] / W,b[i] % W};
    fft(f,1,lim),fft(g,1,lim);
    for(register int i = 0;i < lim;++i)
        h[i] = ~f[(lim - i) % lim];
    for(register int i = 0;i < lim;++i)
        f[i] *= g[i],g[i] *= h[i];
    fft(f,-1,lim),fft(g,-1,lim);
    for(register int i = 0;i < lim;++i)
    {
        long long ac = (f[i].a + g[i].a) / 2 + 0.5;
        long long bd = g[i].a - ac + 0.5;
        long long bcad = f[i].b + 0.5;
        a[i] = ((ac % mod * W % mod * W % mod) % mod + (bcad % mod * W % mod) % mod + bd % mod) % mod;
    }
}
inline poly inverse(const poly &f,int n)
{
    static int s[30];
    static poly g,h,q;
    int top = 0;
    g.clear();
    for(;n > 1;s[++top] = n,n = (n + 1) >> 1);
    g[0] = fpow(f[0],mod - 2);
    for(;top;--top)
    {
        n = s[top];
        q = g,h = f,h.clear(n);
        mul(g,g,n),g.clear(n),mul(g,h,n);
        for(register int i = 0;i < n;++i)
            g[i] = dec(add(q[i],q[i]),g[i]);
        g.clear(n);
    }
    return g;
}
inline void derivative(poly &f,int n)
{
    for(register int i = 1;i < n;++i)
        f[i - 1] = (long long)f[i] * i % mod;
    f[n - 1] = 0;
}
inline void integral(poly &f,int n)
{
    for(register int i = n - 1;~i;--i)
        f[i + 1] = (long long)f[i] * inv[i + 1] % mod;
    f[0] = 0;
}
inline poly ln(const poly &f,int n)
{
    static poly g;
    g = f,derivative(g,n),mul(g,inverse(f,n),n),integral(g,n);
    return g;
}
int main()
{
    scanf("%d%d",&len,&mod),init((len + 1) << 1),f[0] = 1;
    for(register int i = 1;i <= len;++i)
        scanf("%d",f.a + i);
    f = ln(f,len + 1);
    for(register int i = 1;i <= len;++i)
        f[i] = (long long)f[i] * i % mod;
    for(register int i = 1;i <= len;++i)
    {
        ans += (bool)f[i];
        for(register int j = 2 * i;j <= len;j += i)
            f[j] = dec(f[j],f[i]);
    }
    printf("%d\n",ans);
    for(register int i = 1;i <= len;++i)
        f[i] && (printf("%d ",i),1);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment