首页 > 代码库 > HDU 2865

HDU 2865

2024-07-27 23:39:59   213人阅读

和上题一样，但K较大，不能直接用矩阵来写。这个矩阵必定是这个形式的。

0 1 1 1

1 0 1 1

1 1 0 1

1 1 1 0

分成对角线上元素B与非对角线上元素A

k: 1 2 3 4 ...

A: 1 2 7 20...

B: 0 3 6 21...

按上题经验，我们可以知道，B才是要求的。那么

Bn=(k-1)An-1

An=(k-2)An-1+Bn-1

于是可以得到

An=（k-2）An-1+(k-1)*An-2.这里就可以使用到矩阵连乘了。

可以通过A求得B。注意，这里能用的只能是K-1种颜色，因为中间一种颜色已不可用。于是，按上题同样的思路即可。

 

 

PS：今天不知为什么，内心特别烦闷。这道题的思路，昨天就想到的，本以为留着今天来写。可是，没想到，一点心情也没有。。。以后也不做这种蠢事，一定要一有思路，马上就写。。。。

贴个别人的代码吧。。（他是求出了Bn的表达式的，但我找不出来）

#include<cstdio>#include<cstring>#include<vector>#define P 1000000007#define MAXM 2#define MAXN 32000typedef long long LL;using namespace std;bool p[MAXN];vector<int> factor;vector<int> prime;struct Matrix {    LL mat[MAXM][MAXM];    void Zero() {        memset(mat, 0, sizeof(mat));    }    void Unit() {        Zero();        mat[0][0] = mat[1][1] = 1;    }    void Build(int k) {        Zero();        mat[0][1] = 1;        mat[0][0] = k - 2;        mat[1][0] = k - 1;    }};Matrix operator *(Matrix &a, Matrix &b) {    int i, j, k;    Matrix tmp;    tmp.Zero();    for (i = 0; i < MAXM; i++) {        for (j = 0; j < MAXM; j++) {            for (k = 0; k < MAXM; k++)                tmp.mat[i][j] += a.mat[i][k] * b.mat[k][j];            tmp.mat[i][j] %= P;        }    }    return tmp;}Matrix operator ^(Matrix a, int k) {    Matrix tmp;    for (tmp.Unit(); k; k >>= 1) {        if (k & 1)            tmp = tmp * a;        a = a * a;    }    return tmp;}void Factor(int n) {    int i;    factor.clear();    for (i = 1; i * i < n; i++) {        if (n % i == 0) {            factor.push_back(i);            factor.push_back(n / i);        }    }    if (i * i == n)        factor.push_back(i);}LL ExtGcd(LL a, LL b, LL &x, LL &y) {    LL t, d;    if (b == 0) {        x = 1;        y = 0;        return a;    }    d = ExtGcd(b, a % b, x, y);    t = x;    x = y;    y = t - a / b * y;    return d;}LL InvMod(LL a, LL n) {    LL x, y;    ExtGcd(a, n, x, y);    return (x % n + n) % n;}int Count(int x) {    int res, i;    res = x;    for (i = 0; prime[i] * prime[i] <= x; i++) {        if (x % prime[i] == 0) {            res -= res / prime[i];            while (x % prime[i] == 0)                x /= prime[i];        }    }    if (x > 1)        res -= res / x;    return res;}LL F(int n, int k) {    LL res;    if (n == 1)        res = 0;    else if (n == 2)        res = (LL) k * (k - 1);    else if (n == 3)        res = (LL) k * (k - 1) % P * (k - 2);    else {        Matrix g;        g.Build(k);        g = g ^ (n - 3);        res = g.mat[0][0] * k % P * (k - 1) % P * (k - 2);        res += g.mat[1][0] * k % P * (k - 1);    }    return res % P;}LL Burnside(int n, int k) {    LL ans;    int i;    Factor(n);    for (i = ans = 0; i < (int) factor.size(); i++) {        ans += F(factor[i], k) * Count(n / factor[i]) % P;        if (ans >= P)            ans -= P;    }    return ans * InvMod(n, P) % P;}void Init() {    int i, j;    memset(p, true, sizeof(p));    for (i = 2; i < 180; i++) {        if (p[i]) {            for (j = i * i; j < MAXN; j += i)                p[j] = false;        }    }    prime.clear();    for (i = 2; i < MAXN; i++) {        if (p[i])            prime.push_back(i);    }}int main() {    int n, k;    Init();    while (~scanf("%d%d", &n, &k))        printf("%I64d\n", Burnside(n, k - 1) * k % P);    return 0;}

　　

HDU 2865


联系
我们