题目链接 Matrix multiplication

求矩阵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)$表示 x1的个数

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

最新文章

  1. Linux学习笔记(6)-文件I/O
  2. SPOJ 375 Query on a tree
  3. SSIS 项目部署模型
  4. float数据在内存中是怎么存储的 AND IEEE754测试程序
  5. oracle 循环语句
  6. CssSpritesGenerator使用
  7. php大力力 [018节]如何联系大力力
  8. PetShop
  9. 【原】Spark中Master源码分析(一)
  10. Django Meta内部类选项
  11. .NET系统架构改造的经验和教训
  12. R与数据分析旧笔记(十一)数据挖掘初步
  13. Java开源内容管理CMS系统J4CMS的几个样式
  14. python之字符串详解2
  15. 基于FPGA的RGB565_YCbCr_Gray算法实现
  16. MyEclipse激活步骤
  17. Linux新手随手笔记1.3
  18. 【读书笔记】iOS-Objective-C编程
  19. Jsp基本语法 第二章
  20. XSS工具

热门文章

  1. ios之UISplitViewController
  2. Mac 输入法小技巧
  3. (44)zabbix报警媒介:email
  4. mcu读写调式
  5. python基础学习笔记——方法返回值
  6. go的相关用法
  7. luogu2146 [NOI2015]软件包管理器
  8. 关于Relay Log无法自动删除的问题
  9. IS-IS IGP
  10. Cocos2d-JS 实现将TiledMap中的每个 tile 变成物理精灵的方法