【Rect】

【问题描述】

给定一个由数字(0-9)构成的字符串s。我们可以由此定义出size(s)*size(s)大小的矩阵b,其中b[i][j]=s[i]*s[j];请问在这个矩阵b中,有多少子矩阵满足其中的b[i][j]的和为另一个给定的数字a。

【输入格式】

第一行一个整数a。

第二行字符串s。

【输出格式】

一个整数表示满足条件的子矩阵数。

【输入样例】

10

12345

【输出样例】

6

【样例说明】

b矩阵为:

01 02 03 04 05

02 04 06 08 10

03 06 09 12 15

05 10 15 20 25

诸如01 02 03 04的和为10的子矩阵有6个。

【数据范围】

对10%的输入数据:size(s)<=10

对30%的输入数据:size(s)<=100

对100%的输入数据:0<=a<=1000000000,size(s)<=4000

把样例矩阵拿到草稿纸上乱搞一搞可以发现对于一个以(x1,y1),(x2,y2)为一条对角线两角的矩阵,其和为sum[x1~x2]*sum[y1~y2] 而sum一定为原来没构成矩阵前的数字的前缀和。所以与处理处前缀和,再算出一个sum[x1~x2]时用a/sum[x1~x2]去配sum[y1~y2]即可。注意a!=0时如果sum为0那么取模会RE需要continue掉,至于a=0时当sum=0,所有情况都可以,根据容斥原理推一推公式即可。

下面是代码:

 

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*