HDOJ5514

发表于 | 分类于

题目HDOJ5514

题意

题目给了m块石头 n个青蛙
石头从0~m-1标号 石头围成一个圆 青蛙从1~n标号
第i只青蛙可以跳ai格 即从k石头跳到(k+ai)%m石头
所有的青蛙都从0石头开始跳 每一只青蛙都可以跳任意步
当一只青蛙跳到一个石头上
它就”占领”这块石头
它会”占领”尽可能多的石头
当它跳离这块石头 “占领”关系并不会改变
问：
有多少石头被占领了至少1次 输出这些石头的下标和
n<=1e4 m<=1e9 ai<=1e9

分析

此题时限1s 显然暴力O(n*m)的做法是不可行的
优化复杂度的关键在于如何处理某些石头被重复计算的问题
比如两只青蛙可以分别跳2和3 那么6这块石头会被这两只青蛙重复占领 但是我们只能对它算一次贡献
这样去重的问题 一般采用容斥处理

我们先考虑只有一只青蛙的情况
由于石头围成一个圆 问题即为：
k*ai%m一共有多少不同的值，这里的$k\in N$
我们先来解决这个问题
首先lcm(ai,m)必定存在 记为r
r是m的倍数 相当于把一个m长的路径复制了r/m份 头尾连起来
青蛙在长为m的环上跳 相当于在这个长为r的直道上跳
由于青蛙跳r/ai次必定为到达r 相当于青蛙在环上跳了r/ai次回到原点
并不需要担心重复 因为r=lcm(ai,m)
如果某个被复制的点被重复跳到了 那么在此之前必已经经过r 矛盾了
(对 那个打表发现的规律就是这么来的)
于是显然在这个r上能跳r/ai次 能占领r/ai个格子
化简一下 r/ai=lcm(ai,m)/ai=ai*m/gcd(ai,m)/ai=m/gcd(ai,m)
那么问题转化为一只能跳gcd(ai,m)的青蛙在m长度的直道上能占领多少石头

在此之后 我们解决原问题
由于直接容斥的复杂度是指数级别的
于是采用对m的因子算贡献的方法

假设d是m的因子 青蛙每次能跳k步
如果d%k==0 也就是说青蛙可以跳到d这个石头 那么青蛙也能跳到d的整数倍石头
同时 如果2d也是m的因子 并且2d%k==0 显然这个石头之前被算过了 需要容斥一下
我们用cnt数组标记 cnt[i]==1表示m的第i个因数可以被某个ai整除
用num数组计数 num[i]表示m的第i个因数的贡献次数
假设d这个石头有贡献 那么我们需要给ans加上d 2d 3d … (m-1)/d*d
这里可以用等差数列公式优化 相当于给ans加上d*(1+(m-1)/d)*((m-1)/d)/2
注意这里需要容斥 在最后要保证所有有贡献的因子的num值为1
因此 如果d有贡献 ans+=(cnt-num)*d*(1+(m-1)/d)*((m-1)/d)/2
并更新 大于d并且能被d整除因子的num值 因为它们在这个时候也被算了cnt-num次贡献

于是这里的代码应该这样写：
fac容器存了m的因子(从小到大排序 下标从0开始)
cnt和num的意义上面已经说了

1
2
3
4
5
6
7
8
9
10
11
12
long long ans = 0;
for (int i = 0; i < fac.size(); i++) {
    if (cnt[i] != num[i]) {
        ll t = (m - 1) / fac[i];
        ans += (t*t + t) / 2 * fac[i] * (cnt[i] - num[i]);//等差数列求和公式优化
        for (int j = i + 1; j < fac.size(); j++) {
            if (fac[j] % fac[i] == 0) {
                num[j] += cnt[i] - num[i];//更新后继因子贡献
            }
        }
    }
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e4 + 10;

ll cnt[N], num[N];
vector<ll> fac;

int main() {
    int t;
    cin >> t;
    int cas = 1;
    while (t--) {
        int n;
        int m;
        cin >> n >> m;
        fac.clear();
        memset(cnt, 0, sizeof(cnt));
        memset(num, 0, sizeof(num));
        for (int i = 1; i*i <= m; i++) {
            if (m%i == 0) {
                fac.push_back(i);
                if (i*i != m) fac.push_back(m / i);
            }
        }
        sort(fac.begin(), fac.end());
        fac.pop_back();
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            int g = __gcd(x, m);
            for (int j = 0; j < fac.size(); j++) {
                if (fac[j] % g == 0) {
                    cnt[j] = 1;
                }
            }
        }
        ll ans = 0;
        for (int i = 0; i < fac.size(); i++) {
            if (cnt[i] != num[i]) {
                ll t = (m - 1) / fac[i];
                ans += (t*t + t) / 2 * fac[i] * (cnt[i] - num[i]);
                for (int j = i + 1; j < fac.size(); j++) {
                    if (fac[j] % fac[i] == 0) {
                        num[j] += cnt[i] - num[i];
                    }
                }
            }
        }
        printf("Case #%d: ", cas++);
        cout << ans << endl;
    }
    return 0;
}