codeforces365C（数学）

本文主要是介绍codeforces365C（数学），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

365C

题意：

给定一个长度为n的字符串s，组成一个数组b，其中b[i,j]=s[i]xs[j]，问有多少个矩阵的和等于给定的数字a

思路：

考虑一般情况：假设子矩阵是左上角是(x,y)，右下角是(xn,yn);
则这个矩阵的和可以表示为
第一行是：

\[s[x]*s[y]+s[x]*s[y+1]+s[x]*s[y+2]+...+s[x]*s[y_{n}] \]

化简得：

\[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;
}

这篇关于codeforces365C（数学）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！