不是很難的一場~~~
A. Shooshuns and Sequence
隨便YY下吧，首先必須從k個之後，都是相同的，否則不管怎麼樣，都不會完成
然後就需要看k之前連續相同的有幾個
B. Cosmic Tables
直接搞，兩個數組分別記錄每一行當前的位置，以及每一列當前的位置
C. Reducing Fractions
分解質因子之後，不要將質因子組合，那樣容易出錯，一個是容易出上界，二個容易個數過多
顯然新分數是將原分數約分得到的，所以個數不變，我們保留剩下的因子即可
[cpp]
#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 10000005
#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
using namespace std;
int prime[N]={0},c1[N],c2[N];
int n,m,a[M],b[M];
void Prime(){
for(int i=2;i<N;i++){
if(prime[i]) continue;
for(int j=2;j*i<N;j++)
prime[i*j]=1;
}
}
void split(int num,int c[]){
for(int i=2;i*i<=num&&prime[num];i++){
while(num%i==0){
c[i]++;
num/=i;
}
}
if(num>1) c[num]++;
}
void print(int num,int c[]){
int tmp=1;
for(int i=2;i*i<=num&&prime[num];i++){
// cout<<i<<" "<<c[i]<<endl;
while(num%i==0){
if(c[i]){c[i]--;tmp*=i;}
num/=i;
}
}
if(num>1&&c[num]){c[num]--;tmp*=num;}
printf("%d ",tmp);
}
int main(){
Prime();
while(scanf("%d%d",&n,&m)!=EOF){
mem(c1,0);mem(c2,0);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
split(a[i],c1);
}
for(int i=0;i<m;i++){
scanf("%d",&b[i]);
split(b[i],c2);
}
for(int i=2;i<N;i++){
int mm=min(c1[i],c2[i]);
c1[i]-=mm;c2[i]-=mm;
}
printf("%d %d\n",n,m);
for(int i=0;i<n;i++)
print(a[i],c1);
printf("\n");
for(int i=0;i<m;i++)
print(b[i],c2);
printf("\n");
}
return 0;
}
#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 10000005
#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
using namespace std;
int prime[N]={0},c1[N],c2[N];
int n,m,a[M],b[M];
void Prime(){
for(int i=2;i<N;i++){
if(prime[i]) continue;
for(int j=2;j*i<N;j++)
prime[i*j]=1;
}
}
void split(int num,int c[]){
for(int i=2;i*i<=num&&prime[num];i++){
while(num%i==0){
c[i]++;
num/=i;
}
}
if(num>1) c[num]++;
}
void print(int num,int c[]){
int tmp=1;
for(int i=2;i*i<=num&&prime[num];i++){
// cout<<i<<" "<<c[i]<<endl;
while(num%i==0){
if(c[i]){c[i]--;tmp*=i;}
num/=i;
}
}
if(num>1&&c[num]){c[num]--;tmp*=num;}
printf("%d ",tmp);
}
int main(){
Prime();
while(scanf("%d%d",&n,&m)!=EOF){
mem(c1,0);mem(c2,0);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
split(a[i],c1);
}
for(int i=0;i<m;i++){
scanf("%d",&b[i]);
split(b[i],c2);
}
for(int i=2;i<N;i++){
int mm=min(c1[i],c2[i]);
c1[i]-=mm;c2[i]-=mm;
}
printf("%d %d\n",n,m);
for(int i=0;i<n;i++)
print(a[i],c1);
printf("\n");
for(int i=0;i<m;i++)
print(b[i],c2);
printf("\n");
}
return 0;
}
D. Olympiad
readforces~~~~看懂之後，排序直接貪心，題目說一定有一組相加大於k，所以最優為1
E. Decoding Genome
簡單題~~構造矩陣，快速冪乘
[cpp]
#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 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<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;
}
#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 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<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;
}
