luogu P2000 拯救世界

嘟嘟嘟

题目有点坑，要你求的多少大阵指的是召唤kkk的大阵数 * lzn的大阵数，不是相加。

看到这个限制条件，显然要用生成函数推一推。

比如第一个条件“金神石的块数必须是6的倍数”，就是\(1 +x ^ 6 + x ^ {12} + \ldots\)，也就是\(\frac{1 - x ^ {6n}}{1 - x ^ 6}\)。当\(x \in (-1, 1)\)时，就变成了\(\frac{1}{1 - x ^ 6}\)。

剩下的同理。

然后把这10个条件都乘起来，一顿化简，答案就是\(\frac{(n + 1) * (n + 2) * (n + 3) *(n + 4)}{24}\)。

本来想快乐的写高精，但是\(n = 1e5\)还非得用fft。

于是就写了一发，不开O2会TLE飞，开了后TLE最后一个点。然后把fft的预处理改成bin哥的写法后就过了。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define In inline

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-8;

const db PI = acos(-1);

const int maxn = 4e6 + 5;

inline ll read()

{

    ll ans = 0;

    char ch = getchar(), last = ' ';

    while(!isdigit(ch)) last = ch, ch = getchar();

    while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();

    if(last == '-') ans = -ans;

    return ans;

}

inline void write(ll x)

{

    if(x < 0) x = -x, putchar('-');

    if(x >= 10) write(x / 10);

    putchar(x % 10 + '0');

}

char a1[maxn];

int n, m, a[maxn], b[maxn];

int len = 1;

struct Comp

{

    db x, y;

    In Comp operator + (const Comp& oth)const

    {

        return (Comp){x + oth.x, y + oth.y};

    }

    In Comp operator - (const Comp& oth)const

    {

        return (Comp){x - oth.x, y - oth.y};

    }

    In Comp operator * (const Comp& oth)const

    {

        return (Comp){x * oth.x - y * oth.y, x * oth.y + y * oth.x};

    }

    friend In void swap(Comp& a, Comp& b)

    {

        swap(a.x, b.x); swap(a.y, b.y);

    }

}c[maxn], d[maxn], omg[maxn], inv[maxn];

int r[maxn];

In void init()

{

    omg[0] = inv[0] = (Comp){1, 0};

    omg[1] = inv[len - 1] = (Comp){cos(2 * PI / len), sin(2 * PI / len)};

    for(int i = 2; i < len; ++i) omg[i] = inv[len - i] = omg[i - 1] * omg[1];

}

In void fft(Comp* a, Comp* omg)

{

	for(int i = 0; i < len; ++i) if(i < r[i]) swap(a[i], a[r[i]]);

    for(int l = 2; l <= len; l <<= 1)

    {

        int q = l >> 1;

        for(Comp* p = a; p != a + len; p += l)

            for(int i = 0; i < q; ++i)

            {

                Comp tp = omg[len / l * i] * p[i + q];

                p[i + q] = p[i] - tp, p[i] = p[i] + tp;

            }

    }

}

In void mul(int* a, int* b)

{

    int tot = max(n, m); len = 1;

    while(len < (tot << 1)) len <<= 1;

	int lim = 0;

	while((1 << lim) < len) ++lim;

	for(int i = 0; i < len; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lim - 1));

    for(int i = 0; i < len; ++i) c[i] = d[i] = (Comp){0, 0};

    for(int i = 0; i < n; ++i) c[i] = (Comp){a[i], 0};

    for(int i = 0; i < m; ++i) d[i] = (Comp){b[i], 0};

    init();

    fft(c, omg), fft(d, omg);

    for(int i = 0; i < len; ++i) c[i] = c[i] * d[i];

    fft(c, inv);

    for(int i = 0; i <= len; ++i) a[i] = 0;

    for(int i = 0; i < len; ++i)

    {

        a[i] += (int)(c[i].x / len + 0.5);

        if(a[i] >= 10) a[i + 1] += a[i] / 10, a[i] %= 10;

    }

    n = len;

    while(n - 1 && !a[n - 1]) --n;

//	for(int i = n - 1; i >= 0; --i) printf("%d", a[i]); enter;

}

In void add(int* a, int x, int& n)

{

    a[0] += x;

    for(int i = 0; i < n; ++i)

        if(a[i] >= 10) a[i + 1] += a[i] / 10, a[i] %= 10;

        else break;

    ++n;

    while(n - 1 && !a[n - 1]) --n;

//	for(int i = n - 1; i >= 0; --i) printf("%d", a[i]); enter;

}

In void div(int* a, int x)

{

    static int ret[maxn];

    reverse(a, a + n);

    int tp = 0, cnt = 0;

    for(int i = 0; i < n; ++i)

    {

        tp = tp * 10 + a[i];

        ret[++cnt] = tp / x;

        tp %= x;

    }

    int sta = 1;

    while(sta < cnt && !ret[sta]) ++sta;

    for(int i = sta; i <= cnt; ++i) write(ret[i]); enter;

}

int main()

{

//	freopen("random.in", "r", stdin);

//	freopen("ac.out", "w", stdout);

    scanf("%s", a1);

    m = n = strlen(a1);

    for(int i = 0; i < n; ++i) b[i] = a[i] = a1[n - i - 1] - '0';

    add(a, 1, n); add(b, 1, m);

    for(int i = 2; i <= 4; ++i)

    {

        add(b, 1, m);

        mul(a, b);

    }

    div(a, 24);

    return 0;

}

巴特西

luogu P2000 拯救世界

最新文章

热门文章