首页 > 代码库 > HDU 2865
HDU 2865
和上题一样,但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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。