TOJ::Matrix

題目是要求一段數字S, Bij=Si*Sj,矩陣B的任意子矩陣和有多少等於a。
觀察之後發現,某一個子矩陣的和等於他的邊(數列S)的乘積,有點類似(A+B)的平方之類的。

所以我每舉N平方的S的區間和,如果是a的因數就把 S[a]++,最後再跑一次 S[i]S[a/i],也就是因數分解a的感覺。如果a是0就S[i]S[0]2,因為不是0時會跑到兩次,但是0只會跑到一次所以要2,還要記得加上S[0]*S[0]。
注意範圍,答案最大的狀況是 (4000^2)^2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#define N 4001
#define LL long long
using namespace std;
LL S[N*9]={0};
int NU[N];
char C[N];
int main(int argc,char *argv[])
{
int t,a;
LL sum=0,tmp=0;
scanf("%d",&t);
while(t--){
sum=tmp=0;
fill(S,S+N*9,0);
scanf("%d",&a);
scanf("%s",C);
int n=strlen(C);
for(int i=0;i<n;i++){NU[i]=C[i]-'0';}
for(int i=0;i<n;i++){
sum=0;
for(int j=i;j<n;j++){
sum+=NU[j];
if(a==0)S[sum]++;
else if(sum==0){}
else if(a%sum==0)S[sum]++;
}
}
tmp=0;
if(a==0){
for(int i=1;i<=N*9;i++){
tmp+=S[0]*S[i]*2;
//if(S[i]!=0)printf("EE:(%d)%d %d",i,S[0],S[i]);
}
tmp+=S[0]*S[0];
printf("%lld\n",tmp);
}else{
for(int i=1;i<=N*9;i++){
if(S[i]!=0){
if(a/i<=N*9)tmp+=S[a/i]*S[i];
}
}
printf("%lld\n",tmp);
}
}
return 0;
}