Visits: 2045

AtCoder Grand Contest 047

Integer Product

考虑 $\times 10^9$ 之后质因子中 $2,5$ 的次数，卡精度。

const int M = 57, inf = 1e9;
int n, c[M][M];
ll ans;

int main() {
    ios::sync_with_stdio(0);
    rd(n);
    for (int i = 1; i <= n; i++) {
        string s;
        rds(s);
        int p = -1;
        for (ui j = 0; j < s.size(); j++)
            if (s[j] == '.') p = j;
        if (!~p) p = s.size(), s += ".0";
        while ((int)s.size() - p < 10) s += "0";
        ll a = 0;
        for (ui j = 0; j < s.size(); j++)
            if (s[j] != '.') a = a * 10 + s[j] - '0';
        int c2 = 0, c5 = 0;
        while (a % 2 == 0) ++c2, a /= 2;
        while (a % 5 == 0) ++c5, a /= 5;
        c[c2][c5]++;
    }
    for (int i = 0; i < M; i++)
        for (int j = 0; j < M; j++) {
            if (i >= 9 && j >= 9) ans += 1ll * c[i][j] * (c[i][j] - 1);
            for (int x = 0; x < M; x++)
                for (int y = 0; y < M; y++)
                    if (i + x >= 18 && j + y >= 18 && (i != x || j != y))
                        ans += 1ll * c[i][j] * c[x][y];
        }
    print(ans / 2);
    return 0;
}

First Second

所有字符串能生成的新字符串只有 $\mathcal O(|\Sigma|\sum_{i=1}^n |s_i|)$，Hash 判即可。

const int P[2] = {998244353, 998244853}, H = 19491001;
struct Hash {
    int a[2];
    inline Hash() {}
    inline Hash(int x) {
        a[0] = a[1] = x;
    }
    inline Hash(int x, int y) {
        a[0] = x, a[1] = y;
    }
    inline friend bool operator == (Hash x, Hash y) {
        for (int i = 0; i < 2; i++)
            if (x.a[i] != y.a[i]) return 0;
        return 1;
    }
    inline friend Hash operator + (Hash x, Hash y) {
        for (int i = 0; i < 2; i++)
            x.a[i] = (x.a[i] + y.a[i]) % P[i];
        return x;
    }
    inline friend Hash operator - (Hash x, Hash y) {
        for (int i = 0; i < 2; i++)
            x.a[i] = (x.a[i] - y.a[i] + P[i]) % P[i];
        return x;
    }
    inline friend Hash operator * (Hash x, Hash y) {
        for (int i = 0; i < 2; i++)
            x.a[i] = 1ll * x.a[i] * y.a[i] % P[i];
        return x;
    }
    inline ll h() {
        return ((ll)1e9 * a[1] + a[0]) % H;
    }
};

const Hash B = Hash(131, 13331);

const int N = 2e5 + 7;
int n, m;
string s[N];
vector<Hash> h[N];

int hh[H], he[N], hc[N], ht[N], tot;

inline void add(int x, int y, int z) {
    for (int i = hh[x]; i; i = ht[i])
        if (he[i] == y) return hc[i] += z, void();
    he[++tot] = y, hc[tot] = z, ht[tot] = hh[x], hh[x] = tot;
}

inline int ask(int x, int y) {
    for (int i = hh[x]; i; i = ht[i])
        if (he[i] == y) return hc[i];
    return 0;
}

ll ans;

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) {
        rds(s[i]), reverse(s[i].begin(), s[i].end());
        h[i].resize(s[i].size());
        h[i][0] = s[i][0];
        for (ui j = 1; j < s[i].size(); j++)
            h[i][j] = h[i][j-1] * B + s[i][j];
        add(h[i][s[i].size()-1].h(), h[i][s[i].size()-1].a[0], 1);
    }
    for (int i = 1; i <= n; i++) {
        static bool v[26];
        memset(v, 0, sizeof(v));
        for (int j = s[i].size() - 1; ~j; j--) {
            v[s[i][j]-'a'] = 1;
            if (j != (int)s[i].size() - 1) {
                Hash o = j ? h[i][j-1] : 0;
                for (int k = 0; k < 26; k++)
                    if (v[k]) {
                        Hash w = o * B + (k + 'a');
                        ans += ask(w.h(), w.a[0]);
                    }
            }
        }
    }
    print(ans);
    return 0;
}

Product Modulo

考虑找到 $P$ 的一个原根 $p$，将除了 $0$ 之外的每个数转化成 $2^k \bmod P$ 的形式，那么乘法取模就相当于指数上的循环卷积，FFT 实现，时间复杂度 $\mathcal O(P \log P)$。

取 $p=2$ 即可。

const int P = 2e5 + 3;
int n, c[P], p[P];
ll d[P], ans;

namespace FFT {
    const int N = 1 << 21 | 1;
    const ld PI = acos(-1);
    struct I {
        ld x, y;
        inline I() {}
        inline I(ld x, ld y) : x(x), y(y) {}
        inline I &operator = (int o) { return x = o, y = 0, *this; }
        inline I operator + (const I o) const { return I(x + o.x, y + o.y); }
        inline I operator - (const I o) const { return I(x - o.x, y - o.y); }
        inline I operator * (const I o) const {
            return I(x * o.x - y * o.y, x * o.y + y * o.x);
        }
    } a[N], b[N];
    int n, m, k, l, r[N];
    inline void fft(I *a, int n, int x) {
        for (int i = 0; i < n; i++) if (i < r[i]) swap(a[i], a[r[i]]);
        for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1) {
            I W = I(cos(PI / k), x * sin(PI / k));
            for (int i = 0; i < n; i += o) {
                I w = I(1, 0);
                for (int j = 0; j < k; j++, w = w * W) {
                    I x = a[i+j], y = w * a[i+j+k];
                    a[i+j] = x + y, a[i+j+k] = x - y;
                }
            }
        }
    }
    inline void solve() {
        k = 1, l = 0;
        while (k <= n + m) k <<= 1, ++l;
        for (int i = 0; i < k; i++)
            r[i] = (r[i>>1] >> 1) | ((i & 1) << (l - 1));
        for (int i = n + 1; i < k; i++) a[i] = 0;
        for (int i = m + 1; i < k; i++) b[i] = 0;
        fft(a, k, 1), fft(b, k, 1);
        for (int i = 0; i < k; i++) a[i] = a[i] * b[i];
        fft(a, k, -1);
        for (int i = 0; i <= n + m; i++) a[i].x /= k;
    }
}

int main() {
    rd(n);
    for (int i = 1, x; i <= n; i++) {
        rd(x);
        if (x) ++c[x];
    }
    FFT::n = FFT::m = P - 2;
    for (int i = 0; i <= P - 2; i++) {
        p[i] = i ? 2 * p[i-1] % P : 1;
        FFT::a[i] = FFT::b[i] = c[p[i]];
        d[2*i%(P-1)] -= c[p[i]];
    }
    FFT::solve();
    for (int i = 0; i <= 2 * P - 4; i++)
        d[i%(P-1)] += (ll)(FFT::a[i].x + 0.5);
    for (int i = 0; i <= P - 2; i++) ans += d[i] * p[i];
    print(ans / 2);
    return 0;
}

Twin Binary Trees

设第一棵树上的两个叶子为 $u,v$，其 LCA 为 $w$。

枚举 $w$。

枚举 $u$，设其对应的第二棵树上的叶子为 $p_u$，枚举 $p_u$ 的祖先 $x$，将 $w \to x$ 的贡献加到 $x$ 上。

枚举 $v$，设其对应的第二棵树上的叶子为 $p_v$，枚举 $p_v$ 的祖先 $y$，计算 $p_u,p_v$ 的 LCA 为 $y$ 时的贡献。

时间复杂度 $\mathcal O(n \log^2 n)$。

const int N = 1 << 18 | 1;
int n, l, r, a[N];
modint f[N], ans;

void dfs1(int p, modint w) {
    w *= p;
    if (p >= l) {
        p = a[p];
        while (p) w *= p, f[p] += w, p >>= 1;
        return;
    }
    dfs1(ls, w), dfs1(rs, w);
}

void dfs2(int p, modint w) {
    w *= p;
    if (p >= l) {
        p = a[p];
        while (p != 1) w *= p, ans += w * f[p^1] * (p >> 1), p >>= 1;
        return;
    }
    dfs2(ls, w), dfs2(rs, w);
}

void dfs3(int p) {
    if (p >= l) {
        p = a[p];
        while (p) f[p] = 0, p >>= 1;
        return;
    }
    dfs3(ls), dfs3(rs);
}

int main() {
    rd(n), l = 1 << (n - 1), r = 1 << n;
    for (int i = l; i < r; i++) rd(a[i]), a[i] += l - 1;
    for (int p = 1; p < l; p++) dfs1(ls, p), dfs2(rs, 1), dfs3(ls);
    print(ans);
    return 0;
}

Product Simulation

先把 $A,B$ 的二进制数搞出来，然后一位一位的乘再加起来即可，具体构造方式见代码。

#define p(x, a, b, c) printc(x), printc(' '), print(a, b, c)

int main() {
    print(3870);
    p('+', 0, 1, 3);
    p('<', 2, 3, 3);
    for (int x = 0; x < 2; x++) {
        p('+', 3, x, x);
        int y = x + 4;
        for (int i = 0; i < 30; i++) {
            if (i > 0) p('+', y, y, y);
            p('+', y, 3, 6);
            for (int j = i; j < 29; j++) p('+', 6, 6, 6);
            int z = i + 7 + x * 30;
            p('<', 6, x, z);
            p('+', y, z, y);
        }
    }
    for (int t = 0; t < 59; t++) {
        if (t > 0) p('+', 2, 2, 2);
        for (int i = max(t - 29, 0); i <= min(t, 29); i++) {
            int j = t - i;
            p('+', i + 7, j + 37, 4);
            p('<', 3, 4, 4);
            p('+', 2, 4, 2);
        }
    }
    return 0;
}

Rooks

咕。