ACM模版

描述

题解

这个题我不会写,看了题解也不怎么会,先 mark 一下吧,给大家提供一下官方题解和一份看起来还不错的代码吧……(╯﹏╰)难受。

我的数学比较差,容斥玩得不是特别好,玩不转,这个 dp 过程大致理解,可是修改操作部分不是特别懂……看了好久也没有理清楚头绪。感觉自己蠢死了~~~

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

#define clr(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int MAXN = 101;
const int MAXM = 5e4 + 10;

int n, m;
int a[MAXM];
int b[MAXM];
int c[MAXM];
int dp[MAXN][MAXN][MAXN];
ll tmp[MAXN];
ll res[MAXN];
ll ans[MAXN];

ll dfs(int u, int d)
{
    if (res[u] != -1)
    {
        return res[u];
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (dp[d][u][i])
        {
            ans = (ans + dp[d][u][i] + dp[d][u][i] * dfs(i, d)) % MOD;
        }
    }

    return res[u] = ans;
}

ll cal(int u)
{
    clr(res, -1);
    for (int i = 1; i <= n; i++)
    {
        if (res[i] == -1)
        {
            dfs(i, u);
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = (ans + res[i]) % MOD;
    }

    return ans;
}

int main()
{
    clr(dp, 0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
        for (int j = 1; j * j <= c[i]; j++)
        {
            if (c[i] % j == 0)
            {
                dp[j][a[i]][b[i]]++;
                if (c[i] / j != j)
                {
                    dp[c[i] / j][a[i]][b[i]]++;
                }
            }
        }
    }

    for (int i = 1; i < MAXN; i++)
    {
        tmp[i] = cal(i);
    }
    for (int i = MAXN - 1; i > 0; i--)
    {
        ans[i] = tmp[i];
        for (int j = 2 * i; j < MAXN; j += i)
        {
            ans[i] -= ans[j];
        }
        ans[i] = (ans[i] % MOD + MOD) % MOD;
    }

    cout << ans[1] << endl;

    int T;
    cin >> T;
    while (T--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        vector<int> v;
        for (int i = 1; i * i <= c[x]; i++)
        {
            if (c[x] % i == 0)
            {
                dp[i][a[x]][b[x]]--;
                v.push_back(i);
                if (c[x] / i != i)
                {
                    dp[c[x] / i][a[x]][b[x]]--;
                    v.push_back(c[x] / i);
                }
            }
        }
        c[x] = y;
        for (int i = 1; i * i <= c[x]; i++)
        {
            if (c[x] % i == 0)
            {
                dp[i][a[x]][b[x]]++;
                v.push_back(i);
                if (c[x] / i != i)
                {
                    dp[c[x] / i][a[x]][b[x]]++;
                    v.push_back(c[x] / i);
                }
            }
        }
        for (int i = 0; i < v.size(); i++)
        {
            tmp[v[i]] = cal(v[i]);
        }
        for (int i = MAXN - 1; i > 0; i--)
        {
            ans[i] = tmp[i];
            for (int j = 2 * i; j < MAXN; j += i)
            {
                ans[i] -= ans[j];
            }
            ans[i] = (ans[i] % MOD + MOD) % MOD;
        }

        cout << ans[1] << endl;
    }

    return 0;
}