( VIJOS )VOJ 1049 送给圣诞夜的礼品 矩阵快速幂
2024-08-22 17:34:52
非常普通的矩阵快速幂...
但是我
第一次写忘了矩阵不能交换律...
第一二次提交RE直到看到题解才发现这道题不能用递归快速幂...
第三次提交成了c编译错误...
第四次提交WA发现写循环快速幂的时候少清零了一个f...
所以提交了五次才终于对了,什么垃圾的代码能力...通过率杀手...
希望下次能捡起我的脑子....
代码很简单 如下
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=;
const double eps=1e-;
int n,m;
struct mat{
int e[maxn][maxn];
};
mat pro(mat x,mat y){
mat z;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
z.e[i][j]=;
for(int k=;k<=n;k++){
z.e[i][j]+=x.e[i][k]*y.e[k][j];
}
}
}return z;
}
mat pow(mat x,int k){
mat z;
bool f=;
while(k>){
if(k%!=){
if(f){
z=x;
f=;
}else{
z=pro(x,z);
}
}k/=;
x=pro(x,x);
}
return z;
}
int main(){
int k;
scanf("%d%d%d",&n,&m,&k);
int x,z,w;
z=k/m; w=k%m; mat c;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
c.e[i][j]=;
}
}
mat a=c; mat d=c;
for(int i=;i<=m;i++){
mat b=c;
if(i==){
for(int j=;j<=n;j++){
scanf("%d",&x);
a.e[j][x]=;
}
if(w>=){
d=a;
}
continue;
}
for(int j=;j<=n;j++){
scanf("%d",&x);
b.e[j][x]=;
}
a=pro(b,a);
if(i<=w){
d=a;
}
}
if(z==){
a=d;
}else if(w==){
c=a;
a=pow(c,z);
}else{
c=a;
a=pro(d,pow(c,z));
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(a.e[i][j]!=){
printf("%d ",j);
break;
}
}
}
cout<<endl;
return ;
}
最新文章
- SPOJ DISUBSTR ——后缀数组
- java List<;Item>; its=new ArrayList<;Item>;(); Map按value中的某字段排序
- 无约束优化算法——牛顿法与拟牛顿法(DFP,BFGS,LBFGS)
- 【bzoj1433】 ZJOI2009—假期的宿舍
- CentOS7安装Nginx并部署
- 编码神器——Sublime Text 包管理工具及扩展大全
- 访问者模式,visitor
- Unity 3D中的内存管理
- 【转】关于Activity和Task的设计思路和方法
- poj 3335 /poj 3130/ poj 1474 半平面交 判断核是否存在 / poj1279 半平面交 求核的面积
- Hive基础(3)---Fetch Task(转)
- [转载] MapReduce工作原理讲解
- 学习使用Mendeley1
- Decision tree(决策树)算法初探
- mysql--实现oracle的row_number() over功能
- python selenium 百度登录
- html限制文本框只能输入数字和一个小数点
- 项目Alpha冲刺——随笔集合
- bootstrap 引用注意事项
- 理解RESTFul和SOA