Algoogle

Algorithm for Programming Contest

JOI 春合宿 2009 Sequence

Category: JOI Tag: implementation, math

Sequence

問題概要


m個の要素からなる数列Aが渡される.
この数列をさらに以下のように拡張するとき, pからqまでにある奇数の数を求めよ.

解法

まずどの数も偶奇しかいらないので2でmodを取ったものを考える.
幅mずつ数列をずらしながら区切ってみる.
サンプルだと始め1234が1010となり次が0101(2345)になる(5=4+1, 下の例は実装を考慮して向きを反転させている).
この0101から1010は求めることができ(各値について, 一つ前の値と自分の値からm個前の値は一意に定まるから), また当然次の数も求めることが出来る.
いま幅mが有限なので前後が一意に定まるなら必ずループするはずである.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
0101
1010
1101
0110
0011
1001
0100
0010
0001
1000
1100
1110
1111
0111
1011
0101
...

よってこのループを求めてやれば区間を圧縮できる.
ループの長さは最悪でも 2^m-1個のはずである.
列を求める際にそれまでの奇数の個数をカウントしておけばあとはp,qを圧縮して計算するだけ.


コード


(Sequence.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;

int m, a, b, t, sum[(1<<24)+32];
long long p, q;

inline void nexta(int &x) {
        int c = (1&x)^(1&(x>>(m-1)));
        x = (x>>1)|(c<<(m-1));
}

void find_loop()
{
        b = a;
        for (int i = 0; i < m; i++) sum[i+1] = sum[i]+((b>>i)&1);

        int cur = 0;
        do {
                nexta(b);
                sum[cur+m+1] = sum[cur+m]+((b>>(m-1))&1);
                cur++;
        } while(b != a);
        t = cur;
}

long long solve()
{
        if(!a) return 0;
        find_loop();

        long long ans = 0;
        long long d = q-p;
        ans += d/t*sum[t];
        d %= t;
        p %= t;
        q = p+d;
        if(q > t) ans += sum[t]-sum[p]+sum[q%t];
        else ans += sum[q]-sum[p];
        return ans;
}

void input()
{
        cin >> m >> p >> q;
        p--;
        for (int i = 0; i < m; i++){
                int t; cin >> t; t%=2;
                a |= (t<<i);
        }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments