HDU 4920 Matrix multiplication(bitset优化)
2024-09-04 15:48:32
求矩阵A和B相乘的结果。
因为答案只要对3取模,所以我们可以通过一些方法来加速计算。
我们对两个矩阵各开两个bitset,分别存储模3余1和模3余2的数。
然后相乘的时候and一下就好了。
c[i][j] = f(a_one[i] & b_one[j]) + f(a_one[i] & b_two[j]) * 2 + f(a_two[i] & b_one[j]) * 2 + f(a_two[i] & b_two[j])
$f(x)$表示 x中1的个数
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i) typedef long long LL; const int A = 810;
const int mod = 3; int n;
bitset <A> a_one[A], a_two[A], b_one[A], b_two[A], tmp;
int x; int main(){ while (~scanf("%d", &n)){ rep(i, 1, n){
a_one[i].reset();
a_two[i].reset();
b_one[i].reset();
b_two[i].reset();
} rep(i, 1, n){
rep(j, 1, n){
scanf("%d", &x);
x %= 3;
if (x == 1) a_one[i].set(j);
else if (x == 2) a_two[i].set(j);
}
} rep(i, 1, n){
rep(j, 1, n){
scanf("%d", &x);
x %= 3;
if (x == 1) b_one[j].set(i);
else if (x == 2) b_two[j].set(i);
}
} rep(i, 1, n){
rep(j, 1, n){
int ans = 0;
tmp = a_one[i] & b_one[j];
ans += tmp.count();
tmp = a_one[i] & b_two[j];
ans += 2 * tmp.count();
tmp = a_two[i] & b_one[j];
ans += 2 * tmp.count();
tmp = a_two[i] & b_two[j];
ans += tmp.count();
ans %= 3;
printf("%d", ans);
if (j < n) putchar(32);
}
putchar(10);
} } return 0;
}
最新文章
- Linux学习笔记(6)-文件I/O
- SPOJ 375 Query on a tree
- SSIS 项目部署模型
- float数据在内存中是怎么存储的 AND IEEE754测试程序
- oracle 循环语句
- CssSpritesGenerator使用
- php大力力 [018节]如何联系大力力
- PetShop
- 【原】Spark中Master源码分析(一)
- Django Meta内部类选项
- .NET系统架构改造的经验和教训
- R与数据分析旧笔记(十一)数据挖掘初步
- Java开源内容管理CMS系统J4CMS的几个样式
- python之字符串详解2
- 基于FPGA的RGB565_YCbCr_Gray算法实现
- MyEclipse激活步骤
- Linux新手随手笔记1.3
- 【读书笔记】iOS-Objective-C编程
- Jsp基本语法 第二章
- XSS工具