自动搬运

查看原文

来自洛谷，原作者为

	251Sec 祈祷着今后的你的人生，永远都有幸福的“魔法”相伴。

搬运于2025-08-24 22:38:52，当前版本为作者最后更新于2024-09-02 19:29:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单题，咋没人写题解。

不难得到一个暴力 DP 形如 $f(n,c,l_1,l_2,l_3,0/1,0/1)$，即已经填了 $n$ 位，最后一位为 $c$，结尾相等、上升、下降的长度为 $l_{1..3}$，是否已经选出了字母，是否已经选出了数字的方案数。这个 DP 太炸裂了，不过我们再观察一下：$l_{1..3}$ 至多有一个不是 $1$，$c$ 为大写字母和小写字母的状态是等价的，最后两个 $0/1$ 实际上只需要记一个代表是否存在一个位置左侧和右侧分别为字母和数字。所以状态数瞬间就少了很多，只有几千种了，可以暴力 DP 前 $10^3$ 项。$l,r$ 很大，看起来就很线性递推，所以记录 $s(n)$ 代表长度 $\le n$ 的密码种类数，然后直接把它丢进 BM 一看发现递推式长度只有几百。那就做完了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 1e9 + 7;
ll QPow(ll a, ll b) {
	ll res = 1;
	for (; b; b >>= 1, a = a * a % P) if (b & 1) res = res * a % P;
	return res;
}
struct Poly {
	vector<ll> w;
	Poly() {}
	Poly(int sz) : w(sz) {}
	Poly(vector<ll> w) : w(w) {}
	ll &operator[](int i) { return w[i]; }
	ll operator[](int i) const { return w[i]; }
	int size() const { return w.size(); }
	void resize(int x) { w.resize(x); }
	Poly operator*(const Poly &b) const {
		Poly res(size() + b.size() - 1);
		for (int i = 0; i < size(); i++) {
			for (int j = 0; j < b.size(); j++) {
				res[i + j] += w[i] * b[j] % P;
			}
		}
		for (int i = 0; i < res.size(); i++) res[i] %= P;
		return res;
	}
	Poly operator%(const Poly &b) const {
		if (size() < b.size()) return *this;
		Poly a = *this;
		ll iv = QPow(b.w.back(), P - 2);
		int m = b.size() - 1;
		for (int i = size() - 1; i >= m; i--) {
			if (!a[i]) continue;
			ll w = a[i] * iv % P;
			for (int j = 0; j <= m; j++) (a[i - j] -= w * b[m - j] % P) %= P;
		}
		for (int i = 0; i < a.size(); i++) a[i] = (a[i] % P + P) % P;
		while (a.size() && !a.w.back()) a.w.pop_back();
		return a;
	}
};
namespace BM {
	vector<ll> cur, lst;
	ll del, fail;
	void UpdLst(vector<ll> t, ll tdel, ll tfail) {
		if ((int)t.size() - tfail < (int)lst.size() - fail) fail = tfail, del = tdel, lst = t;
	}
	vector<ll> Solve(ll *a, int n) {
		for (int i = 1; i <= n; i++) {
			ll d = a[i];
			for (int j = 0; j < cur.size(); j++) d -= a[i - j - 1] * cur[j] % P;
			d = (d % P + P) % P;
			if (!d) continue;
			vector<ll> tcur = cur;
			if (!fail) cur.resize(i);
			else {
				ll w = d * del % P;
				if (cur.size() < i - fail + lst.size()) cur.resize(i - fail + lst.size());
				(cur[i - fail - 1] += w) %= P;
				for (int j = 0; j < lst.size(); j++) (cur[i - fail + j] += (P - lst[j]) * w % P) %= P;
			}
			UpdLst(tcur, QPow(d, P - 2), i);
		}
		for (int i = 0; i < cur.size(); i++) cur[i] = (P - cur[i]) % P;
		reverse(cur.begin(), cur.end());
		cur.push_back(1);
		return cur;
	}
}
int l, r, a, b;
ll f[1005][36][26][2][3], s[1005];
void Upd(ll &x, ll y) { (x += y) %= P; }
ll Calc(Poly f, int n) {
	Poly a; a.resize(2), a[1] = 1;
	Poly res; res.resize(1), res[0] = 1;
	for (; n; n >>= 1, a = a * a % f) if (n & 1) res = res * a % f;
	ll ans = 0;
	for (int i = 0; i < res.size(); i++) ans += res[i] * s[i] % P;
	return ans % P;
}
int main() {
	scanf("%d%d%d%d", &l, &r, &a, &b);
	for (int i = 0; i < 36; i++) f[1][i][1][0][0] = 1 + (i > 9);
	for (int i = 1; i <= 1000; i++) {
		for (int j = 0; j < 36; j++) {
			for (int k = 1; k < 26; k++) {
				for (int x = 0; x < 2; x++) {
					for (int y = 0; y < 3; y++) {
						if (f[i][j][k][x][y] && ((!y && k < a) || (y && k < b))) {
							ll w = f[i][j][k][x][y];
							for (int z = 0; z < 36; z++) {
								if (z == j) Upd(f[i + 1][z][!y ? k + 1 : 2][x][0], w);
								else if (z == j + 1 && j != 9) Upd(f[i + 1][z][y == 1 ? k + 1 : 2][x][1], w);
								else if (z == j - 1 && j != 10) Upd(f[i + 1][z][y == 2 ? k + 1 : 2][x][2], w);
								else Upd(f[i + 1][z][1][x || ((j < 10) != (z < 10))][0], w);
								if (z > 9) Upd(f[i + 1][z][1][x || ((j < 10) != (z < 10))][0], w);
							}
							if (x) Upd(s[i], w);
						}
					}
				}
			}
		}
	}
	for (int i = 1; i <= 1000; i++) Upd(s[i], s[i - 1]);
	auto g = BM::Solve(s - 1, 1001);
	printf("%lld\n", (Calc(g, r) - Calc(g, l - 1) + P) % P);
	return 0;
}