Codeforces 1139D Steps to One dp

啊，我要死了，这种垃圾题居然没写出来，最后十分钟才发现错在哪。

不知道为什么我以为对于一个数x ，除了它的因子和它的倍数都是和它互质的，我脑子是抽了吗？

随便瞎dpdp的题。。还熬夜打cf好暴躁啊啊啊。

我求我自己以后打比赛多动动脑子。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N = 1e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

const double eps = 1e-;

const double PI = acos(-);

int Power(int a, int b) {

    int ans = ;

    while(b) {

        if(b & ) ans = 1ll * ans * a % mod;

        a = 1ll * a * a % mod; b >>= ;

    }

    return ans;

}

void add(int &a, int b) {

    a += b; if(a >= mod) a -= mod;

}

int n, ans, dp[N];

int inv[N];

vector<int> fac[N];

vector<int> cnt[N];

int dfs(int x) {

    if(x == ) return ;

    if(~dp[x]) return dp[x];

    dp[x] = ;

    int ret = n / x;

    int res = SZ(fac[x]);

    add(dp[x], (1ll * inv[n - ret] * n + mod) % mod);

    for(int i = ; i < SZ(fac[x]) - ; i++) {

        add(dp[x], 1ll * inv[n - ret] * cnt[x][i] % mod * dfs(fac[x][i]) % mod);

    }

    return dp[x];

}

int main() {

    memset(dp, -, sizeof(dp));

    inv[] = ;

    for(int i = ; i < N; i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;

    for(int i = ; i < N; i++)

        for(int j = i; j < N; j += i)

            fac[j].push_back(i);

    scanf("%d", &n);

    for(int i = ; i <= n; i++) {

        cnt[i].resize(SZ(fac[i]));

        for(int j = SZ(fac[i]) - ; j >= ; j--) {

            cnt[i][j] = n / fac[i][j];

            for(int k = j + ; k < SZ(fac[i]); k++)

                if(fac[i][k] % fac[i][j] == )

                    cnt[i][j] -= cnt[i][k];

        }

    }

    for(int i = ; i <= n; i++)

        add(ans, 1ll * inv[n] * dfs(i) % mod);

    printf("%d\n", ans);

    return ;

}

/*

*/

秒客网

Codeforces 1139D Steps to One dp

相关文章