caozy623's Blog

看看数据范围|s|<=4000……模拟肯定不行。

如果写出求子矩阵元素和的式子就可以发现显然对于左上角为(x,y),右下角为(z,w)的一个子矩阵，其和应该为(s[x]+……+s[z])*(s[y]+……+s[w])。那么显然可以采用部分和优化的方法。设sum[i]表示s[0]+..s[i-1]，然后枚举所有的0<=j<i<=n，用c数组记录下sum[i]-sum[j]的个数。最后只需枚举a的质因数，然后ans+=c[i]*c[a/i]即可。注意枚举时还要判一下a/i是否小于sum[n]，不然就会数组越界了。（因为a<=10e9）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#include<cstdlib>
#define ll long long
#define maxn 100010
#define inf 1000000000
#define linf (1LL<<50)
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
    return x*f;
}

inline void read(char *s,int &ts)
{
	char x=getchar();
	while(!(x>='a'&&x<='z'))x=getchar();
	while(x>='a'&&x<='z')s[++ts]=x,x=getchar();
}
int A,a[maxn];
char s[maxn];
int sum[maxn],c[maxn];
int main()
{
    scanf("%d",&A);
    scanf("%s",s+1);
    int n=strlen(s+1);
    for(int i=1;i<=n;i++)
    {
        a[i]=s[i]-48;
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=n;i++)
    for(int j=0;j<i;j++)
    c[sum[i]-sum[j]]++;
    ll ans=0;
    if(A==0)
    {
        for(int i=0;i<=sum[n];i++)
        ans+=(ll)c[0]*(ll)c[i];
    }
    for(int i=1;i<=sum[n];i++)
    if(A%i==0&&A/i<=sum[n])
    ans+=(ll)c[i]*(ll)c[A/i];
    printf("%I64d\n",ans);
    return 0;
}