cf C. Matrix

http://codeforces.com/contest/365/problem/C

构造出的矩阵中的长方形的和等于构成它的长的那些数字的和加上构成它的宽的那些数字的和。也就是求这个字符串中的两个子字符串的和的乘积等于a的数目。记录每一个子字符串的和的等于m的数目。然后枚举就可以求出数目。0要单独处理。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 50000
 5 #define LL __int64
 6 using namespace std;
 7 
 8 LL a;
 9 char s[maxn];
10 LL c[maxn];
11 LL sum[maxn];
12 LL g[maxn];
13 LL ans;
14 
15 
16 int main()
17 {
18     while(scanf("%I64d",&a)!=EOF)
19     {
20         scanf("%s",s);
21         int k=strlen(s);
22         for(int i=0; i<k; i++)
23         {
24             c[i+1]=(LL)(s[i]-'0');
25             sum[i+1]=sum[i]+c[i+1];
26         }
27         int cnt=0;
28         for(int i=1; i<=k; i++)
29         {
30             for(int j=0; j<i; j++)
31             {
32                 LL m=sum[i]-sum[j];
33                 g[m]++;
34                 cnt++;
35             }
36         }
37         if(a==0)
38         {
39            ans=2*(cnt-g[0])*g[0]+g[0]*g[0];
40         }
41         else
42         {
43             ans=0;
44             for(int i=1; i<40000; i++)
45             {
46                 if(a/i<40000&&a%i==0)
47                 {
48                     ans+=g[i]*g[a/i];
49                 }
50             }
51         }
52         printf("%I64d
",ans);
53     }
54     return 0;
55 }

View Code