yukicoder 550: 夏休みの思い出(1)

https://yukicoder.me/problems/no/550

解法

x3+ax2+bx+c=0 を解く前に x3+ax2+bx+c≡0 (mod 33331) で解く。これは全探索で解くことができ、解の個数が 3 個以下であることが保証されている。

得られた解を α,β,γ とすると、元の方程式の解は α+33331k,β+33331k,γ+33331k の形で表せる。解の範囲が分かっているため、こちらも全探索できる。

#include <iostream>
#include <set>

int main() {
    long long a, b, c;
    std::cin >> a >> b >> c;

    constexpr int MOD = 33331;
    std::set<long long> ans;
    for (__int128 i = 0; i < MOD; i++) {
        if ((i*i*i + a*i*i + b*i + c) % MOD == 0) {
            for (__int128 j = i - MOD*MOD; j <= MOD*MOD; j += MOD) {
                if (j*j*j + a*j*j + b*j + c == 0) ans.insert(j);
            }
        }
    }

    for (long long x : ans) {
        std::cout << x << ' ';
    }
}

python3 (153 bytes)

a,b,c=map(int,input().split())
P=33331
f=lambda x:(x+a)*x*x+x*b+c
print(*sorted(j for i in range(P) if f(i)%P==0 for j in range(i-P*P,P*P,P) if f(j)==0))

解の範囲が狭いことが分かっていれば、より高次の方程式に対しても同じ方法が適用できる。

Codeforces #425 (Div.2) E. Vasya and Shifts

http://codeforces.com/contest/832/problem/E

問題概要

  • 文字列 s1,s2,...,sn がそれぞれ 4 つずつ――全部で4n個――与えられる
  • 使われている文字はabcdeの5種類で、文字列長はすべて m
  • 4n個の文字列の中からいくつか選び、その総和が b になるようなパターン数を求めるクエリが飛んでくる
  • 文字列の和は'a'=0,...,'e'=4として (s+t)[i]=(s[i]+t[i])%5で定義する
  • si を複数回使うとき、使う順序は区別しない。

解法

文字列で考える必要なまったくなくて、単に GF(5) 上の m 次元ベクトルと考えればいい。この問題は

\begin{equation}
\mathbf{b} = c_1 \mathbf{s}_1 + c_2 \mathbf{s}_2 + \cdots +c_n \mathbf{s}_n
\end{equation}

を満たすような \( (c_1,c_2,\ldots,c_n) \) が何通りあるか、という問題に還元できる。これは連立方程式であるから、線形代数の理論を用いると良い。係数行列を A とする。解が存在するならば \(5^{n-\mathrm{rank}A}\) 通り存在する。

したがって、連立方程式が解を持つかどうかを判定できれば良い。\(b\) が与えられるたびに掃き出し法を行うのでは遅いため、\( (A\,\mathbf{b_1}\,\mathbf{b_2}\,\cdots\,\mathbf{b_q}) \)という拡大係数行列を構築しまとめて掃き出し法を行う。

掃き出し法はまあ良いと思うんだけど、解の個数があまり自明ではないので証明のアイディアをつらつらと書いておく。

  • 連立方程式\(Ac=b\) が解 \(Ac'=b\) を持ってるなら、\(A(c-c')=0\) と変形できる
  • 上のように変形できるのであれば、解の個数は連立方程式\(Ax=0\) の解の個数と等しいはず
  • \(Ax=0\)となるような\(x\)全体を行列の\(A\)のカーネルと呼ぶ
  • 解の個数は \( |\mathrm{Ker}A| \) と表せる
  • \( \mathrm{Ker} A \) は線形空間である
  • 次元定理により \( \mathrm{rank}A+\mathrm{dim}\mathrm{Ker} A = \mathrm{dim}V \)――ここで A は V→W の線形写像
  • \(m\) 次元の線形空間は \(m\) 個の基底が存在し、すべての元は \( \lambda_1 u_1 + \lambda_2 u_2 + \cdots + \lambda_m u_m \) の形で一意に定まる
  • \(\mathbb{F}_5\)上の\(m\)次元の線形空間の要素数は \(5^m\) である
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

constexpr int MOD = 5;

struct modint {
    int n;
    modint(int n = 0) : n(n) {}
};

std::string input() {
    static char buf[1000];
    scanf("%s", buf);
    return std::string(buf);
}

modint inv[5];

modint operator+(modint a, modint b) { return modint((a.n += b.n) >= MOD ? a.n - MOD : a.n); }
modint operator-(modint a, modint b) { return modint((a.n -= b.n) < 0 ? a.n + MOD : a.n); }
modint operator*(modint a, modint b) { return modint(1LL * a.n * b.n % MOD); }
modint operator/(modint a, modint b) { return a * inv[b.n]; }
modint &operator+=(modint &a, modint b) { return a = a + b; }
modint &operator-=(modint &a, modint b) { return a = a - b; }
modint &operator*=(modint &a, modint b) { return a = a * b; }
modint &operator/=(modint &a, modint b) { return a = a / b; }

int main() {
    inv[1] = 1;
    for (int i = 2; i < MOD; i++) {
        inv[i] = inv[MOD % i] * (MOD - MOD / i);
    }

    int n, m;
    std::cin >> n >> m;

    static modint a[500][800];

    for (int i = 0; i < n; i++) {
        std::string s = input();
        for (int j = 0; j < m; j++) {
            a[j][i] = s[j] - 'a';
        }
    }
    int q;
    std::cin >> q;
    for (int i = 0; i < q; i++) {
        std::string s = input();
        for (int j = 0; j < m; j++) {
            a[j][i + n] = s[j] - 'a';
        }
    }

    const int h = m;
    const int w = n + q;
    int r = 0;
    for (int j = 0; j < n && r < h; j++) {
        int p = r;
        for (int i = r; i < h; i++) {
            if (a[i][j].n != 0) {
                p = i;
                break;
            }
        }
        std::swap(a[p], a[r]);
        if (a[r][j].n == 0) continue;
        for (int jj = j + 1; jj < w; jj++) {
            a[r][jj] /= a[r][j];
        }
        a[r][j] = 1;
        for (int ii = r + 1; ii < h; ii++) {
            for (int jj = j + 1; jj < w; jj++) {
                a[ii][jj].n += 25 - a[ii][j].n * a[r][jj].n;
                a[ii][jj].n %= MOD;
            }
            a[ii][j] = 0;
        }
        r++;
    }

    constexpr long long MOD2 = 1e9 + 7;
    long long pw = 1;
    for (int i = 0; i < n - r; i++) {
        pw *= 5;
        pw %= MOD2;
    }

    for (int j = 0; j < q; j++) {
        long long ans = pw;
        for (int i = r; i < m; i++) {
            if (a[i][j + n].n != 0) {
                ans = 0;
            }
        }
        printf("%d\n", (int)ans);
    }
}

187ms。

Educational Codeforces Round 25: F. String Compression

http://codeforces.com/contest/825/problem/F

解法

文字列の最小周期はKMP法のテーブルを用いて計算できる。kmp[i]は文字列 S の先頭 i 文字を切り出した文字列の prefix と suffix の最大共通部分である。たとえば aabaabaab という文字列ならば 6 である。

aabaabaab
******
   ******

もし文字列に周期があるならば、i-kmp[i]が最小の周期になる。これはよく考えると分かるだろう。逆に文字列に周期がないならば、iはi-kmp[i]の倍数にはならない。

KMPテーブルの計算はO(n)でできるため、全体でO(n^2)で解くことができた。

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int main() {
    std::string s;
    std::cin >> s;

    const int n = s.size();

    std::vector<int> len(n + 1);
    for (int i = 1; i <= n; i++) {
        len[i] = len[i / 10] + 1;
    }

    std::vector<int> dp(n + 1, 1e9);
    std::vector<int> kmp(n + 1);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        kmp[i] = -1;
        int u = -1;
        for (int j = i + 1; j <= n; j++) {
            while (u != -1 && s[j - 1] != s[i + u]) u = kmp[i + u];
            if (u == -1) {
                kmp[j] = u = 0;
            } else {
                kmp[j] = ++u;
            }
            int period = (j - i) - kmp[j];
            if ((j - i) % period != 0) {
                period = j - i;
            }
            dp[j] = std::min(dp[j], dp[i] + len[(j - i) / period] + period);
        }
    }

    std::cout << dp[n] << std::endl;
}

最小周期が求められることの証明

周期が存在しないときは自明である。周期が存在するとき正しく求められるのかを考察する。

周期が存在するとき、たとえば以下のような対が考えられる。

f:id:pekempey:20170718002559p:plain:w500

文字列の長さを \(N\)、最小周期を \(T\)、kmpの値を \(K\) としたとき \(K>=N-T\) は自明に成り立つ。しかし \(K \gt N - T\) となってしまうと周期が正しく取れなくなってしまう。実はそうはならないことを示せば良い。

f:id:pekempey:20170718002928p:plain:w500

もし \(N-T\)よりも \(K\) が大きくなったとする。等しいノード同士を結ぶと以下のようになる。よく見るとすべてのノードが連結である。何故連結になるのかを示す。

f:id:pekempey:20170718003011p:plain:w500

重要な考察として、最小周期は素数である。\(N-K \lt T\) なので \(N-K\) は \(T\) の倍数ではありえない。つまり \(N-K\) と \(T\) は互いに素である。

f:id:pekempey:20170718003143p:plain:w500

互いに素なので、整数論のよくある定理(拡張ユークリッド互除法とかで見るやつ)により任意の地点に到達できる。よってすべての値が等しいということになる。しかしこれは矛盾、つまり仮定が誤っている。

Educational Codeforces Round 25: G. Tree Queries

http://codeforces.com/contest/825/problem/G

解法

f:id:pekempey:20170717205714p:plain

一番最初の黒頂点を根 r として考える。黒頂点に囲まれている部分を black-tree と呼ぶことにする。

タイプ1
u-r パスを black-tree に併合すればいい。事前に r-u パス上の最小頂点を求めておくことで O(1) で併合と同等の操作が行える。

タイプ2
white-path と black-tree の最小値を求めれば良い。white-path を厳密に求める必要はなく、r-u パス上の最小頂点のみを求めれば良い。これも O(1) でできる。

#include <iostream>
#include <algorithm>
#include <vector>

int input() {
    int n;
    scanf("%d", &n);
    return n;
}

int main() {
    int n, q;
    std::cin >> n >> q;

    std::vector<std::vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int u = input() - 1;
        int v = input() - 1;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    input();
    int root = input() % n;
    q--;

    std::vector<int> white_path(n, -1);
    std::vector<int> stack;
    white_path[root] = root;

    stack.push_back(root);
    while (!stack.empty()) {
        const int u = stack.back();
        stack.pop_back();
        white_path[u] = std::min(u, white_path[u]);

        for (int v : g[u]) {
            if (white_path[v] == -1) {
                white_path[v] = white_path[u];
                stack.push_back(v);
            }
        }
    }

    int ans = 0;
    int black_min = 1e9;
    while (q--) {
        int t = input();
        int x = (input() + ans) % n;

        if (t == 1) {
            black_min = std::min(black_min, white_path[x]);
        } else {
            ans = std::min(white_path[x], black_min) + 1;
            printf("%d\n", ans);
        }
    }
}

prime counting function

以下の問題を解く際に「n 以下の素数の個数」を高速に求める必要が出てくる。

http://codeforces.com/contest/665/problem/F

素数列を\(p_0,p_1,\ldots\)とする。

\(\phi(x,p_i)\)を\(x\)以下の正整数のうち\(p_0,p_1,\ldots,p_i\)を約数に持たないものの個数と定義する。このとき以下の漸化式が成り立つ。

\[ \phi(x,p_i)=\phi(x,p_{i-1})-\phi\left(\frac{x}{p_i},p_{i-1}\right) \]

さらに\(\pi(x,p_i)=\phi(x,p_i)+i+1\)と定義する。\(x \le p_i^2\)のとき\(\pi(x,p_i)=\pi(x)\)になることは試し割りの素数判定の原理を考えれば容易にわかる。2,3,5,7,...で割り切れない正整数の個数を数えているのであまり良く考えないと 1 を素数に含めてしまうので注意

これを最初の漸化式に当てはめると以下の漸化式が導ける。

\[ \pi(x,p_i)=\pi(x,p_{i-1})-\pi\left(\frac{x}{p_i},p_{i-1}\right)+i+1 \]

\( \pi(x,p_i) \) のテーブルを更新するとき、\( \pi(1..p_i^2-1,p_i) \) の値は変わらないことを使うと、DPテーブルの更新は大幅に高速化できる。

この手法を使うとpi(N/i)側が求められるという利点がある。1000000以下の素数で計算しても1sec程度である。

#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;

const long long N = 5e5;
bool tab[N + 1];
long long pi[N + 1];
long long hi[N + 1];
vector<long long> primes;

int main() {
	long long n;
	cin >> n;
	// 1 is prime !!
	for (int i = 1; i <= N; i++) {
		pi[i] = i;
		hi[i] = n / i;
		tab[i] = true;
	}
	for (int i = 2; i <= N; i++) {
		if (tab[i]) {
			primes.push_back(i);
			for (int j = i * 2; j <= N; j += i) {
				tab[j] = false;
			}
		}
	}
	for (int i = 0; i < primes.size(); i++) {
		long long p = primes[i];
		// n/j>=p*p
		// j<=n/(p*p)
		for (int j = 1; j <= min(N, n / (p * p)); j++) {
			long long k = n / j / p;
			hi[j] -= (k <= N ? pi[k] : hi[j * p]) - (i + 1);
		}
		for (int j = N; j >= p * p; j--) {
			pi[j] -= pi[j / p] - (i + 1);
		}
	}
	long long ans = 0;
	for (long long p : primes) {
		if (p * p * p <= n) {
			ans++;
		}
		ans += max(0LL, hi[p] - pi[p]);
	}
	cout << ans << endl;
}