題解 [校內測試]圖森破

題意

設 $f(n)$ 爲知足如下條件的字符串個數：html

1. 串長爲 $S$，字符集爲 $[0,9]$。
2. 設 $suf_i$ 爲第 $i$ 個字符對應的後綴在最後補 $0$ 補成長度爲 $n$ 獲得的串，則 $\forall i\in [2,n], suf_i>suf_1$

試求 $\sum_{i=1}^n i^2f(i)$ 模 $258280327$ 獲得的值。c++

組合

試求 $f(n)$。web

首先考慮長度爲 $n$ 的答案是什麼。app

首先全部循環節小於 $n$ 的串是不合法的，這十分顯然。svg

而後對於一個不具備循環節的串，咱們能夠轉它（ $\text{newS}_{i\%n +1}\leftarrow S_i$），能夠轉出 $n$ 個互不相同的串。下面咱們證實這 $n$ 個串中有且僅有一個是合法的。spa

1. 這 $n$ 個串中至少有一個是合法的：

考慮設 $S$ 爲 $n$ 個串中字典序最小的串，若它不合法，則存在一個後綴 $B< S$。因爲 $S$ 是字典序最小的，所以 $B$ 的長度不超過 $\lfloor \frac{n}{2}\rfloor$。3d

因爲 $S$ 是字典序最小的，所以若是設 $S$ 去掉 $B$ 爲 $A$，則 $B$ 是 $A$ 的前綴。

而後考慮轉到 $B$ 的字符串。

因爲 $S$ 是字典序最小的，所以對應字符存在以下關係：code

此時紅色後綴循環移位後獲得orm

2. 這 $n$ 個串中至多有一個是合法的：

假設有兩個串合法，設爲 $S_1,S_2$，考慮 $S_2$ 設 $S_2$ 在 $S_1$ 中的位置的後綴是 $F_2$，另外一個是 $F_1$，知 $S_2\ge F_2,S_1\ge F_1$（補 0），而 $S_2< F_1,S_1< F_2$ （定義），故 $S_2\ge F_2>S_1\ge F_1$，與 $S_2< F_1$ 矛盾！xml

所以咱們只須要算循環節等於 $n$ 的串的個數，設爲 $g(n)$。

事實上這很是好算啊！易知 $\sum_{d|n} g(d)=10^n$，因此 $g(n)=\sum_{d|n} 10^{\frac{n}{d}}\times \mu(d)$ （莫比烏斯反演）！

$f(n)=\frac{1}{n}\sum_{d|n} 10^{\frac{n}{d}}\times \mu(d)$

數論

$\begin{aligned} & \sum_{n=1}^N n \sum_{d|n} \mu(\frac{n}{d})10^{d} \\ &= \sum_{d=1}^N d10^d \sum_{n=1}^{N/d} n\mu(n) \end{aligned}$

注意到這是杜教篩簡單題，所以 $\Theta(n^{2/3}\log n)$ 求解。（能夠 $\Theta(n^{2/3})$，只須要把 map 和算 sum(i¹⁰i) 換掉，前者能夠只記憶化 i 而不是 N/i，後者能夠分塊預處理來 O(1) 算 10^n）

代碼

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

typedef long long ll;

const int NN = 5000000;
const int MOD = 258280327;
int mu[NN + 5], P[NN + 5], pl;
ll sum[NN + 5], ans, N;
bool np[NN + 5];
map<ll, ll> M;

ll power(ll a, ll b, ll p = MOD) {
	ll ret = 1; a %= p;
	for (; b; a = a * a % p, b >>= 1) if (b & 1) ret = ret * a % p;
	return ret;
}

const ll inv2 = power(2, MOD - 2), inv9 = power(9, MOD - 2);

ll getS(ll n) {
	if (n <= NN) return sum[n];
	if (M.find(n) != M.end()) return M[n];
	ll s = 1;
	for (ll i = 2, j; i <= n; i = j + 1) {
		j = n / (n / i);
		s = (s - getS(n / i) * (i + j) % MOD * (j - i + 1) % MOD * inv2) % MOD;
	} M[n] = s; return s;
}

inline ll S(ll n) {
	ll pw = power(10, n + 1); n %= MOD;
	return (pw * n - (pw - 10) * inv9) % MOD * inv9 % MOD;
}
int main() {
	scanf("%lld", &N), mu[1] = 1;
	for (int i = 2; i <= NN; ++i) {
		if (!np[i]) P[++pl] = i, mu[i] = -1;
		for (int j = 1; j <= pl && i * P[j] <= NN; ++j) {
			np[i * P[j]] = 1;
			if (i % P[j]) mu[i * P[j]] = mu[i] * mu[P[j]];
			else { mu[i * P[j]] = 0; break; }
		}
	}
	for (int i = 1; i <= NN; ++i) sum[i] = (sum[i - 1] + i * mu[i]) % MOD;
	getS(N);
	for (ll i = 1, j; i <= N; i = j + 1) {
		 j = N / (N / i);
		 ans = (ans + getS(N / i) * (S(j) - S(i - 1))) % MOD;
	}
	printf("%lld\n", (ans + MOD) % MOD);
	return 0;
}