365C
给定一个长度为n的字符串s,组成一个数组b,其中b[i,j]=s[i]xs[j],问有多少个矩阵的和等于给定的数字a
考虑一般情况:假设子矩阵是左上角是(x,y),右下角是(xn,yn);
则这个矩阵的和可以表示为
第一行是:
化简得:
\[s[x]*(s[y]+s[y+1]+s[y+2]+...+s[y_{n}]) \]一共有n行,所以总矩阵大小就是:
\[(s[x]+s[x+1]+s[x+2]+...+s[x_{n}])*(s[y]+s[y+1]+s[y+2]+...+s[y_{n}]) \]所以可以预处理出来所有区间的前缀和,然后枚举,求a/s[len]的个数即可
#include <bits/stdc++.h> #define x first #define y second #define IOS ios::sync_with_stdio(false);cin.tie(0); #define lowbit(x) x&(-x) #define INF 0x7fffffff #define eb emplace_back #define divUp(a,b) (a+b-1)/b #define mkp(x,y) make_pair(x,y) #define lb lower_bound #define ub upper_bound #define int long long using namespace std; typedef unsigned long long ull; typedef pair<int, int> pii; int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}; bool checkP2(int n) {return n > 0 and (n & (n - 1)) == 0;}; char s[4010]; int ss[4010]; void solve() { int a; cin >> a; cin >> (s + 1); int n = strlen(s + 1); map<int, int> mp; for (int i = 1; i <= n; i++) ss[i] = ss[i - 1] + s[i] - '0'; for (int len = 1; len <= n; len++) { for (int l = 1; l + len - 1 <= n; l++) { int r = l + len - 1; int x = ss[r] - ss[l - 1]; mp[x]++; } } int cnt = 0; for (int len = 1; len <= n; len++) { for (int l = 1; l + len - 1 <= n; l++) { int r = l + len - 1; int x = ss[r] - ss[l - 1]; if(a==0) cnt+=mp[0];//a为0的情况特判; if(x==0) continue;//x为0避免对0取模, if (a % x == 0) { cnt += mp[a / x]; } } } cout << cnt << endl; } signed main() { IOS; solve(); return 0; }