SCUT - 12 - 西方国家 - 矩阵快速幂
2024-09-04 20:00:37
https://scut.online/p/12
可以用矩阵快速幂来做。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=26;
struct Matrix {
int m[MAXN][MAXN];
Matrix() {}
void clear() {
memset(m,0,sizeof(m));
}
void init(int m[MAXN][MAXN]) {
for(int i=0; i<MAXN; ++i) {
for(int j=0; j<MAXN; ++j)
this->m[i][j]=m[i][j];
}
}
Matrix operator+(Matrix ma) {
Matrix res;
res.clear();
for(int i=0; i<MAXN; ++i) {
for(int j=0; j<MAXN; ++j)
res.m[i][j]=m[i][j]+ma.m[i][j];
}
return res;
}
Matrix operator*(Matrix ma) {
Matrix res;
res.clear();
for(int i=0; i<MAXN; ++i) {
for(int j=0; j<MAXN; ++j)
for(int k=0; k<MAXN; ++k)
res.m[i][j]+=m[i][k]*ma.m[k][j];
}
return res;
}
Matrix qpow(ll n) {
Matrix res;
res.clear();
for(int i=0; i<MAXN; ++i)
res.m[i][i]=1;
Matrix x=*this;
for(;n;n>>=1){
if(n&1)
res=res*x;
x=x*x;
}
return res;
}
void show(){
for(int i=0; i<MAXN; ++i) {
for(int j=0; j<MAXN; ++j)
printf("%d",m[i][j]);
printf("\n");
}
printf("\n");
}
};
char s[27];
char t[1001];
int main() {
#ifdef Yinku
freopen("Yinku.in","r",stdin);
#endif // Yinku
ll n;
while(~scanf("%lld",&n)) {
scanf("%s%s",s,t);
Matrix A;
A.clear();
for(int i=0;i<26;i++){
A.m[i][s[i]-'a']=1;
}
Matrix An=A.qpow(n);
for(int i=0;i<26;i++){
for(int j=0;j<26;j++){
if(An.m[i][j]){
//printf("%c->%c\n",'a'+i,'a'+j);
s[i]='a'+j;
}
}
}
for(int i=0;t[i]!='\0';i++){
t[i]=s[t[i]-'a'];
}
puts(t);
}
return 0;
}
最新文章
- ASP.NET Core框架揭秘（持续更新中…）
- VIM键盘映射 (Map)~转载
- Hibernate SQL方言 (hibernate.dialect) Spring配置文件applicationContext.xml
- 特殊字符转义&时间格式化&获取URL参数
- 拖放 js
- sendEmail的使用
- jvm运行时环境属性一览
- 爆破vcrkme01（已补上注册机）
- linux note
- poj 3335 /poj 3130/ poj 1474 半平面交 判断核是否存在 / poj1279 半平面交 求核的面积
- poj 1014多重背包
- AO之Addins开发[杂谈1] Toolbar中添加一条分割线
- 【sed & awk 第二版笔记】以州和人名排列_P38
- [ExtJS6学习笔记]Ext JS6主题系列 (Classic工具包)
- 【原创】分布式之redis复习精讲
- JS一些实用的方法
- sqlserver为不同数据库建立不同访问权限的帐号
- ALGO-149_蓝桥杯_算法训练_5-2求指数
- ext.js打印出提示弹窗(鼓捣了两天终于尼玛出来了)
- JavaScript：动态代理之远程代理