Codeforces 1139 D(プッシュ+dp)

タイトル配信推計ブログ配信
式を押し終わったら素朴に求めればいいオーズ

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int m, mu[maxn], vis[maxn], primes[maxn], tot;
ll dp[maxn];
vector factor[maxn];

ll ksm(ll a, ll b) {
    ll ret = 1;
    for (; b; b >>= 1) {
        if (b & 1)  ret = ret * a % mod;
        a = a * a % mod;
    }
    return ret;
}

void pre(int n) {
    rep(i, 1, n) {
        for (int k = 1; k * i <= n; k++)
            factor[k * i].push_back(i);
    }

    mu[1] = 1;
    rep(i, 2, n) {
        if (!vis[i]) {
            primes[tot++] = i;
            mu[i] = mod - 1;
        }
        for (int j = 0; j < tot && primes[j] * i <= n; j++) {
            vis[primes[j] * i] = 1;
            if (i % primes[j] == 0) break;
            mu[primes[j] * i] = mod - mu[i];
        }
    }
}

ll calc(int x, int d) {
    ll ret = 0;
    for (int i : factor[x / d]) {
        ret = (ret + (ll)mu[i] * (m / d / i) % mod) % mod;
    }
    return ret;
}

void DP() {
    dp[1] = 0;
    rep(i, 2, m) {
        ll k = m - m / i;
        ll tmp = m;
        for (auto j : factor[i]) {
            if (j == i) continue;
            tmp = (tmp + dp[j] * calc(i, j) % mod) % mod;
        }
        dp[i] = tmp * ksm(k, mod - 2) % mod;
    }
}

ll ANS(int m) {
    ll ret = 0;
    rep(i, 1, m) {
        ret = (ret + dp[i] + 1) % mod;
    }
    return ksm(m, mod - 2) * ret % mod;
}

int main() {
    read(m);
    pre(m);
    DP();
    writeln(ANS(m));
    return 0;
}

転載先:https://www.cnblogs.com/AlphaWA/p/10675795.html