首页 > 代码库 > SGU 196.Matrix Multiplication
SGU 196.Matrix Multiplication
时间限制：0.25s
空间限制：4M
Solution
n=10000，m=100000，显然不能用矩阵乘法乘出来。
S= ATA
对于矩阵S的一行，所有在A矩阵中1位置的元素都相等，并且都等于这一行1的个数之和。假设有k个1，这一行的和显然是k*k
由此只要统计每一行有多少个1，累加它的平方就可以了。O（n）的时间解决。
code
#include<cstdio>int sum[10009], n, m, x, y;int main() { scanf ("%d %d", &n, &m); for (int i = 1; i <= m; i++) { scanf ("%d %d", &x, &y); sum[x]++, sum[y]++; } int ans = 0; for (int i = 1; i <= n; i++) ans += sum[i] * sum[i]; printf ("%d", ans); return 0;}
SGU 196.Matrix Multiplication
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。