Rockdu's Blog

4
7
10

3
5
15

题目大意：有一个长度为n的环形项链，现在把上面的珠子染成黑白两种颜色，要求任意两个黑色的珠子不能相邻，并且因为项链是环形的，能通过旋转变得相同的方案只算一种。问有多少种方案。

如果没有限制，这道题就是Burnside引理的板题。那么加了限制同样的我们要算出旋转1，2，3……格之后仍然相同的方案有多少种，这里我们依然可以把旋转i格相同的不考虑同构方案数转换为长度为gcd(i, n)的项链不考虑同构的方案数。但是因为有限制不好推导公式。

这时候我们考虑DP得到答案。首先分情况讨论：把环拆成链，第一个珠子是黑色DP一遍，那么结尾为白色的状态合法。第一个珠子是白色再DP一遍，结尾两种状态都合法。把答案加起来就可以了，总复杂度为O(n)。

但是考虑到这个DP每步转移都是一样的，可以矩阵加速。那么我们得到单个i的答案的复杂度就是O(logn)，再枚举GCD=i的有多少个，用一个欧拉函数就可以做到O(sqrt(n)*logn)。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
using namespace std;
const int mod = 1e9 + 7;
LL tmp[2][2];

void mul(LL A[2][2], LL B[2][2]) {
    tmp[0][0] = (1ll * A[0][0] * B[0][0] + 1ll * A[1][0] * B[0][1]) % mod;
    tmp[0][1] = (1ll * A[0][1] * B[0][0] + 1ll * A[1][1] * B[0][1]) % mod;
    tmp[1][0] = (1ll * A[0][0] * B[1][0] + 1ll * A[1][0] * B[1][1]) % mod;
    tmp[1][1] = (1ll * A[0][1] * B[1][0] + 1ll * A[1][1] * B[1][1]) % mod;
    memcpy(A, tmp, sizeof(tmp));
}

void MTpow(LL mt[2][2], int b) {
    LL ans[2][2] = {{1, 0}, {0, 1}};
    while(b) {
        if(b & 1) mul(ans, mt);
        mul(mt, mt), b >>= 1;
    }
    memcpy(mt, ans, sizeof(ans));
}

LL tmp2[2];
void mul(LL dp[2], LL A[2][2]) {
    tmp2[0] = (dp[0] * A[0][0] + dp[1] * A[0][1]) % mod;
    tmp2[1] = (dp[0] * A[1][0] + dp[1] * A[1][1]) % mod;
    memcpy(dp, tmp2, sizeof(tmp2));
}

int F(int x) {
    if(x == 1) return 1;
    LL A[2][2] = {{0, 1}, {1, 1}}, dp[2] = {1, 0}, ans;
    MTpow(A, x - 1), mul(dp, A);
    ans = dp[1], dp[0] = 0, dp[1] = 1;
    mul(dp, A), ans += dp[0], ans %= mod, ans += dp[1], ans %= mod;
    return ans;
}

int n, k, sq, ans;

int phi(int n) {
    int sq = sqrt(n), ans = 1, cnt = 0, pow = 1, N = n;
    for(register int i = 2; i <= n && i <= sq; ++i) {
        while(n % i == 0) 
            n /= i, ++cnt, pow *= i;
        if(cnt) ans *= (pow - pow / i), pow = 1, cnt = 0;
    }
    if(n != 1) ans *= (n - 1);
    return ans;
}

LL fpow(LL a, int b) {
    LL ans = 1;
    while(b) {
        if(b & 1) ans = a * ans % mod;
        a = a * a % mod, b >>= 1;
    }
    return ans;
}

int main() {
    while(1) {
        ans = 0;
        if(!(~scanf("%d", &n))) break;
        sq = max((int)(sqrt(n)), 2); // 注意！一定要拿小样例卡自己 
        for(register int i = 1; i < sq; ++i) {
            if(n % i == 0) {
                ans += 1ll * F(i) * phi(n / i) % mod, ans %= mod;
                ans += 1ll * F(n / i) * phi(i) % mod, ans %= mod;
            }
        }
        if(sq * sq == n) ans += 1ll * F(sq) * phi(n / sq) % mod, ans %= mod;
        LL invN = fpow(n, mod - 2);
        printf("%d\n", invN * ans % mod);
    }
    return 0;
}