https://atcoder.jp/contests/arc084/tasks/arc084_d

問題概要

N個の非負整数Aiが黒板に書かれている。黒板に書いてある数に対して「数をひとつ選びそれを2倍したものを黒板に書き足す」「数をふたつ選びそれらのbitwise xorをとったものを黒板に書き足す」という操作を好きな順番で何度でも行えるとき、黒板に書かれうる数のうち大きさがX以下であるものが何種類存在するか求めよ。

1 <= N <= 6

1 <= X, Ai <= 2⁴⁰⁰⁰

解法

なぜそうするかはとりあえずおいといて、与えられた数の2進表記を多項式の係数とみなすことにする。 1111 は x³ + x² + x¹ + 1 となり、 101 は x² + 1 となる、いう具合である。このようにすると「ある数を2倍する操作」は「多項式にxをかける操作」とみなすことができるようになる。また「2つの数のxorをとる操作」は「多項式同士の足し算をする操作（ただし係数はmod2で考える）」になる。

ではこのような操作を繰り返していって作ることのできる多項式はどのようなものになるか？実はこれはGCDのような概念を考えることで解決することができる。どういうことかというと、「与えられたN個の多項式に上の操作を繰り返して作れる多項式の集合」を考えたとき、実はそれとまったく同じ集合を「ひとつの多項式だけが含まれる集合」から始めても作ることができる。その「ひとつの多項式」をここではGCDと呼んでいる。（普通の整数のGCDも、上の操作を「整数倍」と「足し算・引き算」に置き換えると同じような性質がある（あるよね？）（なかったらすいません））

GCDの求め方だが、互除法と同じ形でやれる。すなわち次数が大きい方の多項式をA, 次数の小さい方（同じでも良い）をBとして、最大次数が揃うまでBにxをかけてから足す。その結果をCとして再帰的に同じことをし続ける、という形である。これでGCDとなる多項式を求めることができる。

GCDとなる多項式Gが求まったら、あとはそれを使ってどんな数が作れるかを考えればよい。ここでGの最大次数をdとすると、実はd次より上の項はどんな組み合わせでも自由につくることができる。そして(d-1)次より下の項はそれに応じて自動的に一意に決まる。なぜなら x倍の操作でGを左にシフトしていくことはできるが右にシフトさせることはできないからである。もしd次以上の項の係数をフリップさせたいのであればGをそこまで左シフトさせてから足せばいいが、(d-1)次以下に対してはそれができないので自由にいじることはできない。

よって答えとしては、基本的にXのd次以上の項は全部自由に作れるので、そこの部分だけを切り取って2進数と見なした数は全部作ることができる。ただしひとつだけ例外があって、作った結果d次以上の全部の項がXと一致している場合、後ろの桁の結果によってはXをオーバーしている可能性がある。なのでそのケースだけは実際にGから構成してみてXを超えないか確かめる必要がある。もし超えていたらその数は作れないので除く。あとは0も数える対象であるのでそれを忘れず含めるようにする。

感想

わからんが、とにかく書いた

GCDが「集合の要素hoge倍する・または集合の要素同士を足し算（引き算）して集合に加えていく」という操作をするときの最小要素？的な感じになるというのはもっとちゃんと理解しておくべきことっぽい

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string;

immutable long MOD = 998244353;

int[] gcd(int[] a, int[] b) {
    while (true) {
        if (a.length < b.length) swap(a, b);
        if (b.length == 0) return a.dup;
        ulong msb = a.length;

        foreach (i; 0..a.length) {
            if (i < b.length) {
                a[i] ^= b[i];
            }
            if (a[i]) {
                msb = min(i, msb);
            }
        }

        a = a[msb..$];
    }
}

void main() {
    auto s = readln.split;
    auto N = s[0].to!int;
    auto X = s[1].map!(a => to!int(a == '1')).array;
    auto P = N.iota.map!(_ => readln.chomp.map!(a => to!int(a == '1')).array).array;

    auto G = P.front.dup;
    foreach (i; 1..N) G = gcd(G, P[i].dup);

    long ans = 0;

    for (long i = X.length.to!long - G.length.to!long, tmp = 1; i >= 0; i -= 1, tmp = tmp * 2 % MOD) {
        if (X[i]) {
            ans = (ans + tmp) % MOD;
        }
    }


    auto M = new int[](X.length);

    for (int i = 0; i + G.length <= M.length; ++i) {
        if (M[i] != X[i]) {
            for (int j = 0; j < G.length; ++j) {
                M[i+j] ^= G[j];
            }
        }
    }

    if (M <= X) {
        ans = (ans + 1)  % MOD;
    }

    ans.writeln;
}

nebukuro09の日記

AtCoder Regular Contest 084: F - XorShift

問題概要

解法

感想

コード (D言語)