Codeforces Round #137 (Div. 2) - c++编程基础

mespace std;
struct Matrix{
LL m[N][N];
}init;
LL n,k,m;
int ID(char ch){
if(ch>='a'&&ch<='z') return ch-'a';
else return ch-'A'+26;
}
Matrix Mult(Matrix m1,Matrix m2,int n){
Matrix ans;
for(int i=0;i for(int j=0;j ans.m[i][j]=0;
for(int k=0;k ans.m[i][j]=(ans.m[i][j]+m1.m[i][k]*m2.m[k][j])%MOD;
}
return ans;
}
Matrix Pow(Matrix m1,LL b,int n){
Matrix ans;
for(int i=0;i for(int j=0;j ans.m[i][j]=(i==j);
while(b){
if(b&1)
ans=Mult(ans,m1,n);
m1=Mult(m1,m1,n);
b>>=1;
}
return ans;
}
void debug(Matrix m1,int n){
for(int i=0;i for(int j=0;j printf("%I64d ",m1.m[i][j]);
printf("\n");
}
}
int main(){
while(scanf("%I64d%d%d",&n,&k,&m)!=EOF){
for(int i=0;i while(m--){
char str[5];
scanf("%s",str);
init.m[ID(str[0])][ID(str[1])]=0;
}
// debug(init,k);
init=Pow(init,n-1,k);
// debug(init,k);
LL ans=0;
for(int i=0;i for(int j=0;j ans=(ans+init.m[i][j])%MOD;
printf("%I64d\n",ans);
}
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#define inf 1<<27
#define M 100005

#define N 55
#define Min(a,b) ((a)<(b) (a):(b))
#define Max(a,b) ((a)>(b) (a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(b))
#define LL long long
#define MOD 1000000007
using namespace std;
struct Matrix{
LL m[N][N];
}init;
LL n,k,m;
int ID(char ch){
if(ch>='a'&&ch<='z') return ch-'a';
else return ch-'A'+26;
}
Matrix Mult(Matrix m1,Matrix m2,int n){
Matrix ans;
for(int i=0;i for(int j=0;j ans.m[i][j]=0;
for(int k=0;k ans.m[i][j]=(ans.m[i][j]+m1.m[i][k]*m2.m[k][j])%MOD;
}
return ans;
}
Matrix Pow(Matrix m1,LL b,int n){
Matrix ans;
for(int i=0;i for(int j=0;j ans.m[i][j]=(i==j);
while(b){
if(b&1)
ans=Mult(ans,m1,n);
m1=Mult(m1,m1,n);
b>>=1;
}
return ans;
}
void debug(Matrix m1,int n){
for(int i=0;i for(int j=0;j printf("%I64d ",m1.m[i][j]);
printf("\n");
}
}
int main(){
while(scanf("%I64d%d%d",&n,&k,&m)!=EOF){
for(int i=0;i while(m--){
char str[5];
scanf("%s",str);
init.m[ID(str[0])][ID(str[1])]=0;
}
// debug(init,k);
init=Pow(init,n-1,k);
// debug(init,k);
LL ans=0;
for(int i=0;i for(int j=0;j ans=(ans+init.m[i][j])%MOD;
printf("%I64d\n",ans);
}
return 0;
}

Codeforces Round #137 (Div. 2) (二)