0

等間隔の二項係数モジュロMの合計を見つける方法は?
すなわち。( n C a + n C a + r + n C a + 2r + n C a + 3r + ... + n C a + kr ) % M = ?
与えられた: 0 <= a < r, a + kr <= n < a + (k+1)r, n < 10 5 , r < 100

私の最初の試みは：

int res = 0;
int mod=1000000009;
for (int k = 0; a + r*k <= n; k++) {
    res = (res + mod_nCr(n, a+r*k, mod)) % mod;
}

しかし、これは効率的ではありません。したがって、ここ とこの論文を読んだ後、上記の
合計が次 と同等であることがわかりました。および ω = e i2π/rは原始的な 1 の r乗根です。 Order(r) でこの合計を見つけるコードは何ですか?

編集: n は 10 5まで、r は 100 までです。

元の問題のソース: https://www.codechef.com/APRIL14/problems/ANUCBC
コンテストの問題の編集者: https://discuss.codechef.com/t/anucbc-editorial/5113
この投稿を 6 年間再訪した後後で、元の問題ステートメントを自分のバージョンにどのように変換したか思い出せませんが、正しいソリューション アプローチを見たい人のために、元のソリューションへのリンクを共有しました。

4

4 に答える 4

0

操作は高価です。modできるだけ避けてください

uint64_t res = 0;
int mod=1000000009;
for (int k = 0; a + r*k <= n; k++) {
    res += mod_nCr(n, a+r*k, mod);
    if(res > mod)
        res %= mod;
}

このコードはテストしていません

于 2014-04-13T12:12:04.783 に答える