本文主要是介绍[Z-Trening-718][BALKAN OI 2009]Reading，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Q1 ： 邻接矩阵只能限制边数 怎么控制路径长度呢？
A ： 把路径长度转换为多条边 每个点虚拟为五个
Q2 ： 怎么统计长度小于N的点的和呢？
A ：虚拟一个空字符 他与任意真实字符距离为1 这样我们可以自然的构造一些开头是空字符的单词 比如"__AA" 这个单词开头有两个空字符 总体相异度为4
还有就是此题特别卡常数 其实我是没过的 用了1700+ms才过
题目可以直接在Vjudge上看 只是测不了
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXN 131
#define MAXM 131
#define MAXF 26
typedef int LL;
struct Matrix{ int n, m; LL A[MAXN+10][MAXN+10];
}E, Z, A, D, B;
bool vis[MAXN+10][MAXN+10];
LL Map[MAXN+10][MAXN+10];
int m;
LL K;
const int p = 1000000007;
void init(Matrix &X)
{ X.n = X.m = 0; memset(X.A, 0, sizeof(X.A));
}
void Get_E()
{ memset(E.A, 0, sizeof(E.A));E.n = E.m = MAXN; for(int i = 0; i < E.n; i++) E.A[i][i] = 1;
}
void mul(Matrix AA, Matrix BB, Matrix &Ans)
{ Matrix D; init(D); Ans.n = D.n = AA.n; Ans.m = D.m = BB.m; for(int i = 0; i < MAXN; i++) for(int j = 0; j < MAXN; j++) for(int k = 0; k < MAXN; k++) { D.A[i][k] += ((long long)AA.A[i][j] * BB.A[j][k]) % p; if(D.A[i][k] > p)D.A[i][k] -= p; } memcpy(Ans.A, D.A, sizeof(D.A));
}
void pow_mod(Matrix A, LL k, Matrix &Ans)
{ Matrix t = A; E.n = A.n; E.m = A.m; while(k) { if(k & 1) mul(E, t, E);mul(t, t, t); k >>= 1; } memcpy(Ans.A, E.A, sizeof(E.A));
}
int main()
{Get_E();cin >> K >> m;char c;c = getchar();while(c !='\n' ) c=getchar();for(int i = 1; i <= 26; i++)for(int d = 4; d >= 1; d--)Map[i+26*d][i+26*(d-1)] = 1;for(int i = 0; i < m; i++){char s[10];fgets(s, 10, stdin);int u = s[0] - 'a' + 1, v = s[2] - 'a' + 1, d = s[4] - '0';Map[u][v+26*(d-1)] = 1;Map[v][u+26*(d-1)] = 1;vis[u][v] = vis[v][u] = true;}for(int i = 1; i <= 26; i++)for(int j = i; j <= 26; j++)if(!vis[i][j])Map[i][j] = Map[j][i] = 1;for(int i = 0; i <= 26; i++) Map[0][i]++;LL ans = 0;memcpy(B.A, Map, sizeof(B.A));B.m = B.n = MAXN;pow_mod(B, K, A);for(int i = 0; i <= 26; i++)for(int j = 1; j <= 26; j++){ans += A.A[i][j];if(ans > p)ans %= p;}ans %= p;cout << ans;
}
/*
1 1
a b 2
*/这篇关于[Z-Trening-718][BALKAN OI 2009]Reading的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
