ABC132 F Small Products

令和ABC初期の問題。黄diffだったけど自力できたのでうれしいね。

問題概要

正の整数 個を一列に並べたものであって、隣接して並んでいるどの つの整数の積も 以下であるものの個数を で割った余りを求めてください。

考察

例えば数列のある数が1であったとき、隣接する項の積が以下になるのは、隣接する項が以下の時です。

もし数列のある数が2であれば、隣接する項の積が以下になるのは、隣接する項が以下の時です。

もし数列のある数が3であれば、隣接する項の積が以下になるのは、隣接する項が以下の時です。

みたいな風に考えると、各項についてとりあえずまで見ればまあ解けます。ただし間に合いません。

で、間に合わないのでくらいにならないかな～と考えると、本当にそうなることがわかります。

軽くお気持ち証明をします。示したいことは「隣接する項の積を以下にするために見るべき数はたかだかである」ことです。

とします。は「ある数をとすると、隣の数は以下でなければならない」という意味です。

するとこうなります。やなどが抜けていると思うかもしれません。

例えばですが、右側がになるのは既にで出ているので考えなくて良いです。

上に示したものは、左側の値を変化させていったときに、右側の値が変化する境界です。

これらの値の変化は明らかに単調であるので、これらの境界のみ考えればよく(= 境界の間は必ず全て同じ値になる)、状態を大きく削減することが出来ます。

ここまではすぐできました。ただここから遷移を合わせるパートで大変に手こずりましたね......。

以前から遷移ガチャをせずに、きちんと数式などで考えて機械的に遷移を導いていくことを意識して目指しているんですが、結局よくわからなくなってガチャガチャやってサンプル試して出すをしてしまいました。大反省。

これがキーエンスコンでの大失敗の原因になったので、本当に改善しないといけません。こういうのを速めに詰め切るのってどうしたら良いんでしょうか。

少々手探り感はありますが、まずナイーブな実装をしてみることにします。

最初配るDPで考えていたんですが、区間和更新が必要になって嫌になりました(これでめっちゃ時間を溶かした)。

こういう時のテクとして、配るDPで区間和更新になるやつは、貰うDPにすると区間和取得で対応できることが多いです。
区間に辺が張られたグラフのDPなどで、普通のセグ木を使って処理する典型があったりしますね。

というわけで貰うDPを考えると、以下のような式になります。

この遷移は累積和で処理できるので、前処理さえしていれば十分高速に動作します。

これでナイーブな実装は出来ました。

ここからであることを利用した解法にするのはまあまあ簡単で、遷移式はほぼ変わりません。

ただ先述の通りであることを利用した解法は、境界のみに着目して境界の間にある数をすっ飛ばすことで高速化するものなので、境界の間にある数を補完してあげる必要があります。

よって境界の間にある数をとすると、

と導けます。

以上を実装することでこの問題を解くことが出来ます。

僕の実際のコードは以下です。実質貰うDPの考え方をしているのに、迷走していたので配るDPのままになっています。遷移ガチャで当たりを引けないとこういうちぐはぐなことになりがち......。何で解けたんだ？

#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define rep(i,n) for(ll i=0;i<(n);++i)
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template< int mod >
struct ModInt {
    int x;

    ModInt() : x(0) {}

    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator*=(const ModInt &p) {
        x = (int) (1LL * x * p.x % mod);
        return *this;
    }

    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }

    ModInt operator-() const { return ModInt(-x); }

    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

    bool operator==(const ModInt &p) const { return x == p.x; }

    bool operator!=(const ModInt &p) const { return x != p.x; }

    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
        t = a / b;
        swap(a -= t * b, b);
        swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const {
        ModInt ret(1), mul(x);
        while(n > 0) {
        if(n & 1) ret *= mul;
        mul *= mul;
        n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ModInt &a) {
        int64_t t;
        is >> t;
        a = ModInt< mod >(t);
        return (is);
    }

    static int get_mod() { return mod; }
};

using modint = ModInt<MOD>;

int main(int argc, char const *argv[]) {
    ll n,k; cin>>n>>k;
    vector<ll> A;

    // 境界を全列挙する
    for (ll i = 1; i*i <= n; ++i) {
        A.push_back(i);
        if (i!=n/i) A.push_back(n/i);
    }

    int m = A.size();
    sort(A.begin(), A.end());
    vector<modint> a(m);
    rep(i,m) a[i] = A[i];

    // DP初期化
    vector<vector<modint>> dp(k+1, vector<modint>(m+1, 0));
    rep(j,m) {
        if (j == 0) dp[0][j] = 1;
        if (j != 0) dp[0][j] = a[j]-a[j-1];
    }
    modint N = n;

    rep(i,k-1) {
        vector<modint> cost(m+1);
        rep(j,m) cost[j+1] += dp[i][j]+cost[j];
        rep(j,m) {
            modint tmp = 1;
            if (j != 0) tmp = a[j]-a[j-1];
            dp[i+1][j] += cost[m-j]*tmp;
        }
    }

    modint ans = 0;
    for (int j = m-1; j >= 0; --j) {
        ans += dp[k-1][j];
    }

    cout << ans << '\n';
    return 0;
}