ABC 156 F - Modularness 解説 - haradyの競プロ記

問題へのリンク

全完25位。嬉しいね f:id:harady_hara:20200222223928p:plain

お気持ち

$k,\ q < 5000$ なので $O(kq)$ でよさそう。

解説

なので各クエリごとに $x$ 及び $d_i$ を $mod\ m$ で置き換えて良い。以下では $X= x\ mod\ m,\ D_i=d_i \ mod\ m$ とする。
すると数列は以下のようになる。

f:id:harady_hara:20200222222154p:plain — $a_i$ は適宜 $mod$ を取る

$a_j < a_{j+1}$ を満たさない $j$ を数えてみる。

$X+D_0+D_1\ ...\ +D_i$ が $m$ 以上になった時点で繰り上がり(?)が発生し、 $j=i$ で $a_j < a_{j+1}$ を満たさない。また $D_j=0$ となるような $j$ でも満たさない。このように、繰り上がる箇所と $D_j=0$ となる $j$ が分かれば解ける。

繰り上がりの回数は $(\sum _{i=0}^{n-2}{D_{i}} + X)/m$ 回である。なぜなら $D_i < m$ より隣接二項間で2回以上繰り上がることはないため。

0の個数は自明。また、 $D_j=0$ なる $j$ では繰り上がりは発生しない。

よって $O(kq)$ で解ける。

実装

以下ソースコード(コード内では#define int long longしています)

#define rep(i,a) for(int i=0;i<a;i++)

void solve() {
    int k, q; cin >> k >> q;
    vector<int> d(k); rep (i, k) cin >> d[i];
    rep (_, q) {
        int n, x, m; cin >> n >> x >> m; x %= m;
        int sum = 0;
        int z = 0;
        vector<int> D(k); rep (i, k) D[i] = d[i] % m, sum += D[i], z += (D[i] == 0);
        sum *= (n - 1) / k, z *= (n - 1) / k;
        rep (i, (n - 1) % k) sum += D[i], z += D[i] == 0;
        sum += x;
        cout << n - 1 - sum / m - z << endl;
    }
}