codevs \ # 3147 [문제 풀이] 행렬 곱셈 2

제목 설명 Description
n * n 의 행렬 두 개 를 제시 하고 m 회 는 그들의 적 중 고정자 행렬 의 수치 와.
* 카드 평 가 를 방지 하기 위해 데이터 범 위 를 줄 이 고 시한 을 낮 추 었 습 니 다.
입력 설명 Input Description
첫 줄 두 개의 정수 n, m.다음 n 줄 은 각 줄 의 n 개의 비 마이너스 정 수 를 나타 내 고 첫 번 째 행렬 을 나타 낸다.다음 n 줄, 각 줄 n 개의 비 마이너스 정 수 는 두 번 째 행렬 을 나타 낸다.다음 m 줄, 각 줄 의 네 번 째 정수 a, b, c, d 는 첫 번 째 행렬 과 두 번 째 행렬 의 적 중, 두 번 째 줄 의 b 열 과 c 행 의 d 열 을 정점 으로 하 는 서브 행렬 의 요소 와.
출력 설명 Output Description
매번 질문 할 때마다 한 줄 의 정 수 를 출력 하여 이번 질문 의 답 을 표시 합 니 다.
샘플 입력 Sample Input
3 2 1 9 8 3 2 0 1 8 3 9 8 4 0 5 15 1 9 6 1 1 3 3 2 3 1 2
샘플 출력 Sample Output
661 388
데이터 범위 및 알림 Data Size & Hint
[데이터 규모 와 약정]
40% 의 데이터 만족, n < = 100, m < = 1000.100% 의 데이터 만족, n < = 800, m < = 10000, 입력 데이터 에서 매트릭스 요소 < 100, a, b, c, d < = n.
데이터 에 경사도 가 있다.
진짜 폭력:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
struct Mart
{
	int a[801][801];
}A,B,C;
void Martix(Mart A,Mart B)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				C.a[i][j]+=A.a[i][k]*B.a[k][j];
			}
		//	printf("%d ",C.a[i][j]);
		}
		//printf("
");
	}
}
int x1,x2,y1,y2;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&A.a[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&B.a[i][j]);
	Martix(A,B);
	for(int k=1;k<=m;k++)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		long long ans = 0;
		if(x1>x2)swap(x1,x2);
		if(y1>y2)swap(y1,y2);
		for(int i=x1;i<=x2;i++)
		{
			for(int j=y1;j<=y2;j++)
			{
				ans += C.a[i][j];
			}
		}
		printf("%lld
",ans);
	}
	return 0;	
}

첫 번 째 행렬 의 i 행 j 는 a [i] [j], 두 번 째 는 b [i] [j] 로 설정 하고 행렬 곱셈 의 정의 에 따라 답 은 ∑ (min (a, c) < = i < = max (a, c), min (b, d) < = j < = max (b, d) (∑ (1 < k < n) a [i] [k] * b [k] [j]),
시간 복잡 도 는 O (n ^ 3) 로 시간 을 초과 합 니 다.
그래서 우 리 는 그것 을 변형 시 켜 야 한다.
덧셈 결합 율, 득: ∑ (1 < k < n) (∑ (min (a, c) < = i < = max (a, c)) (∑ (min (b, d) < = j < = max (b, d))) (a [i] * b [k] [j])),
곱셈 결합 侓, 득: ∑ (1 < k < n) (∑ (min (a, c) < = i < = max (a, c) a [i] [k]) * (∑ (min (b, d) < = j < = max (b, d) b [k] [j])),
시간 복잡 도 는 O (n ^ 2) 로 떨 어 지지 만 m 회 를 계산 해 야 하기 때문에 시간 을 초과 합 니 다.
그러나 우 리 는 ∑ (min (a, c) < = i < = max (a, c) a [i] [k] 와 ∑ (min (b, d) < = j < = max (b, d) b [k] [j] 는 접두사 와 구 할 수 있 음 을 발견 할 수 있다.
따라서 시간 복잡 도 는 다시 O (n) 로 떨 어 지지 만 처리 하 는 O (n ^ 2) 를 추가 해 야 합 니 다.
그래서 총 시간 복잡 도 는 O (mn + n ^ 2) 입 니 다.
메모: 공간 제한 이 64000 KB 이기 때문에 접두사 와 후 에는 행렬 a 와 행렬 b 를 유지 할 수 없습니다. 또한 변수 유형 은 긴 정형 을 사용 해 야 하지만 접두사 와 정형 만 사용 할 수 있 습 니 다. 긴 정형 을 사용 하 는 것 은 답 일 수 밖 에 없습니다.
첨부 코드:

#include<iostream>

using namespace std;

int n,m,i,j,matrix1[2001][2001]={},matrix2[2001][2001]={},a,b,c,d;

long long answer;

int main ()

{

    cin>>n>>m;

    for (i=1;i<=n;i++)

    for (j=1;j<=n;j++)

    scanf("%d",&matrix1[i][j]);

    for (i=1;i<=n;i++)

    for (j=1;j<=n;j++)

    scanf("%d",&matrix2[i][j]);

    for (i=1;i<=n;i++)

    for (j=1;j<=n;j++)

    matrix1[i][j]+=matrix1[i-1][j];

    for (i=1;i<=n;i++)

    for (j=1;j<=n;j++)

    matrix2[i][j]+=matrix2[i][j-1];

    for (i=1;i<=m;i++)

    {

        scanf("%d %d %d %d",&a,&b,&c,&d);

        answer=0;

        for (j=1;j<=n;j++)

        answer+=(long long)(matrix1[max(a,c)][j]-matrix1[min(a,c)-1][j])*(long long)(matrix2[j][max(b,d)]-matrix2[j][min(b,d)-1]);

        cout<<answer<<endl;

    }

    return 0;

} 

ACcode：100scores.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
struct Mart
{
	int a[801][801];
}A,B;
int x1,x2,y1,y2;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&A.a[i][j]);
			A.a[i][j]+=A.a[i-1][j];
		}
			
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&B.a[i][j]);
			B.a[i][j]+=B.a[i][j-1];
		}
	for(int k=1;k<=m;k++)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		long long ans = 0;
		if(x1>x2)swap(x1,x2);
		if(y1>y2)swap(y1,y2);
		for(int j=1;j<=n;j++)
		ans+=(A.a[x2][j]-A.a[x1-1][j])*(B.a[j][y2]-B.a[j][y1-1]);
		printf("%lld
",ans);
	}
	return 0;	
}