Atcoder题解汇总

ABC 158

E. Divisible Substring (取模前缀和思维, 一点点基本数论)

题意

给了一个长度为 /(n/) 的数字串，和一个质数 /(p/) ，询问有多少子串对应的数字满足是 /(p/) 的倍数，输出答案, 若有前导零也算作合法数字。

数据范围
/(1/leq N /leq 2 * 10^5/)
/(2/leq P /leq 10000/)

思路

• 显然不能用高精，过于荒谬，然后我就不会了
• 其实是个前缀和题目，但有个小结论:
  • /(x_1x_2x_3x_4x_5 * 10^n /% p = m,/;x_1x_2*10^{n+3}/%p=m/)
  • 则 /(x_3x_4x_5 * 10^n /% p = m/), 即 /(x_3x_4x_5 /% p = 0/)
  • 若 /(p/) 是质数，且 /(p /neq 2 /& p /neq 5/)
  • /(p = 2/), /(p = 5/) 特判即可
• 利用以上结论做前缀和计数即可，很经典，记得 cnt[0] = 0

Solution

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> PII;
typedef std::pair<ll, ll> PLL;
typedef double db;
#define arr(x) (x).begin(),(x).end()
#define x first
#define y second
#define pb push_back
#define endl "/n"
using namespace std;
/*----------------------------------------------------------------------------------------------------*/

ll qmi(ll a, ll k, int mod) {
    ll res = 1;
    while (k) {
            if (k & 1)
                    res = res * a % mod;
            a = a * a % mod;
            k >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, p;
    string s;
    cin >> n >> p >> s;
    ll sum = 0, ans = 0;
    vector<ll> cnt(p, 0);
    if (p == 2 || p == 5) {
        for (int i = n - 1; i >= 0; i--)
            ans = ans + ((s[i] - '0') % p == 0) * (i + 1);
    }
    else {
        cnt[0] = 1;
        for (int i = 0; i < n; i++) {
            sum = (sum * 10 + s[i] - '0') % p;
            ll now = qmi(10, n - 1 - i, p) * sum % p;
            ans += cnt[now];
            cnt[now]++;
        }
    }
    cout << ans << endl;
    return 0;
}
// x1x2x3x4 * 10^3 % p = m, x1x2 * 10^5 % p = m
// 两者相减, x3x4 * 10^3 % p = 0 等价于 x3x4 % p = 0

F. Removing Robots (线性DP，思维)

题意

给了 /(n/) 个机器人的坐标 /(x_i/) 和移动距离 /(d_i/), 每个机器人可以被主动激活向正轴移动 /(d_i/) 距离, 如果途中碰到别的机器人也会激活别的机器人, 以此递归进行。主动激活的次数不限制，机器人被激活后移动完成就会消失，询问最后机器人的剩余的不同情况数。

答案/(/mod 998244353/)

数据范围
/(1 /leq N /leq 2 * 10^5/)
/(-10^9/leq x_i /leq 10^9/)
/(1/leq d_i /leq 10^9/)

思路

• 考虑问题的话，要逆向来考虑是显然的，正着太麻烦，并且主动激活的顺序和结果无关
• DP的由来感觉不是很好想？定义状态 /(f[i]/) 为关于 [i,n] 机器人的方案数。
• 如果这样定义状态的话，状态转移就好想了。对于此题对一个机器人的操作是要么主动激活要么被动激活要么没有激活。
  • 对于主动激活，不考虑前面的机器人的局面会是什么，那么对于后面的情况，局面是和激活该机器人能影响的范围有关（直接或者间接）。
  • 对于被动激活，不考虑前面机器人的局面，实际是和主动激活一个效果
  • 对于没有激活，不考虑前面机器人的局面，其实是后一个机器人的所有局面。
• 所以状态转移：f[i] = (f[i+1] + f[next]) % mod, 目标答案 f[1]
• 用栈来实现查找最远不被影响的机器人。

Solution

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> PII;
typedef std::pair<ll, ll> PLL;
typedef double db;
#define arr(x) (x).begin(),(x).end()
#define x first
#define y second
#define pb push_back
#define endl "/n"
using namespace std;
/*----------------------------------------------------------------------------------------------------*/
const int mod = 998244353;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    vector<PII> v(n + 1);
    for (int i = 1; i <= n; i++){
        cin >> v[i].x >> v[i].y;
        v[i].y += v[i].x;
    }
    sort(v.begin() + 1, v.end());
    vector<ll> f(n + 2, 0);     // f[i] 代表 [i, n] 的方案数。主动激活由 right 转移， 不激活由 i + 1 转移
    f[n + 1] = 1;
    vector<int> stk(n + 2, 0);
    int top = 0;
    stk[++top] = n + 1;
    v.pb({2e9 + 10 ,0});
    for (int i = n; i ; i--) {
        while (top && v[stk[top]].x < v[i].y) top--;
        int right = max(stk[top], i);
        stk[++top] = i;
        f[i] = (f[i + 1] + f[right]) % mod;
    }
    cout << f[1] << endl;
    return 0;
}