自动搬运

查看原文

来自洛谷，原作者为

	Composite_Function 复合函数

搬运于2025-08-24 23:11:09，当前版本为作者最后更新于2025-03-15 19:31:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

赛时没时间口胡的。赛后已复现。

---

首先考虑 $n$ 位数中选出 $i$ 个是 $0$ 或 $1$，$j$ 个是 $3$ 或 $4$，其余填 $2$。这样答案就是：

$$\sum_{i=2}^{n-1}\sum_{j=2}^{n-i-1}{{n-1}\choose{i}}{{n-i-1}\choose{j}}(i-1)(j-1) $$

分离并作简单的计算得到：

$$\sum_{i=2}^{n-1}{{n-1}\choose{i}}(i-1)\left(\sum_{j=2}^{n-i-1}\left((n-i-1){{n-i-2}\choose{j-1}}-{{n-i-1}\choose{j}}\right)\right) $$

进一步得到：

$$\sum_{i=2}^{n-1}{{n-1}\choose{i}}(i-1)\left((n-i-1)2^{n-i-2}-2^{n-i-1}+1\right) $$

即：

$$\sum_{i=2}^{n-1}\left((n-1){{n-2}\choose{i-1}}-{{n-1}\choose{i}}\right)\left((n-i-1)2^{n-i-2}-2^{n-i-1}+1\right) $$

然后我们如法炮制把上面的东西进一步拆开：

$$(2n^2-15n+22)3^{n-3}-(n^2-11n+18)2^{n-3}-n+2$$

就可以强行算了。常数极小。

当然如果你注意力惊人会知道算到这个地方的时候答案一定会是常数的幂乘以多项式，直接待定系数即可。

---

#include <bits/stdc++.h>
using namespace std;

struct FastIO {
	inline FastIO& operator >> (short& x) {
		x = 0;
		char f = 0, ch = getchar();
		while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
		while (ch <= '9' && ch >= '0') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
		return x = (f ? -x : x), *this;
	}
	inline FastIO& operator >> (int& x) {
		x = 0;
		char f = 0, ch = getchar();
		while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
		while (ch <= '9' && ch >= '0') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
		return x = (f ? -x : x), *this;
	}
	inline FastIO& operator >> (long long& x) {
		x = 0;
		char f = 0, ch = getchar();
		while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
		while (ch <= '9' && ch >= '0') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
		return x = (f ? -x : x), *this;
	}
	inline FastIO& operator >> (double& x) {
		x = 0;
		char f = 0, ch = getchar();
		double d = 0.1;
		while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
		while (ch <= '9' && ch >= '0') x = x * 10 + (ch ^ 48), ch = getchar();
		if (ch == '.') {
			ch = getchar();
			while (ch <= '9' && ch >= '0') x += d * (ch ^ 48), d *= 0.1, ch = getchar();
		}
		return x = (f ? -x : x), *this;
	}
} rin;

#define ll long long
#define uint unsigned int
#define reg register
#define ld long double
#define uint unsigned int
#define ull unsigned long long
#define qint const int&
#define qll const ll&
#define quint cosnt uint&
#define qull const ull&
#define endl "\n"

inline void qmod(int& x, const int& mod) {
	x = x >= mod? x - mod : x;
}

const int N = 1e7 + 10, mod = 1e9 + 7, Mod = mod - 1;
int l;
ll val, idx;
char ch[N];
inline int qpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod, b >>= 1;
	}
	return res;
}

signed main() {
	rin >> l, cin >> ch;
	if (l <= 1 && ch[0] <= '4') return puts("0"), 0;
	for (int i = 0; i < l; ++i) {
		val = ((val << 3) + (val << 1) + (ch[i] ^ 48)) % mod;
		idx = ((idx << 3) + (idx << 1) + (ch[i] ^ 48)) % Mod;
	}
	ll res = (2 * val * val - 15 * val + 22) % mod * qpow(3, idx - 3) % mod;
	res -= (val * val - 11 * val + 18) % mod * qpow(2, idx - 3) % mod;
	res = res - val + 2;
	res = (res % mod + mod) % mod;
	cout << res << endl;
	return 0;
}

拜谢 @Ruan_ji 提出的错误。