题解 P4270 【[USACO18FEB]Cow Gymnasts】

· · 题解

想要却不可得，你奈人生何

这题考场写炸.zip，瞎搞出答案？？？然后精度爆炸...参考了一下题解

预备知识： φ(x) = x\frac{(p1-1)(p2-1)...(pi-1)}{p1p2..pi}

题意： 给定 n 个平台，每个平台可以放置 1...n 个奶牛，对于层数为 i 的奶牛，每次会顺时针移动 （i-1） 个单位到其他平台。然后落下，问有多少种排列方式，使得不管怎么移动，每个平台的奶牛数都不变

结论一：对于每个层数的奶牛，只能从其他平台相同层数的奶牛平移过来，不能从层数较高的奶牛落下得到。

证明： 假设平台中层数最高为M，每次移动时，在这个平台前面M-1个的平台，每个都会贡献一头奶牛，如果存在落下的情况的话，那么在前面第M个的平台有存在落下的情况，那么这个平台的层数就会大于M，所以我们可以得到最高层的奶牛是从其他相同层数的奶牛平移过来。并且最高层的奶牛不会小落，因为这样会导致这个平台的奶牛层数就不是最高的了，所以最高层的奶牛对下面几层的奶牛无影响。依次类推，可以得到结论。

结论二：第i层的奶牛的循环周期是i的约数

证明： 依题意，每层的奶牛都是循环的，对于某个平台层数为i的奶牛，肯定是从一个周期为T的奶牛移动k次得到（等价于i=kT）结论得证

结论三：第i-1层的奶牛的循环周期是第i层奶牛循环周期的约数

证明： 对于一个平台第i层的奶牛，显然奶牛不能飞，不能悬空，所以下面一定要有一头奶牛垫着。然后感性理解一下... 滑稽

结论四：任意两个平台上的奶牛数量之差不超过一

证明： 对于两个相邻层的奶牛，周期分别为T_{i}和T_{i+1}(i为层数)，由结论二、三可得，T_{i}为i的约数，T_{i+1}为i+1的约数，gcd(i,i+1)=1，所以gcd(T_{i},T_{i+1})=1，又因为T_{i}为T_{i+1}的约数。所以我们可以得到T_{i}=1，所以除了最高的一层，周期都为1

结论五： ans = 2-n + \sum_{m=1}^{n-1}\ 2^{gcd(m,n)}

证明：这里的m意为最矮的台子有m只奶牛（m∈[1,n-1]），层数为m-1，由结论一二可得，循环周期为n和m的约数，所以最大的循环周期为 gcd（n, m) ，同时可以找到 gcd（n, m) 组，每组可以取或不取，共有 2^{gcd(m,n)}种情况，但是不能全部取，这个时候不满足最矮的有m头牛。当m=n时全部不取，此时方案数为1。所以我们可以得到一个式子 ans = 1+ \sum_{m=1}^{n-1}\ (2^{gcd(m,n)}-1)化简一下就是我们结论五

优化

我们可以观察一下n<=10^{12}所以直接暴力肯定会超的，于是我们就考虑一下优化，可以参考一下Longge的问题，里面的题解可以参考一下科学养锁，我们假设一下gcd（n, m） = n/g ，我们的洗个马就可以化简成 \sum_{g|n}^{n}\ (2^{n/g}*φ(g))然后搜一搜wjh的搜索天下第一就可以卡过去了，然后精度方面，在最后的答案因为n是有可能比我们的模数大的，所以我们要

    ans = (ans + 2 - N) % mod;
    if (ans < 0)
        ans += mod;

而不是

    ans = (ans + 2 - N + mod) % mod;

然后你就考崩了...下面是代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll mod = 1e9 + 7;
ll ans, N, n;
vector <ll> q;
vector <int> cnt;

inline ll ksm(ll a, ll p) {
    ll rt = 1;
    while (p) {
        if (p&1)
            rt = rt  * a % mod;
        a =  a * a % mod;
        p>>=1;
    }
    return rt;
}

void dfs(int num, ll g, ll m1, ll m2) {
    if (num == q.size()) {
        if (g == 1)
            return;
        ans+=ksm(2,N/g)*(g/m2%mod*m1%mod)%mod;
        ans%=mod;
        return;
    }
    dfs(num+1, g, m1, m2);
    m1 = m1 * (q[num] - 1) % mod;
    m2 = m2 * q[num];
    for (int i = 1; i <= cnt[num]; i++) {
        g = g * q[num];
        dfs(num+1, g, m1, m2);
    }
}

int main() {
    cin >> N;
    n = N;
    for (ll i = 2; i * i <= n; i++)
        if (n % i == 0) {
            int tot = 0;
            q.push_back(i);
            while (n % i==0) {
                n /= i;
                tot++;
            }
            cnt.push_back(tot);
        }
    if (n > 1) {
        q.push_back(n);
        cnt.push_back(1);
    }
    dfs(0, 1, 1, 1);
    ans = (ans + 2 - N) % mod;
    if (ans < 0)
        ans += mod;
    cout << ans;
    return 0;
}