けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

【ライブラリ】mod の値が大きいときの mod 演算

昨日の CSA 068 DIV2 E Sliding Product Sum で、まさかのときのために作っていたライブラリがドンピシャで役に立ちました!!!

「1000000007 で割った余りを答えよ」という問題は多いですが、「m が与えられて m で割った余りを答えよ」となると往々にして辛いですね。ましてや、m が int 型に収まらないとなると...


long long a = ?, b = ?
(a * b) % m


というなんでもない計算が long long 型オーバーフローしてしまいます。対策として、

a を b 回足しあげる、ただし繰り返し二乗法を流用する

というのがあります。a + a が long long 型オーバーフローしない限りは大丈夫です。

inline long long mod(long long a, long long m) {
    return (a % m + m) % m;
}
inline long long mul(long long a, long long b, long long m) {
    a = mod(a, m); b = mod(b, m);
    if (b == 0) return 0;
    long long res = mul(mod(a + a, m), b>>1, m);
    if (b & 1) res = mod(res + a, m);
    return res;
}
inline long long inv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a/b;
        a = mod(a - mul(t, b, m), m); swap(a, b);
        u = mod(u - mul(t, v, m), m); swap(u, v);
    }
    return mod(u, m);
}

CSA 068 DIV2 E Sliding Product Sum


[1, 2, 3, …, N] の連続する k 要素の積としてありうる和をとる操作を 1 <= k <= K について行って、すべての総和をとって M で割ったあまりを求めよ。

・1 <= N <= 1018
・1 <= K <= min(600, N)
・1 <= M <= 1018


高校数学で習った和の中抜けを使います。そうすると

 (N + 1) N (N - 1) … (N - k + 1) / (k + 1)

を 1 <= k <= K について足しあげる問題になります。愚直に個別に足しあげても O(K2) なので大丈夫です。

ただし、M が大きい上に素数とは限らないので注意が必要です。基本的には掛け算も割り算も上のライブラリを使えばいいのですが、k + 1 と M が互いに素でないケースがいやです。しかし少し考えてみると、

N+1, N, N-1, ..., N-k+1

は連続する k + 1 個の整数なのでそのうちの 1 個が k + 1 で割り切れます。そこだけ k + 1 で割ってあげれば掛け算の問題になります。

#include <iostream>
using namespace std;

long long N, K, M;

inline long long mod(long long a, long long m) {
    return (a % m + m) % m;
}

inline long long mul(long long a, long long b, long long m) {
    a = mod(a, m); b = mod(b, m);
    if (b == 0) return 0;
    long long res = mul(mod(a + a, m), b>>1, m);
    if (b & 1) res = mod(res + a, m);
    return res;
}

long long solve() {
    long long res = 0;
    for (long long k = 1; k <= K; ++k) {
        long long tmp = 1;
        bool ok = false;
        for (long long num = N-k+1; num <= N+1; ++num) {
            long long tnum = num;
            if (!ok && num % (k+1) == 0) {
                ok = true;
                tnum = num / (k+1);
            }
            tmp = mul(tmp, tnum, M);
        }
        res += tmp;
        res %= M;
    }
    return res;
}


int main() {
    while (cin >> N >> K >> M) {
        cout << solve() << endl;
    }
}

AtCoder Petrozavodsk Contest 001 E - Antennas on Tree (黄色, 900 点)

はじめに

昨年末 DEGwer さんの数え上げテクニック集 がとても勉強になる資料として話題になりました。その中の P. 9 の「4. 条件の言い換え」のところに、「必要条件を列挙したらそれが十分条件だった」がありました。

こないだの APC 001 E - Antennas on Tree がその面白い問題例と感じたのでメモします。

APC 001 E - Antennas on Tree


問題概要

N 頂点のツリーの頂点集合の部分集合 S のうち、「全頂点のどの 2 頂点 u, v を選んでも、S に含まれるとある頂点 w が存在して、u-w 間の距離と v-w 間の距離とが異なる」という性質を満たすような最小サイズのものを求めよ。
 
【制約】
・ 2 <= N <= 105


この手の問題を考えるときに、まずはスター (通称「うに」) のケースを考えてみるのはポイントなのかな...と思います。

列の場合は下図のように端っこの一方を選べばよいです (K = 1)。列以外のケースだと最低 2 個は必要になるので、なんとなくこれがコーナーケースになりそうな予感を念頭に置いておきます。

f:id:drken1215:20180207135012j:plain

スター (うに) の場合は、下図のようにうにの先端を 1 個残して選ぶ必要があります。

f:id:drken1215:20180207135409j:plain:w300

このスターの場合をさらに推し進めて考えると以下のことが必要条件になるのがわかります:

どの頂点についてもその頂点を取り除いてできる部分木が m 個あるとすれば、そのうちの m-1 個の部分木からそれぞれ 1 個以上選ぶ必要がある

f:id:drken1215:20180207140359j:plain

これが実は十分条件にもなっているようです。

次数 3 以上の頂点については、この条件を満たせば一意特定できるのはほぼ明らかです。次数 1, 2 の頂点についてが少し不安になりますが、よくよく考えると確かに一意特定可能になっています。

木 DP の枠組みに乗せることを考えてみます。部分木たちの親側に「選ばれた頂点」があるかどうかを分岐するのが面倒そうなので、次数が 3 以上の頂点を根にしてしまえばスッキリします。根の次数が 3 以上なら、どの部分木を考えているときも親側に必ず「選ばれた頂点」が存在することになります。そうすると

木 DP を営むときのどの部分木についても、その子供たちのなす m 個の部分木のうち m-1 個以上に選ばれた頂点があることが必要かつ十分

ということが言えます。ここまで来ればあとは自然に木DPができます。

#include <iostream>
#include <vector>
using namespace std;
int N;
vector<int> G[110000];
const int INF = 1 << 29;
int rec(int v, int p) {
    int all = 0;
    int zero_num = 0;
    for (auto to : G[v]) {
        if (to == p) continue;
        int tmp = rec(to, v);
        all += tmp;
        if (tmp == 0) ++zero_num;
    }
    if (zero_num > 1) all += zero_num - 1;
    return all;
}
int main() {
    cin >> N;
    int r = -1;
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
        if (G[a].size() > 2) r = a;
        if (G[b].size() > 2) r = b;
    }
    if (r == -1) {
        cout << 1 << endl;
        return 0;
    }
    cout << rec(r, -1) << endl;
}

スターリング数と、問題まとめ

この間分割数の記事についての記事を書いたときに続けてスターリング数も次回書くつもりですっかり忘れていたので書こうと思い立ちました。

数え上げに関する話題として分割数やスターリング数は時折登場しますが、どちらも写像12相と呼ばれる広い枠組みに含まれています。前回は分割数を、今回はスターリング数を勉強しました。

なお、スターリング数 (の考え方) が使える問題として以下があります (他にもあったら大募集なのん):

 

0. 写像12相 (再掲)

n 個の玉を k 個の箱に入れる場合の数を数える問題を考えます。

  • 玉をそれぞれ区別するか
  • 箱をそれぞれ区別するか
  • 各箱に入る玉の個数は「制限なし」「1個以内」「1個以上」

によって12パターンの問題設定が考えられるので写像12相と呼ばれています。 以下の記事にとてもよくまとまっています。

mathtrain.jp

ちょっと問題設定がなかなかピンと来ない感じですが、今回は「箱を区別しない」部分をメインに考えます。「箱を区別しない」というのはつまり n 個の玉を k 個のグループに分ける問題を考えるということです。

 

2. スターリング数

考察の対象は以下の場合です:

  • n 個の玉は区別する
  • k 個の箱は区別しない
  • 各箱に入る玉の個数は 1 個以上

つまり n 個の互いに区別できる玉を k 個のグループに分ける場合の数を求める問題です。この場合の数を  S(n, k) と置くことにします。

 

ベル数との関連

ベル数もよく聞く名前ですが、それは以下の場合です:

  • n 個の玉は区別する
  • k 個の箱は区別しない
  • 各箱に入る玉の個数は区別しない

つまり n 個の互いに区別できる玉を k 個以下のグループに分ける場合の数を求める問題です。この場合の数を  B(n, k) と置くことにします。自明にわかることとして、

{ \displaystyle
B(n, k) = \sum_{i=1}^{k} S(n, i)
}

が成立します。そしてなんとベル数 B(n, n) は O(n) で求められるようです!

 

スターリング数の求め方

包除原理を用いて直接求めるバージョンと、漸化式で求めるバージョンがあります。

  • 漸化式で求めるバージョン:

{ \displaystyle
S(n, k) = S(n-1, k-1) + k S(n-1, k)
}

 

  • 直接求めるバージョン:

{ \displaystyle
S(n, k) = \frac{1}{k!} \sum_{i=1}^{k} (-1)^{k-i} C(k, i) i^{n}
}

 

漸化式で求めるバージョン

(これから書く)

分割数と、問題まとめ

こないだのドワンゴからの挑戦状で、分割数を用いる問題が出題されたので、周辺の話題を整理してみました。

数え上げに関する話題として分割数やスターリング数は時折登場しますが、どちらも写像12相と呼ばれる広い枠組みに含まれています。今回は分割数を、次の記事でスターリング数を勉強します。

なお、分割数 (の考え方) が使える問題として以下があります (他にもあったら大募集中なのん):

 

写像12相

n 個の玉を k 個の箱に入れる場合の数を数える問題を考えます。

  • 玉をそれぞれ区別するか
  • 箱をそれぞれ区別するか
  • 各箱に入る玉の個数は「制限なし」「1個以内」「1個以上」

によって12パターンの問題設定が考えられるので写像12相と呼ばれています。 以下の記事にとてもよくまとまっています。

mathtrain.jp

ちょっと問題設定がなかなかピンと来ない感じですが、今回は「箱を区別しない」部分をメインに考えます。「箱を区別しない」というのはつまり n 個の玉を k 個のグループに分ける問題を考えるということです。

 

1. 分割数

蟻本第二版の P. 66 に載っています。考察の対象は以下の場合です:

  • n 個の玉は区別しない
  • k 個の箱は区別しない
  • 各箱に入る玉の個数に制限はない

つまり自然数 n を k 個の 0 以上の整数の和で表す場合の数 (順序が異なるものは同一視) です。n = 5, k = 3 であれば、

0 + 0 + 5 = 0 + 1 + 4 = 0 + 2 + 3 = 1 + 1 + 3 = 1 + 2 + 2

の 5 通りの表し方があります。 この場合の数を P(n, k) と置くことにします。 P(n, k) は「自然数 n を k 個以下の 1 以上の整数の和で表す場合の数」とも言い換えられます (蟻本ではこっち)

 

分割数の性質

ここにまとめます。


  • 「k 個の 1 以上の整数への分割」は P(n-k, k) 通り
  • 「何個でもよい 1 以上の整数への分割」は P(n, n) 通り
  • P(n, k) = P(n, k-1) + P(n-k, k)
  • (ついでに) P(n, n) は O(n√n) で求められる

このうち、3 番目の漸化式を用いることで、P(n, k) を O(nk) で計算できます。特に P(n, n) は O(n2) で計算できます。さらに P(n, n) を求めるだけならばより高速に O(n√n) で計算できるようです。

なお、先程の写像12相の記事では、各箱に入る玉の個数が 1 個以上である場合を P(n, k) としているので記号の使い方が微妙に異なりますが、本質的にほとんど一緒です。

 

「k 個の 1 以上の整数への分割」は P(n-k, k) 通り

P(n, k) が求まれば、写像12相のうちの

  • n 個の玉は区別しない
  • k 個の箱は区別しない
  • 各箱に入る玉の個数は 1 個以上

も簡単に求まります。つまり自然数 n を k 個の 1 以上の整数の和で表す場合の数です。これを Q(n, k) と置くことにします。Q(n, k) に対して、n を分割した k 個の値それぞれについて 1 引くことで、

Q(n, k)  
= (n を k 個の 1 以上の整数に分割する場合の数)  
= (n - k を k 個の 0 以上の整数に分割する場合の数)  
= P(n-k, k)  

が成立します。この考察が「分割数の漸化式」の理解に直結します。

 

漸化式 P(n, k) = P(n, k-1) + P(n-k, k)

P(n, k) = P(n, k-1) + P(n-k, k)

の導出です。n を k 個の 0 以上の整数の和へと分割する方法のうち

0 を含むもの:
0 が何個あるかはわからないが、そのうちの 1 個の 0 を取り除いてしまってもよくて、残りの k - 1 個の 0 以上の整数の和で n を表す方法を考えればよい。よって、P(n, k-1) 通り。

0 を含まないもの:
n を k 個の 1 以上の整数に分割する場合の数、つまり Q(n, k) なので、P(n-k, k) 通り。  

以上より、P(n, k) = P(n, k-1) + P(n-k, k) が成立します。
一瞬、前者の場合について、0 が複数ある場合にダブルカウントしてしまってそうで怖くなるのですが、今回は k 個の整数は区別できないので大丈夫です。

 

1-3. 分割数を用いる問題

yukicoder No.269 見栄っ張りの募金活動

N 人の生徒で順に寄付金を払っていくことで合計 S 円の寄付金を集めたいが、 i + 1 人目の生徒は i 人目の生徒よりも K 円以上多く支払っていなければならない。 このようなことが成立する場合の数を求める問題。

様々な解法がある模様ですが、分割数でも解けます。

x[ i ] := (i 人目の生徒の支払う金額) - iK

とすると、

・x[0] + x[1] + ⋯+x[N-1] = S−(K+2K+⋯+(N-1)K)
・0 <= x[0] <= x[1] <= ... <= x[N-1]

を満たす (x[0], x[1], ..., x[N-1]) の組を数え上げる問題になるので、これは分割数 P(S−(K+2K+⋯+(N-1)K), N) です。
 

第4回 ドワンゴからの挑戦状 予選 C - Kill/Death

これも様々な解法があるようですが、分割数を前処理で求めておいてそれを利用して DP するのが1つの解法かと思います。
 

AOJ 0537 Bingo

分割数そのものではないですが関連しています。想定解法よりオーダーレベルで速い解法です。怒髪さんの 【No.027】「AOJ 0537 Bingo」 - dohatsutsu’s diary を参考にしました。 k = N2, n = S - k(k+1)/2, m = M-k として、

・x[0] + x[1] + ... + x[k-1] = n
・ 0<= x[0] <= x[1] <= ... <= x[k-1] <= m

を満たす (x[0], x[1], ..., x[k-1]) の組を数え上げる問題に帰着します。各 x が m 以下であるという条件の加わった分割数です。分割数を求める DP と同様にして求められます。P'(n, k) と置くことにします。

0 を含むもの:
分割数とまったく同様に、P'(n, k-1) 通り。

0 を含まないもの:
(n を k 個の 1 以上 m 以下の整数に分割する場合の数)
= (n-k を k 個の 0 以上 m-1 以下の整数に分割する場合の数)
= (n-k を k 個の 0 以上 m 以下の整数の分割する場合の数) - (そのうち m を含む場合の数)

この (そのうち m を含む場合の数) は m を 1 個取り除いてしまっても一緒なので P'(n-k-m, k-1) 通りです。 まとめると、

P'(n, k) = P'(n, k-1) + P'(n-k, k) - P'(n-k-m, k-1)

で求められます。
 

CSA 032 G Sum of Powers

a[0] + a[1] + ... + a[K-1] = N を満たす正の整数の組 (a[0], a[1], a[K-1]) それぞれに対して a[0]^M + a[1]^M + ... + a[K-1]^M の値を考えて、その総和を 1000000007 で割った余りを求める問題。

分割数の使い方がすごく賢い。 CSAcademy Round #32 : G. Sum of Powers - kmjp's blog に詳細あり。

総和が N になる a のうち、各 x が y 回使われるものが何通りあるかが計算できればよい。

総和が N になる a のうち、x が y 回以上使われるものは、P(N- K - xy, K - y) 通りあることがわかるので、x が y 回使われるものは P(N - K - (x-1)y, K - y) - P(N - K - (x-1)*(y + 1), K - (y + 1)) 通りある。

 

2. スターリング数

書きました drken1215.hatenablog.com