有std，但是沒有自我實現，所以是無碼專區

description

完全由數字組成的字符串 $s$，劃分成若干段，每一段看成一個十進制的數（允許前導零）求有多少種劃分方法使得相鄰兩個數至少一個是 $D$ 的倍數。對 $10^9+7$ 取模。

數據：$5\times 10^5,10^6$ 級別。

我的想法

針對 $30\%$ 的數據：$n\le 1000$ 【$n=|s|$】。

設 $d{p}_{i,0/1}:$ 劃分在 $i$ 處，枚舉上一個劃分點 $j$，判斷 $(j,i]$ 是否是 $D$ 的倍數 的方案數。

然后直接轉移，就是 $O(n^2)$ 的。

solution

對于另 $20\%:(D,10)=1$ 就是提示正解的部分分。

記 $S_i=({\sum }_{s_i}?10^{n?i})\%D$，即以 $i$ 開始的后綴對應的十進制數（在取模 $D$ 的意義下)

判定條件： $s[i,j]$ 組成的數能被 $D$ 整除，當且僅當 $S_i=S_{j+1}$。

設 $d{p}_{i,0/1}:$ 從前往后劃分到 $i$ ，當前段能否被 $D$ 整除的方案數。

如果能被 $D$ 整除，那么必須從 $S_j=S_{i+1},1\le j<i$ 轉移過來，否則從不被整除的 $S_j$ 轉移過來。

用一個桶數組 $cn{t}_i:S_j=i$ 的 $d{p}_j$ 的和。

i.e. 在 $i$ 轉移被整除的信息的時候，相當于去找 $cn{t}_{S_i}$ 這個桶，$d{p}_i\to cn{t}_{S_i}$。

以上是 $(D,10)=1$，當 $(D,10)=1$ 時，上述的判定條件就不完全對了。

改寫 $D=D_1?D_2$，其中 $(D_1,10)=1,D_2=2^a{5}^b$。

改寫 $S_i:$ 從 $i$ 開始到結尾形成的十進制數對 $D_1$ 取模的結果。

改寫判定條件：$s[i,j]$ 組成的數能被 $D$ 整除，當且僅當 $S_i=S_{j+1}\wedge D_2|s[i,j]$。

在十進制下 $s[i,j]$ 要能被 $2,5$ 的冪次整除，只需要看后面的若干位即可。

這里 $D\le 10^6\approx 2^{20}\approx 5^9$，所以最多看后面的 $20$ 位。

具體而言

• 首先判斷 $s[i?19,i]$ 組成的數是否 $D$ 的倍數。
  • 是，再從桶里面找 $cn{t}_{S_{i+1}}\to d{p}_i$。
• 暴力處理 $s[j,i],i?19\le j\le i?1$ 判斷是否是 $D$ 的倍數，再 $\to d{p}_i$ 。
• 對于 $j=i?19$ 到 $i$ 中間已經包含有 $20$ 位了【$i?(i?19)+1=20$】，所以 $S_j\to cnt$，可以入桶了。

參考code

#include <bits/stdc++.h>using namespace std;template <typename T> T power(T a, long long b) {T r = 1;while (b) {if (b & 1) {r *= a;}a *= a;b >>= 1;}return r; }template <typename T> T inverse(T a, T m) {a %= m;if (a < 0) {a += m;}T b = m, u = 0, v = 1;while (a) {T t = b / a;b -= a * t;swap(a, b);u -= v * t;swap(u, v);}if (u < 0) {u += m;}return u; }template <int _P> struct modnum {static constexpr int P = _P;private:int v;public:modnum() : v(0) {}modnum(long long _v) {v = _v % P;if (v < 0) {v += P;}}explicit operator int() const {return v;}bool operator==(const modnum &o) const {return v == o.v;}bool operator!=(const modnum &o) const {return v != o.v;}modnum inverse() const {return modnum(::inverse(v, P));}modnum operator-() const {return modnum(v ? P - v : 0);}modnum operator+() const {return *this;}modnum &operator++() {v++;if (v == P) {v = 0;}return *this;}modnum &operator--() {if (v == 0) {v = P;}v--;return *this;}modnum operator++(int) {modnum r = *this;++*this;return r;}modnum operator--(int) {modnum r = *this;--*this;return r;}modnum &operator+=(const modnum &o) {v += o.v;if (v >= P) {v -= P;}return *this;}modnum operator+(const modnum &o) const {return modnum(*this) += o;}modnum &operator-=(const modnum &o) {v -= o.v;if (v < 0) {v += P;}return *this;}modnum operator-(const modnum &o) const {return modnum(*this) -= o;}modnum &operator*=(const modnum &o) {v = (int) ((long long) v * o.v % P);return *this;}modnum operator*(const modnum &o) const {return modnum(*this) *= o;}modnum &operator/=(const modnum &o) {return *this *= o.inverse();}modnum operator/(const modnum &o) const {return modnum(*this) /= o;} };template <int _P> ostream &operator<<(ostream &out, const modnum<_P> &n) {return out << int(n); }template <int _P> istream &operator>>(istream &in, modnum<_P> &n) {long long _v;in >> _v;n = modnum<_P>(_v);return in; }using num = modnum<1000000007>;int main() {freopen("division.in", "r", stdin);freopen("division.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);string s;int d;cin >> s >> d;int e = 1;while (d % 2 == 0) {d /= 2;e *= 2;}while (d % 5 == 0) {d /= 5;e *= 5;}int n = s.size();vector<int> a(n + 1);for (int i = 0; i < n; ++i) {a[i + 1] = (a[i] * 10 + (s[i] - '0')) % (d * e);}int inv10 = d == 1 ? 0 : inverse(10, d);vector<int> pw(n + 1);pw[0] = 1;for (int i = 0; i < n; ++i) {pw[i + 1] = (long long) pw[i] * inv10 % d;}vector<int> base(20);base[0] = 1;for (int i = 0; i + 1 < 20; ++i) {base[i + 1] = base[i] * 10 % (d * e);}vector<num> foo(n + 1), bar(n + 1);vector<num> offset_foo(d), offset_bar(d);bar[0] = 1;num pref = 0;for (int i = 0; i <= n; ++i) {foo[i] += pref;if (a[i] % e == 0) {foo[i] += offset_foo[(long long) a[i] * pw[i] % d];bar[i] += offset_bar[(long long) a[i] * pw[i] % d];}pref += bar[i];offset_foo[(long long) a[i] * pw[i] % d] -= bar[i];offset_bar[(long long) a[i] * pw[i] % d] += foo[i] + bar[i];for (int j = i + 1; j <= n && j < i + 20; ++j) {if ((a[j] - (long long) a[i] * base[j - i]) % (d * e) == 0) {foo[j] -= bar[i];bar[j] += foo[i] + bar[i];}if (a[j] % e == 0 && (long long) a[i] * pw[i] % d == (long long) a[j] * pw[j] % d) {foo[j] += bar[i];bar[j] -= foo[i] + bar[i];}}}cout << foo[n] + bar[n] << "\n"; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【无码专区2】序列划分（数学）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。