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;}