読者です 読者をやめる 読者になる 読者になる

math314のブログ

主に競技プログラミング,CTFの結果を載せます

Størmerの定理

前書き

$2^{n} - 3^{k} = 1$ を満たす正の整数 $(n,k)$ をすべて求めなさい。

いきなりですが、上記の問題が解けるでしょうか?

まず小さい数を代入していくと、$(n,k) = (2,1)$ の時は $2^{2} - 3^{1} = 1$ となってこれを満たすことがわかります。 それ以外の解は見つかるでしょうか? 何となく無さそうですが確証は持てないですね…

こういう問題は 指数型の不定方程式 とか呼ばれているそうです。受験で出てきそうな見た目をしていますが、この問題は凶悪なのか解法は見たことがないです。 この問題、解きたいですよね?

今回は Størmerの定理(Stormerの定理) と呼ばれている定理を用いて、$2^{n} - 3^{k} = 1$ を満たす正の整数  (n,k) は $(n,k) = (2,1)$ のみであることを証明します。

今回の証明は http://kam.mff.cuni.cz/~klazar/stormer.pdf を要約したものとなっています。

続きを読む

Windowsで、実行ファイルを書き換えずに既存の.Netアプリケーションのメソッドを置き換える話

動機

昔、箱庭XSSという問題がSECCONで出題されました。 どのような問題だったかは他の方のブログを見て頂ければ分かるかと思います。

nash.hatenablog.com

問題作者のスライドはこちらです。

【XSS Bonsai】 受賞のご挨拶 by @ymzkei5 【SECCON 2014】 - Dec 08, 2014

このアプリケーションは.Net製で、

  • 難読化
  • 既存のdecompilerでは C#, VB.Netのコードに変換出来ない(大体落ちたり例外が発生する)
  • デバッガでattachすると挙動が変わったり、答えが変わる
  • バイナリを書き換えると、checksum一致処理に引っかかる

という特性があります。

webの問題として解いてほしいらしく、作者さんのスライド曰く

f:id:math314:20170122002615p:plain

とのことなので、チートで解こうと考えました。

今回要求される要件は

  • debugger検知に引っかからない
  • 実行ファイルを書き換えない
    • checksumが変わるため

の二つです。

disassembleしてみると、「正規表現で文字列を置換している処理さえ潰せればフラグを取れるのでは?」と思ったので、「Regex.Replaceの挙動を変更する」ことを目標にしました。

しかし箱庭XSSのみに特化したプログラムを書いても面白くないので、もうちょっと大きく出て「.Netアプリケーションのメソッドを、実行ファイルを書き換えずに挙動を変える」ということにしましょう。

(なおこれ以降箱庭XSSは出てきません、手段と目的は往々にして入れ替わります)

実装

github.com

に置いてあるのでご自由にどうぞ。(英語でコメント書こうとして挫折した後がありますね) とりあえず試してみたい人は https://github.com/math314/DotNetInjection/releases/tag/v1.0 から Release.zip をダウンロードして試してみてください。動かし方はreadmeに書いてあります。

続きを読む

Parindromic Tree

競プロ忘年会 in 東京 2016 で発表したpalindromic tree(eertree, 回文木) についてのスライドとコードを載せておきます。

www.slideshare.net

gist.github.com

ARC059 : F - バイナリハック / Unhappy Hacking

追記3:

yosupoが最新版の解説を書いたようです。こちらを見ましょう。

yosupo.hatenablog.com

以下は旧記事です。

AtCoder Regular Contest 059 で出題された F - バイナリハック / Unhappy Hacking の O(n)解法です。

解説はコードに埋め込みました。 カタラン数云々は http://www.mtholyoke.edu/~jjlee/Teaching/Intro_to_Catalan.pdf を見て下さい。

atcoderの提出はこちら Submission #839457 - AtCoder Regular Contest 059 | AtCoder

追記:

今回使ったA126087 - OEISにある漸化式ですが、 Conjectureだそうです。一応 n <= 3000まで正しい事は確認しましたが、気になる方がいるようなので追記します。

追記2: magicを使わなくても解けたようです。

Submission #839587 - AtCoder Regular Contest 059 | AtCoder

解説

以下は旧コード

#include <bits/stdc++.h>

using namespace std;
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)c.size())
#define ten(n) ((int)1e##n)
using ll = long long;

const int MOD = ten(9) + 7;
const int N = ten(4);

// O(N)
ll inverse[N];
void init_inverse() {
    inverse[1] = 1;
    for (int i = 2; i < N; i++) inverse[i] = (MOD - MOD / i) * inverse[MOD%i] % MOD;
}

// O(N)
ll fact[N], infact[N];
void init_fast_fact() {
    init_inverse();
    fact[0] = fact[1] = 1;
    for (int i = 2; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
    infact[0] = infact[1] = 1;
    for (int i = 2; i < N; i++) infact[i] = infact[i - 1] * inverse[i] % MOD;
}

// O(1)
ll fast_nCk(int n, int k) {
    if (n < 0 || k < 0) return 0;
    if (k > n) return 0;
    ll ret = fact[n] * infact[k] % MOD * infact[n - k] % MOD;
    return ret;
}

//O(1)
ll pseudo_catalan(int a, int b, int c) {
    if (c == a - 1) b--, c--;
    if (c == b - 1) a--, c--;
    ll ret = fast_nCk(a + b - 2, a - 1) - fast_nCk(a + b - 2, c - 1);
    if (ret < 0) ret += MOD;
    return ret;
}

int solve(int n, int m) {
    // O(n) にできるが、今回は十分に大きい定数回回している
    init_fast_fact();

    // https://oeis.org/A126087
    // magic[i] = i回タイプした時、文字列が空になるようなキーの押し方の個数
    // O(n)
    vector<ll> magic = { 1, 1, 3 };
    for (int i = 3; i <= n; i++) {
        ll tmp = 3 * (i + 1) * magic[i - 1] + 8 * (i - 2) * magic[i - 2] - 24 * (i - 2) * magic[i - 3];
        magic.push_back(tmp % MOD * inverse[i + 1] % MOD);
        if (magic[i] < 0) magic[i] += MOD;
    }

    // 2の累乗
    // O(n)
    vector<ll> power_of_2;
    power_of_2.push_back(1);
    FOR(i, n) power_of_2.push_back(power_of_2.back() * 2 % MOD);

    ll ans = 0;
    FOR(s, n) {
        // ループ内はO(1)
        //
        // |------|X|-------|
        // <------>^<------->
        //    |    |    |
        //    s    | rem - 1
        //         s回目(0-indexed)
        //
        // 前半s回のタイプ後、文字列の長さが0
        // s+1回目、最初の文字を打つ
        // 後半、s+2回目以降は、文字列が空にならないよう注意しながらタイピング
        // こうすると重複せず数え上げられる
        //
        // 前半はmagicに係数が入っているので、後半のs+2回目以降のタイプの仕方について数え上げればよい

        const int rem = n - s; //後 rem 回タイプ出来る
        if (rem < m) continue;
        if ((rem - m) % 2 != 0) continue;

        const int B = (rem - m) / 2; // s+2回目以降のバックスペースの回数
        const int A = rem - B; // s+2回目以降タイプする文字列 (= {0,1}をタイプする回数)

        const ll a1 = B == 0 ? 1 : pseudo_catalan(A , B + 1, B); //カタラン数の計算方法と同じやつ
        // バックスペースで消される文字列は{0,1}のどっちでもいいので、 2^B  を掛ける
        const ll s_ans = a1 * power_of_2[B] % MOD * magic[s] % MOD;
        ans += s_ans;
    }

    return int(ans % MOD);
}

int main() {
    int n; cin >> n;
    string s; cin >> s;
    int m = sz(s);
    int ans = solve(n, m);
    cout << ans << endl;

    return 0;
}

n以下の素数のsumを高速に計算する

目次

  • 動機
  • 問題概要
  • 準備
  • 計算量
    • \(1 \le p_b \le n^{1/4} \) の時
    • \(n^{1/4} \le p_b \le n^{1/2} \) の時
  • 素直なプログラム
  • 最適化したプログラム
  • 余談

動機

Project Euler で、n以下の素数の合計を求める問題がありました。 Problem 10 - Project Euler

この問題は2*106以下の素数の合計を求めるだけなので簡単なのですが、Lucy_Hedgehog さんという方が面白いアルゴリズムをpostしていました。

せっかくなので、なるべく初心者にも分かりやすいようにアルゴリズムの概要を説明したいと思います。 アルゴリズムとか計算量とかどうでもいい人は、

optimized_prime_sum.cpp · GitHub

のプログラムをコピペして使って下さい。

問題概要

競技プログラミングで以下のような問題が出た場合、どう実装すればいいでしょう?

\(n\)以下の素数の合計を出力して下さい。ただし、n <= 106

エラトステネスの篩を使えばn以下の素数の列挙は \( O(n \log\log (n)) \) で出来るので、このアルゴリズムで十分だと思います。

では次の制約の場合はどうでしょうか。

\(n\)以下の素数の合計を出力して下さい。ただし、n <= 1012

答えは 64bitに収まらないので、109 + 7で割った値を答えて下さい。

アトキンの篩を使えば 計算 \( O(n / \log\log(n)) \) , 空間 \( O(n^{1 / 2}) \) で計算出来る(らしい)ので、これで十分かも知れません。 が、今回は計算 \( O(n^{3/4}) \), 空間\( O(n^{1 / 2}) \) で計算出来る方法を紹介したいと思います。

続きを読む

ISUCON5 オンライン予選 通過しました

優勝賞金100万円!今年もやります ISUCON5 開催と日程のお知らせ #isucon : ISUCON公式Blog

「お題となるWebサービスを決められたレギュレーションの中で限界まで高速化を図るチューニングバトル、それがISUCONです。過去の実績も所属している会社も全く関係ない、結果が全てのガチンコバトルです。」(公式説明)であるISUCON5のオンライン予選に参加してきました。

...

ISUCONは Iikanjini Speed Up Contest の略で、Webアプリケーションがデプロイされたイメージを渡されて、その上で何をしてもいいからとにかくパフォーマンスを上げることが競技内容です。

ISUCON5オンライン予選に参加してきた « chibiegg日誌

ということで参加してきました。

チーム マウント竹田氏(メンバー: @misodengaku, @chibiegg, @__math) で出ていました. 16位で予選通過です。 いつもは @aki33524 も参加するんですが、上限が3人までということだったので、裏番組のTrend Micro CTFを頑張ってもらいました…、きひろくんごめん。

他のメンバーの参加記です

初参加でしたが決勝に進出出来てよかったです。

続きを読む

任意modでの畳み込み演算をO(n log(n))で

http://misawa.github.io/other/fast_kitamasa_method.html を見て刺激されたので書いた.

  1. 畳み込み演算?
  2. 任意modでの畳み込み演算
  3. 中で使われてる技術達
  4. c++のコード

コードと原理の説明をちょっとだけ載せています.

コードだけ欲しい人は https://gist.github.com/math314/6a08301b8b75b8172798 をどうぞ. fast_int32mod_convolution を使うとint32の任意のmodが取れます.

実はまだverifyしてない.

続きを読む