简述
时隔一年之后再学一个新的筛法是不是没救了啊。
乍一看很难直接做,我们考虑从那个长度为 \(m\) 的串开始搞,发现每个 \(01\) 都对应的是一个不等式条件:
\[ a(s + i) + b < p \]
其中在 \(m\) 串的位置中为 \(i\),在 \(S\) 中的位置为 \(s + i\)。列了这么多之后进行区间交,然后发现性质 \(\gcd(a, n) = 1\),代表 \(ai \bmod n\) 是一一对应的,所以我们求最后的值的个数只需要减去 \([n – m + 1, n – 1]\) 内符合条件的数即可。
// P3589.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 1e6 + 200; int n, a, b, p, m, ltot; char str[MAX_N]; pair<int, int> limits[MAX_N << 2]; void create(int l, int r) { if (l <= r) limits[++ltot] = make_pair(l, r); else limits[++ltot] = make_pair(l, n - 1), limits[++ltot] = make_pair(0, r); } int main() { scanf("%d%d%d%d%d%s", &n, &a, &b, &p, &m, str); int ans = 0; for (int i = 0; i < m; i++) if (str[i] == '0') create((p + n - 1LL * i * a % n) % n, (0LL + n - 1 - 1LL * i * a % n) % n); else create((n - 1LL * i * a % n) % n, (p + n - 1LL * i * a % n - 1) % n); for (int i = 1; i < m; i++) create((0LL + b + n - 1LL * a * i % n) % n, (0LL + b + n - 1LL * a * i % n) % n); sort(limits + 1, limits + 1 + ltot); int tmp = -1; for (int i = 1; i <= ltot; i++) { if (limits[i].first > tmp) ans += limits[i].first - tmp - 1, tmp = limits[i].second; else tmp = max(tmp, limits[i].second); } printf("%d\n", ans + n - 1 - tmp); return 0; }
这转化也真是妙…
首先,我们把 \((-1)^b\) 进行转换。发现转换成跟数论相关:\((-1)^b = 1 – 2(b \bmod 2)\),则可以把这个式子弄一下:
自己推了三个假的循环,遂奔向题解。
先考虑设循环节为 \(k\),且考虑最终 \(x = 0, y = 0\) 的局势。我们考虑怎样的循环节才能迭代一次、得到同样的 \(x = 0, y = 0\) 的局势。不妨直接带入 \(k\):
\[ x = (k + \lfloor \frac{k}{B} \rfloor) \bmod A, y = k \bmod B \]
先写出答案的式子:
\[ \prod_{i = 1}^n \prod_{i = 1}^m f(\gcd(i, j)) \]
老套路,枚举公约数:
\[ \prod_{d = 1}^{\min(n, m)} f(d)^{\sum_{i = 1}^n \sum_{j = 1}^m [gcd(i, j) = d]} \]