CF-212-div 1 - c++编程基础

题目意思：

给一个十进制数s和整数n，定义bij=s[i]*s[j].求矩阵b中，共有多少个子矩形，满足矩形内部所有元素之和为n.

解题思路：

发觉矩形的特点：如果每一行都提取一个列标和，实际上就是矩形的行标和*列标和。假设矩形的左上角为(a,b),右下角为(x,y),则矩形的内部和为sum(va(a~x)*sum(va(b~y).

sum[i]表示连续和为i的个数。

dp[i]表示小标从1~i的数值和。

Tip:不能蛮搞，积极分析问题的特点啊。

代码：

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define eps 1e-6  
#define INF 0x3f3f3f3f  
#define PI acos(-1.0)  
#define ll __int64  
#define LL long long  
#define lson l,m,(rt<<1)  
#define rson m+1,r,(rt<<1)|1  
#define M 1000000007  
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;  
  
#define Maxn 41000  
#define Maxm 4100  
  
ll sum[Maxn],dp[Maxm];  
ll all,n;  
char save[Maxm];  
  
  
int main()  
{  
   //freopen("in.txt","r",stdin);  
   //freopen("out.txt","w",stdout);  
   while(~scanf("%I64d%s",&n,save+1))  
   {  
       int len=strlen(save+1);  
       dp[0]=0;  
       memset(sum,0,sizeof(sum));  
  
       for(int i=1;i<=len;i++)  
       {  
           dp[i]=dp[i-1]+save[i]-'0';  
  
           for(int j=1;j<=i;j++)  
               sum[dp[i]-dp[j-1]]++; //统计各个区间的元素和的个数  
       }  
  
       ll ans=0;  
       all=(1+len)*len/2; //总的区间的个数  
  
       if(n)  
       {  
           for(int i=1;i<=dp[len];i++)  
           {  
               if(n%i==0&&n/i<=dp[len])  
                   ans+=sum[i]*sum[n/i]; //列标区间和 和行标区间和  
           }  
       }  
       else  
            ans=2*all*sum[0]-sum[0]*sum[0];//0的话 单独处理  
  
       printf("%I64d\n",ans);  
   }  
   return 0;  
}