捱-捱-䫮问题总结

2016.01.05 14:07 Tue| 14 visits oi_2016| 2016_刷题日常| Text

HDU4609 3-idiots

不妨来枚举最长边,则长度和小于等于最长边长度的边的对数,就是不能构成三角形的情况数。用生成函数求个卷积先去重再算个前缀和就可以很方便地统计答案了。

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

#define N 270000

const double pi = acos(-1.0);

int test, n, a[N];
long long b[N];
complex<double> c[N];

void fft(complex<double> x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        complex<double> wn(cos(type * 2 * pi / s), sin(type * 2 * pi / s));
        for (int i = 0; i < n; i += s)
        {
            complex<double> w(1, 0), t;
            for (int j = 0; j < s >> 1; w *= wn, ++j)
                t = w * x[i + j + (s >> 1)],
                x[i + j + (s >> 1)] = x[i + j] - t, x[i + j] += t;
        }
    }
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cout << fixed << setprecision(7);
    cin >> test;
    while (test--)
    {
        cin >> n;
        memset(b, 0, sizeof b);
        int mx = 0, s = 1;
        for (int i = 1; i <= n; ++i)
            a[i] = read(), ++b[a[i]], mx = max(mx, a[i]);
        while (s < (mx + 1) * 2) s *= 2;
        for (int i = 0; i < s; ++i) c[i] = b[i];
        fft(c, s, 1);
        for (int i = 0; i < s; ++i) c[i] = c[i] * c[i];
        fft(c, s, -1);
        for (int i = 0; i <= mx; ++i)
            b[i] = (long long)(c[i].real() / s + 0.1);
        for (int i = 1; i <= n; ++i) --b[a[i] * 2];
        for (int i = 1; i <= mx; ++i) b[i] = b[i] / 2 + b[i - 1];
        long long sum = 0;
        for (int i = 1; i <= n; ++i) sum += b[a[i]];
        cout << 1.0 - 6.0 * sum / n / (n - 1) / (n - 2) << '\n';
    }
    return 0;
}

SPOJTSUM Triple Sums

和 BZOJ3771 丢斧子这道题基本一样,用生成函数算一算之后再容斥一下就得到了答案。

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

#define N 270000

int n;
long long a[N], f[N], g[N], h[N], f3[N], fg[N];
complex<double> c[N], d[N];
const double pi = 3.14159265358979323;

void fft(complex<double> x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        complex<double> wn(cos(type * 2 * pi / s), sin(type * 2 * pi / s));
        for (int i = 0; i < n; i += s)
        {
            complex<double> w(1, 0), t;
            for (int j = 0; j < s >> 1; w *= wn, ++j)
                t = w * x[i + j + (s >> 1)],
                x[i + j + (s >> 1)] = x[i + j] - t, x[i + j] += t;
        }
    }
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        a[i] = read() + 20000,
        ++f[a[i]], ++g[a[i] * 2], ++h[a[i] * 3];
    for (int i = 0; i < 262144; ++i)
        c[i] = f[i], d[i] = g[i];
    fft(c, 262144, 1), fft(d, 262144, 1);
    for (int i = 0; i < 262144; ++i)
        d[i] = d[i] * c[i], c[i] = c[i] * c[i] * c[i];
    fft(c, 262144, -1), fft(d, 262144, -1);
    for (int i = 0; i < 262144; ++i)
        f3[i] = c[i].real() / 262144 + 0.1, fg[i] = d[i].real() / 262144 + 0.1;
    for (int i = 0; i <= 120000; ++i)
    {
        int temp = (f3[i] - 3 * fg[i] + 2 * h[i]) / 6;
        if (temp) printf("%d : %d\n", i - 60000, temp);
    }
    return 0;
}

UVA12633 Super Rooks on Chessboard

先只考虑覆盖整行和整列的情况,用 FFT 求出来每一斜行中有多少个未被覆盖的格子,之后把没被覆盖的斜行上的答案加起来。

我怎么才知道强制类型转换是截掉尾巴的,而不是四舍五入。

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

#define N 140000

int test, r, c, n, a[N], b[N], tag[N];
complex<double> p[N], q[N];
const double pi = 3.14159265358979323;

void fft(complex<double> x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        complex<double> wn(cos(type * 2 * pi / s), sin(type * 2 * pi / s));
        for (int i = 0; i < n; i += s)
        {
            complex<double> w(1, 0), t;
            for (int j = 0; j < s >> 1; w *= wn, ++j)
                t = w * x[i + j + (s >> 1)],
                x[i + j + (s >> 1)] = x[i + j] - t, x[i + j] += t;
        }
    }
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> test;
    for (int t = 1; t <= test; ++t)
    {
        cin >> r >> c >> n;
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        memset(tag, 0, sizeof tag);
        for (int i = 0; i < r; ++i) a[i] = 1;
        for (int i = 0; i < c; ++i) b[i] = 1;
        for (int x, y, i = 1; i <= n; ++i)
            x = r - read(), y = read() - 1,
            a[x] = b[y] = 0, tag[x + y] = true;
        int s = 1;
        while (s < max(r, c) * 2) s <<= 1;
        for (int i = 0; i < s; ++i)
            p[i] = a[i], q[i] = b[i];
        fft(p, s, 1), fft(q, s, 1);
        for (int i = 0; i < s; ++i) p[i] *= q[i];
        fft(p, s, -1);
        long long ans = 0;
        for (int i = 0; i < s; ++i)
            if (!tag[i]) ans += p[i].real() / s + 0.1;
        printf("Case %d: %lld\n", t, ans);
    }
    return 0;
}

HDU5307 He is Flying

I am flying, too.

对于数组的前缀和 sum,如果 sum[i] + (-sum[j]) = k,那么我们在 k 处就可以获得一个 i - j 的收益,用 FFT 跑一跑再减一减就好了。

注意由于前缀和是单调不减的,所以当 k > 0 的时候我们可以保证 i > j。然而当 k = 0 的时候,就没有办法保证了,需要特判。

另外这题需要用 long double。

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

#define N 270000

int test, n;
long long sum[N];
complex<long double> a[N], b[N], c[N], d[N];
const long double pi = 3.14159265358979323;

void fft(complex<long double> x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        complex<long double> wn(cos(type * 2 * pi / s), sin(type * 2 * pi / s));
        for (int i = 0; i < n; i += s)
        {
            complex<long double> w(1, 0), t;
            for (int j = 0; j < s >> 1; w *= wn, ++j)
                t = w * x[i + j + (s >> 1)],
                x[i + j + (s >> 1)] = x[i + j] - t, x[i + j] += t;
        }
    }
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> test;
    while (test--)
    {
        cin >> n;
        for (int i = 0; i < 131072; ++i)
            a[i] = b[i] = c[i] = d[i] = 0;
        long long ans = 0;
        for (int i = 1, cnt = 0; i <= n; ++i)
        {
            sum[i] = sum[i - 1] + read();
            if (sum[i] == sum[i - 1])
                ++cnt, ans += 1ll * cnt * (cnt + 1) / 2;
            else cnt = 0;
        }
        for (int i = 1; i <= n; ++i)
            a[sum[i]] += i, c[sum[i]] += 1;
        for (int i = 0; i < n; ++i)
            b[50000 - sum[i]] += 1, d[50000 - sum[i]] += i;
        fft(a, 131072, 1), fft(b, 131072, 1);
        fft(c, 131072, 1), fft(d, 131072, 1);
        for (int i = 0; i < 131072; ++i)
            a[i] *= b[i], c[i] *= d[i];
        fft(a, 131072, -1), fft(c, 131072, -1);
        long long t1, t2;
        printf("%lld\n", ans);
        for (int i = 1; i <= sum[n]; ++i)
            t1 = a[50000 + i].real() / 131072 + 0.1,
            t2 = c[50000 + i].real() / 131072 + 0.1,
            printf("%lld\n", t1 - t2);
    }
    return 0;
}

UVALive4671 K-neighbor substrings

卡复数的常数的变态!

好吧,这题只需要反转短串去匹配长串,找到的位置 hash 一下判重而已。

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

#define N 262144

char s1[N], s2[N];
int n, test, cnt[N];
long long base[N], h[N];
set<long long> st;
const double pi = 3.14159265358979323;

struct comp
{
    double x, y;
    comp(double _x = 0.0, double _y = 0.0) : x(_x), y(_y) {}
    comp operator +(comp &c) { return comp(x + c.x, y + c.y); }
    comp operator -(comp &c) { return comp(x - c.x, y - c.y); }
    comp operator *(comp &c) { return comp(x * c.x - y * c.y, x * c.y + y * c.x); }
    double real() { return x; }
};

comp a[N], b[N];

void fft(comp x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        comp wn(cos(type * 2 * pi / s), sin(type * 2 * pi / s));
        for (int i = 0; i < n; i += s)
        {
            comp w(1, 0), t;
            for (int j = 0; j < s >> 1; w = w * wn, ++j)
                t = w * x[i + j + (s >> 1)],
                x[i + j + (s >> 1)] = x[i + j] - t, x[i + j] = x[i + j] + t;
        }
    }
}

long long power(long long a, long long b)
{
    long long re = 1;
    while (b)
    {
        if (b & 1) re *= a;
        a *= a, b >>= 1;
    }
    return re;
}

int main()
{
    base[1] = 1;
    for (int i = 2; i <= 100000; ++i)
        base[i] = base[i - 1] * 131;
    while (cin >> n, n != -1)
    {
        cin.ignore(20, '\n');
        gets(s1); gets(s2);
        int l1 = strlen(s1), l2 = strlen(s2);
        reverse(s2, s2 + l2);
        for (int i = 1; i <= l1; ++i)
            h[i] = h[i - 1] + (s1[i - 1] - 'a') * base[i];
        memset(cnt, 0, sizeof cnt);
        int s = 1;
        while (s < 2 * l1) s <<= 1;
        for (int i = 0; i < s; ++i) a[i] = b[i] = 0;
        for (int i = 0; i <= l1; ++i) a[i] = (s1[i] == 'a');
        for (int i = 0; i <= l2; ++i) b[i] = (s2[i] == 'a');
        fft(a, s, 1), fft(b, s, 1);
        for (int i = 0; i < s; ++i) a[i] = a[i] * b[i];
        fft(a, s, -1);
        for (int i = l2 - 1; i < l1; ++i)
            cnt[i] += a[i].real() / s + 0.5;
        for (int i = 0; i < s; ++i) a[i] = b[i] = 0;
        for (int i = 0; i <= l1; ++i) a[i] = (s1[i] == 'b');
        for (int i = 0; i <= l2; ++i) b[i] = (s2[i] == 'b');
        fft(a, s, 1), fft(b, s, 1);
        for (int i = 0; i < s; ++i) a[i] = a[i] * b[i];
        fft(a, s, -1);
        for (int i = l2 - 1; i < l1; ++i)
            cnt[i] += a[i].real() / s + 0.5;
        int ans = 0;
        st.clear();
        for (int i = l2 - 1; i < l1; ++i)
            if (l2 - cnt[i] <= n)
            {
                long long t = (h[i + 1] - h[i - l2 + 1]) * base[l1 - i];
                if (st.find(t) == st.end()) ++ans, st.insert(t);
            }
        printf("Case %d: %d\n", ++test, ans);
    }
    return 0;
}

CF528D Fuzzy Search

CF 神评测机。数据范围那么大,还以为要被卡常数卡得死去活来。

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

#define N 524288

int n, m, k, cnt[N], ans;
char s1[N], s2[N];
complex<double> a[N], b[N];

const double pi = 3.14159265358979323;

void fft(complex<double> x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        complex<double> wn(cos(type * 2 * pi / s), sin(type * 2 * pi / s));
        for (int i = 0; i < n; i += s)
        {
            complex<double> w(1, 0), t;
            for (int j = 0; j < s >> 1; w *= wn, ++j)
                t = w * x[i + j + (s >> 1)],
                x[i + j + (s >> 1)] = x[i + j] - t, x[i + j] += t;
        }
    }
}

inline void paint(int x, int t)
{
    for (int i = 1; i <= k; ++i)
        if (x + i * t < 0 || x + i * t >= n || a[x + i * t].real()) break;
        else a[x + i * t] = 1;
}

void color(char c)
{
    int s = 1; while (s < n * 2) s <<= 1;
    for (int i = 0; i < s; ++i) a[i] = b[i] = 0;
    for (int i = 0; i < n; ++i) a[i] = (s1[i] == c);
    for (int i = 0; i < m; ++i) b[i] = (s2[i] == c);
    for (int i = 0; i < n; ++i) if (a[i].real()) paint(i, -1);
    for (int i = n - 1; i >= 0; --i) if (a[i].real()) paint(i, 1);
    fft(a, s, 1), fft(b, s, 1);
    for (int i = 0; i < s; ++i) a[i] *= b[i];
    fft(a, s, -1);
    for (int i = m - 1; i < n; ++i) cnt[i] += a[i].real() / s + 0.5;
}

int main()
{
    cin >> n >> m >> k;
    scanf("%s%s", s1, s2);
    reverse(s2, s2 + m);
    color('A'), color('G'), color('C'), color('T');
    for (int i = m - 1; i < n; ++i) if (cnt[i] == m) ++ans;
    cout << ans << endl;
    return 0;
}

ZOJ5522 Permutation Graph

设 dp[i] 表示大小为 i 的连通块内的方案数,有转移方程 dp[i] = i! - ∑(k!*dp[i-k])。用 CDQ 分治预处理出 dp 数组,之后只需要把所有块的答案乘起来。

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

#define N 270000
#define P 786433
#define G 10

int test, n, m, dp[N], fac[N];
int a[N], b[N];

int power(int a, int b)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % P;
        a = 1ll * a * a % P, b >>= 1;
    }
    return re;
}

void ntt(int x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        int wn = power(G, (P - 1) / s);
        for (int i = 0; i < n; i += s)
        {
            for (int w = 1, t, j = 0; j < s >> 1; w = 1ll * w * wn % P, ++j)
            {
                t = 1ll * w * x[i + j + (s >> 1)] % P,
                x[i + j + (s >> 1)] = (x[i + j] - t + P) % P,
                x[i + j] = (x[i + j] + t) % P;
            }
        }
    }
    if (type == -1)
    {
        reverse(x + 1, x + n);
        int inv = power(n, P - 2);
        for (int i = 0; i < n; ++i)
            x[i] = 1ll * x[i] * inv % P;
    }
}

void cdq(int s, int l, int r)
{
    if (l == r) return;
    int mid = (l + r) >> 1;
    cdq(s >> 1, l, mid);
    for (int i = 0; i < 2 * s; ++i) a[i] = b[i] = 0;
    for (int i = 0; i < s; ++i)     a[i] = fac[i];
    for (int i = 0; i < s / 2; ++i) b[i] = dp[l + i];
    ntt(a, s * 2, 1), ntt(b, s * 2, 1);
    for (int i = 0; i < 2 * s; ++i) a[i] = 1ll * a[i] * b[i] % P;
    ntt(a, s * 2, -1);
    for (int i = mid + 1; i <= r; ++i)
        dp[i] = ((dp[i] - a[i - l]) % P + P) % P;
    cdq(s >> 1, mid + 1, r);
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    n = 131072;
    fac[0] = 1;
    for (int i = 1; i < n; ++i)
        dp[i] = fac[i] = 1ll * fac[i - 1] * i % P;
    cdq(n, 0, n - 1);
    cin >> test;
    while (test--)
    {
        cin >> n >> m;
        int ans = 1;
        while (m--)
        {
            int s = 0, l = 0x3f3f3f3f, r = 0;
            cin >> s;
            for (int x, i = 1; i <= s; ++i)
                x = read(), l = min(l, x), r = max(r, x);
            if (r - l + 1 != s) ans = 0;
            ans = 1ll * ans * dp[s] % P;
        }
        cout << ans << endl;
    }
    return 0;
}

HDU5322 Hope

能推出来公式嘛,又是 CDQ 分治。

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

#define N 270000
#define P 998244353
#define G 3

int n, inv[N], fac[N], dp[N];
int a[N], b[N];

int power(int a, int b)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % P;
        a = 1ll * a * a % P; b >>= 1;
    }
    return re;
}

void ntt(int x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        int wn = power(G, (P - 1) / s);
        for (int i = 0; i < n; i += s)
            for (int w = 1, t, j = 0; j < s >> 1; w = 1ll * w * wn % P, ++j)
                t = 1ll * w * x[i + j + (s >> 1)] % P,
                x[i + j + (s >> 1)] = (x[i + j] - t + P) % P,
                x[i + j] = (x[i + j] + t) % P;
    }
    if (type == -1)
    {
        reverse(x + 1, x + n);
        int inv = power(n, P - 2);
        for (int i = 0; i < n; ++i)
            x[i] = 1ll * x[i] * inv % P;
    }
}

void cdq(int s, int l, int r)
{
    if (s == 1) { dp[l] = 1ll * dp[l] * inv[l] % P; return; }
    int mid = (l + r) >> 1;
    cdq(s >> 1, l, mid);
    for (int i = 0; i < s << 1; ++i)    a[i] = b[i] = 0;
    for (int i = 0; i < s >> 1; ++i)    a[i] = dp[l + i];
    for (int i = 0; i < s; ++i)         b[i] = 1ll * i * i % P;
    ntt(a, s << 1, 1), ntt(b, s << 1, 1);
    for (int i = 0; i < s << 1; ++i)    a[i] = 1ll * a[i] * b[i] % P;
    ntt(a, s << 1, -1);
    for (int i = mid + 1; i <= r; ++i)  dp[i] = (dp[i] + a[i - l]) % P;
    cdq(s >> 1, mid + 1, r);
}

int main()
{
    n = 131072;
    inv[0] = inv[1] = 1;
    for (int i = 2; i < n; ++i)
        inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
    fac[0] = 1;
    for (int i = 1; i < n; ++i)
        fac[i] = 1ll * fac[i - 1] * i % P;
    dp[0] = 1;
    cdq(n, 0, n - 1);
    for (int i = 1; i < n; ++i)
        dp[i] = 1ll * dp[i] * fac[i] % P;
    ios::sync_with_stdio(false);
    while (cin >> n) cout << dp[n] << endl;
    return 0;
}

HDU5279 YJC plays Minecraft

对于单个小岛,使用 CDQ 分治分别算出来生成森林的种类数 dp 和首尾相互连通的生成森林的种类数 dp2。最后答案就是 2n * Πdp[a[i]] - Πdp2[a[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
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
#include <bits/stdc++.h>
using namespace std;

#define P 998244353
#define G 3
#define N 270000

int a[N], b[N], c[N];
int test, n, fac[N], invf[N], f[N], dp[N], dp2[N];

int power(int a, int b)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % P;
        a = 1ll * a * a % P; b >>= 1;
    }
    return re;
}

void ntt(int x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        int wn = power(G, (P - 1) / s);
        for (int i = 0; i < n; i += s)
            for (int w = 1, t, j = 0; j < s >> 1; w = 1ll * w * wn % P, ++j)
                t = 1ll * w * x[i + j + (s >> 1)] % P,
                x[i + j + (s >> 1)] = (x[i + j] - t + P) % P,
                x[i + j] = (x[i + j] + t) % P;
    }
    if (type == -1)
    {
        reverse(x + 1, x + n);
        int inv = power(n, P - 2);
        for (int i = 0; i < n; ++i)
            x[i] = 1ll * x[i] * inv % P;
    }
}

void cdq(int s, int l, int r)
{
    if (s == 1)
    {
        if (l >= 2)
            dp[l] = 1ll * dp[l] * fac[l - 1] % P,
            dp2[l] = 1ll * dp2[l] * fac[l - 2] % P;
        return;
    }
    int mid = (l + r) >> 1;
    cdq(s >> 1, l, mid);
    for (int i = 0; i < s << 1; ++i) a[i] = b[i] = c[i] = 0;
    for (int i = 0; i < s >> 1; ++i) a[i] = 1ll * dp[l + i] * invf[l + i] % P;
    for (int i = 1; i < s; ++i) b[i] = 1ll * f[i] * invf[i - 1] % P;
    for (int i = 2; i < s; ++i) c[i] = 1ll * f[i] * invf[i - 2] % P;
    ntt(a, s << 1, 1), ntt(b, s << 1, 1), ntt(c, s << 1, 1);
    for (int i = 0; i < s << 1; ++i)
        b[i] = 1ll * b[i] * a[i] % P, c[i] = 1ll * c[i] * a[i] % P;
    ntt(b, s << 1, -1), ntt(c, s << 1, -1);
    for (int i = mid + 1; i <= r; ++i)
        dp[i] = (dp[i] + b[i - l]) % P, dp2[i] = (dp2[i] + c[i - l]) % P;
    cdq(s >> 1, mid + 1, r);
}

int main()
{
    n = 131072;
    fac[0] = 1, invf[0] = 1;
    for (int i = 1; i < n; ++i)
        fac[i] = 1ll * fac[i - 1] * i % P,
        invf[i] = power(fac[i], P - 2);
    f[1] = 1;
    for (int i = 2; i < n; ++i)
        f[i] = power(i, i - 2);
    dp[0] = 1, dp2[1] = 1;
    cdq(n, 0, n - 1);
    cin >> test;
    while (test--)
    {
        cin >> n;
        int t1 = 1, t2 = 1;
        for (int x, i = 1; i <= n; ++i)
            scanf("%d", &x),
            t1 = 1ll * t1 * dp[x] % P * 2 % P, t2 = 1ll * t2 * dp2[x] % P;
        printf("%d\n", (t1 - t2 + P) % P);
    }
    return 0;
}

HDU5197 DZY Loves Orzing

递归分治 FFT,数组能小则小,空间能省则省会比较好。

最后需要乘上一个 (n^2)!,所以当 n 大于 32000 左右的时候答案就一定是 0 了。然后分块打表求阶乘。

  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
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
using namespace std;

#define P 999948289
#define G 13
#define N 32768

int n, a[N];
int fac250w[] = {1, 742557698, 73674372, 946356867, 886298213, 708096146,
        773952966, 660647426, 872660379, 621464629, 146240630, 11073907,
        331020507, 966916303, 263376751, 724913810, 404930321, 635221949,
        394551857, 498545176, 562325427, 536950599, 266925046, 738717434,
        668613051, 429147738, 909282801, 10912855, 970297033, 906782277,
        798256685, 380689162, 305223031, 473054317, 973044426, 398397354,
        873585932, 837082184, 35696442, 230154370, 848366675, 395030762,
        498317812, 791283606, 729876393, 687219084, 14144336, 388738202,
        622131681, 238052260, 615131072, 718331093, 297286611, 773716290,
        111157771, 431162756, 63177221, 161326878, 369205363, 623737506,
        324440645, 808909462, 413790768, 979151408, 772587162, 4464546,
        559757333, 443604604, 871676563, 371714542, 974193983, 82500450,
        942263908, 185315894, 104545933, 54223863, 211887878, 77999247,
        50565050, 305535316, 997740795, 130673094, 163897601, 289351808,
        66695114, 729120153, 237097830, 311587253, 27795376, 727556861,
        138776107, 547339192, 964309425, 131086468, 506867690, 717366159,
        806657302, 975045217, 73721470, 799384651, 60463155, 15278200,
        250677384, 581871560, 714962263, 601653537, 687281812, 20240697,
        342298761, 110345172, 849353846, 83945017, 780393742, 663545238,
        402233770, 633304039, 624925139, 759606655, 280567057, 199223565,
        284319289, 277878903, 561125465, 298353486, 892653210, 314654467,
        820967388, 803898851, 35901738, 704321056, 397403810, 622152175,
        621890919, 487787873, 362257679, 832878386, 501153778, 190322692,
        689952918, 863253097, 49637371, 340658016, 645535158, 369794366,
        534069911, 872112755, 298258593, 20035735, 736086411, 121186696,
        18422350, 710545571, 301862680, 711936868, 432266780, 135482878,
        1431021, 503084584, 688104229, 155901832, 315367468, 356914873,
        652947205, 54530841, 771192391, 421316800, 695569751, 82704405,
        118678737, 600804263, 627389929, 344664523, 355085077, 657495760,
        613054291, 584164727, 853004017, 139657216, 303988559, 994717222,
        476821457, 693827397, 73959941, 292387570, 875487721, 778373141,
        464724250, 911253787, 23051768, 143794805, 475646428, 393432389,
        141726621, 147248949, 438780884, 745854729, 226591160, 672670820,
        549951077, 995219236, 932612332, 203659324, 14131076, 168303421,
        940005061, 265855319, 23002519, 536206278, 554124620, 510061746,
        620748001, 851476369, 987244115, 291555139, 580925233, 149042572,
        558521374, 383274632, 918300894, 786183014, 791772397, 604994184,
        620615431, 73367798, 790581723, 129609522, 265043715, 180613781,
        799878129, 922586656, 882823746, 416283880, 66288172, 240708669,
        431208759, 909270842, 724075627, 409411141, 517922025, 900296204,
        68037893, 306567461, 617546261, 290320271, 217456008, 408357944,
        651783003, 994082737, 112479761, 792946647, 537749882, 48127529,
        379600720, 253401862, 916904109, 800175401, 525508328, 96487470,
        534528845, 395836029, 406445948, 379921383, 778598554, 156730709,
        927798812, 823130403, 990188195, 515403003, 580405577, 878394092,
        103880758, 719716046, 369947804, 400885024, 57489050, 181554553,
        857137539, 157433961, 259266107, 618532453, 371475709, 760270492,
        826167360, 604145120, 983464964, 970257267, 969187263, 695716939,
        84354794, 1275673, 459753124, 240615015, 823697497, 736174566,
        408012596, 421436679, 426648622, 54654320, 626945763, 157276986,
        431774328, 327946629, 271995405, 536066596, 354685176, 658141660,
        795926192, 727382616, 551735532, 982880700, 472720708, 245472179,
        874196764, 67365955, 500124791, 368566255, 187859258, 500096311,
        520519681, 241651317, 378661975, 801292082, 480958499, 728809526,
        877534116, 217369881, 370398983, 56870514, 353203151, 319391024,
        964920987, 89828706, 890177778, 937776515, 38365858, 658850875,
        255032131, 30426373, 603506321, 555264634, 357473599, 217304883,
        814105031, 170963255, 723364433, 498773700, 585876239, 733811895,
        2716955, 284767864, 88039508, 295139305, 193354430, 902796808,
        351016146, 934003196, 113186364, 476347933, 368512066, 417443364,
        464124136, 586566527, 959931458, 290088520, 426396915, 435341846,
        416364181, 983142297, 95992498, 350563026, 1545277, 530722193,
        402007436, 212766465, 280108510, 295107471, 806573913, 698216151,
        905660380, 730081216, 975610253, 628431500, 403315904, 420062544,
        699384843, 777116154, 850659214, 677271780, 541550777, 487813680,
        530330038, 949777737, 288556578, 425289288, 367496735, 776204139,
        620172524, 556042411, 437374109, 242497963};

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int getfac(int n)
{
    int re = fac250w[n / 2500000];
    for (int i = n / 2500000 * 2500000 + 1; i <= n; ++i)
        re = 1ll * re * i % P;
    return re;
}

int power(int a, int b)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % P;
        a = 1ll * a * a % P; b >>= 1;
    }
    return re;
}

void ntt(int x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        int wn = power(G, (P - 1) / s);
        for (int i = 0; i < n; i += s)
            for (int w = 1, t, j = 0; j < s >> 1; w = 1ll * w * wn % P, ++j)
                t = 1ll * w * x[i + j + (s >> 1)] % P,
                x[i + j + (s >> 1)] = (x[i + j] - t + P) % P,
                x[i + j] = (x[i + j] + t) % P;
    }
    if (type == -1)
    {
        reverse(x + 1, x + n);
        int inv = power(n, P - 2);
        for (int i = 0; i < n; ++i)
            x[i] = 1ll * x[i] * inv % P;
    }
}

void getfft(int a[], int l, int r)
{
    if (l == r) { a[0] = l % P; a[1] = 1; return; }
    int s[N] = {0}, t[N] = {0}, n = 1, mid = (l + r) >> 1;
    getfft(s, l, mid), getfft(t, mid + 1, r);
    while (n <= r - l + 1) n <<= 1;
    ntt(s, n, 1), ntt(t, n, 1);
    for (int i = 0; i < n; ++i)
        a[i] = 1ll * s[i] * t[i] % P;
    ntt(a, n, -1);
}

int main()
{
    while (cin >> n)
    {
        if (1ll * n * n >= P)
            { puts("0"); while (n--) read(); continue; }
        getfft(a, 0, n - 1);
        int ans = 1;
        for (int i = 1; i <= n; ++i)
            ans = 1ll * ans * a[read()] % P;
        ans = 1ll * ans * getfac(n * n) % P *
            power(power(getfac(n), n), P - 2) % P;
        cout << ans << endl;
    }
    return 0;
}

Tsinsen D11428 Prime Distance On Tree

在挺简单的一个树分治上面套了一个 FFT。

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

#define N 65536

int n, v[N], p[N], tot;
int vis[N], head[N], size[N], maxs[N];
long long ans;
complex<double> c[N];
const double pi = 3.14159265358979323;

void getprime(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (!v[i]) p[++tot] = i;
        for (int j = 1; i * p[j] <= n; ++j)
        {
            v[i * p[j]] = true;
            if (i % p[j] == 0) break;
        }
    }
}

void fft(complex<double> x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        complex<double> wn(cos(type * 2 * pi / s), sin(type * 2 * pi / s));
        for (int i = 0; i < n; i += s)
        {
            complex<double> w(1, 0), t;
            for (int j = 0; j < s >> 1; w *= wn, ++j)
                t = w * x[i + j + (s >> 1)],
                x[i + j + (s >> 1)] = x[i + j] - t, x[i + j] += t;
        }
    }
}

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[N * 2];

inline void add(int x, int y)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void getroot(int &root, int sum, int x, int fa)
{
    size[x] = 1, maxs[x] = 0;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            getroot(root, sum, edge[i].to, x),
            size[x] += size[edge[i].to],
            maxs[x] = max(maxs[x], size[edge[i].to]);
    maxs[x] = max(maxs[x], sum - size[x]);
    if (maxs[x] <= maxs[root]) root = x;
}

void dfs(int x, int fa)
{
    size[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            dfs(edge[i].to, x),
            size[x] += size[edge[i].to];
}

void getdis(complex<double> c[], int x, int fa, int d)
{
    c[d] = c[d] + complex<double>(1, 0);
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            getdis(c, edge[i].to, x, d + 1);
}

void solve(int x)
{
    dfs(x, 0), vis[x] = 1;
    int s = 1; while (s <= size[x]) s <<= 1;
    for (int i = 0; i < s; ++i) c[i] = 0;
    getdis(c, x, 0, 0), fft(c, s, 1);
    for (int i = 0; i < s; ++i) c[i] = c[i] * c[i];
    fft(c, s, -1);
    for (int i = 1; i <= tot && p[i] < s; ++i)
        ans += c[p[i]].real() / s + 0.5;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to])
        {
            s = 1; while (s <= size[edge[i].to] * 2) s <<= 1;
            for (int i = 0; i < s; ++i) c[i] = 0;
            getdis(c, edge[i].to, 0, 1), fft(c, s, 1);
            for (int i = 0; i < s; ++i) c[i] = c[i] * c[i];
            fft(c, s, -1);
            for (int i = 1; i <= tot && p[i] < s; ++i)
                ans -= c[p[i]].real() / s - 0.5;
        }
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to])
        {
            int root = 0; getroot(root, size[edge[i].to], edge[i].to, 0);
            solve(root);
        }
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n;
    cout << fixed << setprecision(10);
    getprime(n);
    for (int x, y, i = 1; i < n; ++i)
        x = read(), y = read(), add(x, y), add(y, x);
    maxs[0] = 0x3f3f3f3f;
    int root = 0; getroot(root, n, 1, 0);
    solve(root);
    cout << 1.0 * ans / n / (n - 1) << endl;
    return 0;
}

Tsinsen D11386 Arithmetic Progressions

分块,愉♂悦的时间复杂度。

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

#define B 2000
#define N 100005

int n, a[N], bcnt, bel[N], bl[N], br[N], cnt[N];
long long ans;
complex<double> c[N], d[N];
double pi = 3.14159265358979323;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void fft(complex<double> x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        complex<double> wn(cos(type * 2 * pi / s), sin(type * 2 * pi / s));
        for (int i = 0; i < n; i += s)
        {
            complex<double> w(1, 0), t;
            for (int j = 0; j < s >> 1; w *= wn, ++j)
                t = w * x[i + j + (s >> 1)],
                x[i + j + (s >> 1)] = x[i + j] - t, x[i + j] += t;
        }
    }
}

int main()
{
    cin >> n;
    memset(bl, 0x3f, sizeof bl);
    int bcnt = (n - 1) / B + 1;
    for (int i = 1; i <= n; ++i)
        bel[i] = (i - 1) / B + 1,
        bl[bel[i]] = min(bl[bel[i]], i),
        br[bel[i]] = max(br[bel[i]], i);
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    for (int i = 1; i <= bcnt; ++i)
    {
        for (int j = bl[i]; j <= br[i]; ++cnt[a[j]], ++j)
            for (int k = j + 1; k <= br[i]; ++k)
                if (a[j] * 2 - a[k] >= 1)
                    ans += cnt[a[j] * 2 - a[k]];
    }
    memset(cnt, 0, sizeof cnt);
    for (int i = bcnt; i; --i)
        for (int j = br[i]; j >= bl[i]; ++cnt[a[j]], --j)
            for (int k = j - 1; k >= bl[i]; --k)
                if (a[j] * 2 - a[k] >= 1)
                    ans += cnt[a[j] * 2 - a[k]];
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= bcnt; ++i)
    {
        for (int j = bl[i]; j <= br[i]; ++cnt[a[j]], ++j)
            for (int k = j + 1; k <= br[i]; ++k)
                if (a[j] * 2 - a[k] >= 1)
                    ans -= cnt[a[j] * 2 - a[k]];
        for (int j = bl[i]; j <= br[i]; --cnt[a[j]], ++j);
    }
    for (int s = 65536, i = 2; i < bcnt; ++i)
    {
        for (int j = 0; j < s; ++j) c[j] = d[j] = 0;
        for (int j = 1; j < bl[i]; ++j) c[a[j]] += 1.0;
        for (int j = br[i] + 1; j <= n; ++j) d[a[j]] += 1.0;
        fft(c, s, 1), fft(d, s, 1);
        for (int j = 0; j < s; ++j) c[j] *= d[j];
        fft(c, s, -1);
        for (int j = bl[i]; j <= br[i]; ++j)
            ans += c[a[j] * 2].real() / s + 0.5;
    }
    cout << ans << endl;
    return 0;
}

UOJ#86 mx的组合数

数位 DP 的类似物。Lucas 定理实际上就是将 $m \choose n$ 中的 m 和 n 转化成 p 进制,对每一位取组合数,最后将它们相乘。这样就可以得到一个递推方程了。发现转移方程是乘法取模的形式,我们有 $ind(a * b) = ind(a) + ind(b) \mod \varphi(p)$,这就支持用 FFT 求解啦!

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

#define P 998244353
#define G 3
#define N 65536
#define C 100

__int128_t n, l, r;
int p, fac[N], inv[N], ind[N];
int cn[C], cx[C], ans[N];
int f[N], g[N], a[N], b[N];

int power(int a, int b, int p)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % p;
        a = 1ll * a * a % p; b >>= 1;
    }
    return re;
}

int calc(int m, int n)
{
    if (m < n) return 0;
    return fac[m] * inv[fac[n]] % p * inv[fac[m - n]] % p;
}

int getg(int p, int phi)
{
    static int t[1000];
    int c = 0;
    for (int i = 2; i * i <= phi; ++i)
        if (phi % i == 0)
            t[++c] = i, t[++c] = phi / i;
    for (int i = 2; i < p; ++i)
        for (int j = 1; j <= c + 1; ++j)
            if (j == c + 1) return i;
            else if (power(i, t[j], p) == 1) break;
    return 0;
}

void ntt(int x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        int wn = power(G, (P - 1) / s, P);
        for (int i = 0; i < n; i += s)
            for (int w = 1, t, j = 0; j < s >> 1; w = 1ll * w * wn % P, ++j)
                t = 1ll * w * x[i + j + (s >> 1)] % P,
                x[i + j + (s >> 1)] = (x[i + j] - t + P) % P,
                x[i + j] = (x[i + j] + t) % P;
    }
    if (type == -1)
    {
        reverse(x + 1, x + n);
        int inv = power(n, P - 2, P);
        for (int i = 0; i < n; ++i)
            x[i] = 1ll * x[i] * inv % P;
    }
}

void prework()
{
    fac[0] = 1;
    for (int i = 1; i < p; ++i)
        fac[i] = fac[i - 1] * i % p;
    inv[1] = 1;
    for (int i = 2; i < p; ++i)
        inv[i] = inv[p % i] * (p - p / i) % p;
    int pr = getg(p, p - 1);
    for (int i = 0, t = 1; i < p - 1; ++i)
        ind[t] = i, t = t * pr % p;
}

void dp(__int128_t x, int type)
{
    __int128_t t = 1; int cnt = 0, s = 1;
    while ((n == 0 && t == 1) || t <= n)
        cn[cnt] = n / t % p, cx[cnt] = x / t % p, t *= p, ++cnt;
    while (s < 2 * p) s <<= 1;
    memset(f, 0, sizeof f), memset(g, 0, sizeof g);
    for (int i = cn[0]; i < p; ++i) ++f[ind[calc(i, cn[0])]];
    for (int i = cn[0]; i <= cx[0]; ++i) ++g[ind[calc(i, cn[0])]];
    for (int i = 1; i < cnt; ++i)
    {
        memset(a, 0, sizeof a), memset(b, 0, sizeof b);
        for (int j = cn[i]; j < p; ++j) ++a[ind[calc(j, cn[i])]];
        for (int j = cn[i]; j < cx[i]; ++j) ++b[ind[calc(j, cn[i])]];
        ntt(f, s, 1), ntt(a, s, 1), ntt(b, s, 1);
        for (int i = 0; i < s; ++i) a[i] = 1ll * f[i] * a[i] % P;
        for (int i = 0; i < s; ++i) b[i] = 1ll * f[i] * b[i] % P;
        ntt(a, s, -1), ntt(b, s, -1);
        if (cx[i] >= cn[i])
            for (int j = 0, t = ind[calc(cx[i], cn[i])]; j < p - 1; ++j)
                b[j + t] = (b[j + t] + g[j]) % P;
        memset(f, 0, sizeof f), memset(g, 0, sizeof g);
        for (int i = 0; i < s; ++i)
            f[i % (p - 1)] = (f[i % (p - 1)] + a[i]) % P,
            g[i % (p - 1)] = (g[i % (p - 1)] + b[i]) % P;
    }
    for (int i = 0; i < p; ++i)
        ans[i] = (ans[i] + type * (x / t) % P * f[i] % P) % P,
        ans[i] = (ans[i] + type * g[i] % P) % P;
}

inline __int128_t read()
{
    __int128_t x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> p; n = read(), l = read(), r = read();
    prework();
    dp(r, 1), dp(l - 1, -1);
    int ans0 = (r - l + 1) % P;
    for (int i = 1; i < p; ++i)
        ans0 = ((ans0 - ans[ind[i]]) % P + P) % P;
    printf("%d\n", ans0);
    for (int i = 1; i < p; ++i)
        printf("%d\n", (ans[ind[i]] % P + P) % P);
    return 0;
}

UOJ#50 【UR #3】链式反应

我终于放弃卡常数了。

 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>
using namespace std;

#define P 998244353
#define G 3
#define N 524288

int n, s, a[N], fac[N], finv[N], inv[N];
int dp[N], g[N], p[N], q[N];
char str[N];

int power(int a, int b)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % P;
        a = 1ll * a * a % P; b >>= 1;
    }
    return re;
}

void ntt(int x[], int n, int type)
{
    for (int i = 0, t = 0; i < n; ++i)
    {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int s = 2; s <= n; s <<= 1)
    {
        int wn = power(G, (P - 1) / s);
        for (int i = 0; i < n; i += s)
            for (int w = 1, t, j = 0; j < s >> 1; w = 1ll * w * wn % P, ++j)
                t = 1ll * w * x[i + j + (s >> 1)] % P,
                x[i + j + (s >> 1)] = (x[i + j] - t + P) % P,
                x[i + j] = (x[i + j] + t) % P;
    }
    if (type == -1)
    {
        reverse(x + 1, x + n);
        int inv = power(n, P - 2);
        for (int i = 0; i < n; ++i)
            x[i] = 1ll * x[i] * inv % P;
    }
}

void solve(int s, int l, int r)
{
    if (l == 0 && r == 1) return;
    if (s == 1) { dp[l] = 1ll * dp[l] * inv[l] % P * inv[2] % P; return; }
    int mid = (l + r) >> 1;
    solve(s >> 1, l, mid);
    for (int i = 0; i < s << 1; ++i) p[i] = q[i] = 0;
    for (int i = 0; i < s >> 1; ++i) p[i] = dp[l + i];
    for (int i = 0; i < s && i < l; ++i) q[i] = dp[i];
    ntt(p, s << 1, 1), ntt(q, s << 1, 1);
    for (int i = 0; i < s << 1; ++i) q[i] = 1ll * p[i] * q[i] % P;
    ntt(q, s << 1, -1);
    for (int i = mid + 1; i <= r; ++i) g[i] = (g[i] + 2ll * q[i - l]) % P;
    if (l != 0) goto flag;
    for (int i = 0; i < s << 1; ++i) q[i] = 1ll * p[i] * p[i] % P;
    ntt(q, s << 1, -1);
    for (int i = mid + 1; i <= r; ++i) g[i] = (g[i] + q[i]) % P;
    flag: ;
    for (int i = 0; i < s << 1; ++i) p[i] = q[i] = 0;
    for (int i = 0; i < s >> 1; ++i) p[i] = g[i + l];
    for (int i = 1; i < s; ++i) q[i] = finv[i - 1] * a[i - 1];
    ntt(p, s << 1, 1), ntt(q, s << 1, 1);
    for (int i = 0; i < s << 1; ++i) q[i] = 1ll * p[i] * q[i] % P;
    ntt(q, s << 1, -1);
    for (int i = mid + 1; i <= r; ++i) dp[i] = (dp[i] + q[i - l]) % P;
    solve(s >> 1, mid + 1, r);
}

int main()
{
    cin >> n;
    scanf("%s", str);
    for (int i = 0; i < n; ++i) a[i] = str[i] - '0';
    s = 1; while (s <= n) s <<= 1;
    fac[0] = finv[0] = 1;
    for (int i = 1; i < s; ++i)
        fac[i] = 1ll * fac[i - 1] * i % P, finv[i] = power(fac[i], P - 2);
    inv[1] = 1;
    for (int i = 2; i < s; ++i)
        inv[i] = 1ll * inv[P % i] * (P - P / i) % P;
    dp[1] = 1;
    solve(s, 0, s - 1);
    for (int i = 1; i <= n; ++i)
        printf("%lld\n", 1ll * dp[i] * fac[i] % P);
    return 0;
}