Ecasdqina's MEMO

Ecasdqina's MEMO.

メモ帳.

数列について

らてひるど

ARC050-E LCM111(https://beta.atcoder.jp/contests/arc050/tasks/arc050_c)をやった時に次の数列の任意項を一般の法で求める方法が必要になったのでメモ程度に書いておきます.
a_{N + 1} = a_N \times 10 + 1

コード

このコードでは a_{N + 1} = a_N \times p + 1 の任意項を求めています.

int sequence(int p, int n, int mod){
    if(!n) return 0;
    if(n & 1) return sequence(p, n - 1, mod) * p + 1;
    return sequence(p, n / 2, mod) * (mod_pow(p, n / 2, mod) + 1) % mod;
}

CF | Round470 Div.2 - B. Primal Sport

問題

Problem - B - Codeforces

本文

これ難しすぎでしょ, Div.2 - Bに置く問題ではない.
とりあえずO(N\sqrt N)でしたい気持ちになるんだけど, これはTLEするのでちょっと頭のいいことをしないと通らない.

コード

Submission #36213580 - Codeforces

自作問題を2問作りました.

問題

増加列(Judge ver.)

Ecasdqina's page

難易度はABC-Dくらい(適当).

増加列(Contestant ver.)

Ecasdqina's page

難易度はAGC-Cくらい(適当).

おわりに

今後自作問題はここに置いておきます.

Ecasdqina's page