Codeforces Round #137 (Div. 2)

转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

不是很难的一场~~~

A. Shooshuns and Sequence

随便YY下吧，首先必须从k个之后，都是相同的，否则不管怎么样，都不会完成

然后就需要看k之前连续相同的有几个

B. Cosmic Tables

直接搞，两个数组分别记录每一行当前的位置，以及每一列当前的位置

C. Reducing Fractions

分解质因子之后，不要将质因子组合，那样容易出错，一个是容易出上界，二个容易个数过多

显然新分数是将原分数约分得到的，所以个数不变，我们保留剩下的因子即可

#include<iostream>#include<cstdio>#include<map>#include<cstring>#include<cmath>#include<vector>#include<algorithm>#include<set>#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 1000000007using 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<n;i++)          for(int j=0;j<n;j++){              ans.m[i][j]=0;              for(int k=0;k<n;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<n;i++)          for(int j=0;j<n;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<n;i++){          for(int j=0;j<n;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<k;i++) for(int j=0;j<k;j++) init.m[i][j]=1;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<k;i++)for(int j=0;j<k;j++)ans=(ans+init.m[i][j])%MOD;printf("%I64d\n",ans);}return 0;}