Atcoder-ABC158-EF 题解
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
Solution
#includetypedef long long ll;typedef unsigned long long ull;typedef std::pair PII;typedef std::pair 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 cnt(p, 0); if (p == 2 || p == 5) { for (int i = n - 1; i >= 0; i--) ans = ans + ((s - '0') % p == 0) * (i + 1); } else { cnt = 1; for (int i = 0; i < n; i++) { sum = (sum * 10 + s - '0') % p; ll now = qmi(10, n - 1 - i, p) * sum % p; ans += cnt; cnt++; } } coutn; vector v(n + 1); for (int i = 1; i > v.x >> v.y; v.y += v.x; } sort(v.begin() + 1, v.end()); vector f(n + 2, 0); // f 代表 的方案数。主动激活由 right 转移， 不激活由 i + 1 转移 f = 1; vector 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].x < v.y) top--; int right = max(stk, i); stk[++top] = i; f = (f + f) % mod; } cout
页:
[1]