\(\textbf{G.}\)
- 当 \(a = 0\) 时有 \(x _ i = \begin{cases} s &, i = 0 \\ b &, i \geq 1 \end{cases}\). 所以可以 \(\mathcal{O}(1)\) 计算.
- 当 \(a = 1\) 时有 \(x _ i = s + i b \bmod {p}\). 所以 \(i \equiv \dfrac{g - s}{b} \pmod{p}\), 可以 \(\mathcal{O}(1)\) 计算.
- 当 \(a \geq 2\) 时有 \(x _ i + \dfrac{b}{a - 1} \equiv a \left( x _ {i - 1} + \dfrac{b}{a - 1} \right) \pmod{p}\). 所以 \(a ^ i \equiv \dfrac{g + \dfrac{b}{a - 1}}{s + \dfrac{b}{a - 1}} = \dfrac{(a - 1) g + b}{(a - 1) s + b} \pmod{p}\), 可以使用
BSGS在 \(\mathcal{O}(\sqrt p)\) 内计算.
所以就做完了, 注意取模的细节问题. 单次复杂度 \(\mathcal{O}(\sqrt{p})\).
int bsgs(modint a, modint b){ /* 解方程 a ^ i = b */
if(a.val() == 0 && b.val() == 0)
return 1;
if(a.val() == 0 && b.val() != 0){
if(b.val() == 1)
return 0;
else
return -1;
}
if(a.val() != 0 && b.val() == 0)
return -1;
const int S = sqrt(mod);
map<int, int> mp;
for(int i = 0; i < S; i ++)
mp[(b * a.qpow(i)).val()] = i;
for(int j = S; j <= mod - 1; j += S)
if(mp.count(a.qpow(j).val()))
return j - mp[a.qpow(j).val()];
return -1;
}
void solve(){
int A, B, S, G;
cin >> mod >> A >> B >> S >> G;
if(G == S){
cout << 0 << "\n";
return;
}
if(A == 0){
if(S == G)
cout << 0 << "\n";
else if(G == B)
cout << 1 << "\n";
else
cout << -1 << "\n";
return;
}
if(A == 1){
ll P = G - S;
ll Q = B;
ll R = __gcd(P, Q);
P /= R, Q /= R;
if(Q % mod == 0){
cout << -1 << "\n";
return;
}
cout << (modint(P) / modint(Q)).val() << "\n";
return;
}
ll P = (ll)(A - 1) * G + B;
ll Q = (ll)(A - 1) * S + B;
ll R = __gcd(P, Q);
P /= R, Q /= R;
if(Q % mod == 0){
cout << -1 << "\n";
return;
}
cout << bsgs(modint(A), modint(P) / modint(Q)) << "\n";
}
\(\textbf{H.}\)
考虑对于当前的局面 \((b _ 1, \cdots, b _ n)\), 定义 \(k(b _ 1, \cdots, b _ n) = \max(\max(0, a _ i - b _ i) : 1 \leq i \leq n)\) 表示当前状态和终止状态的距离.
考虑设 \(f(k)\) 表示距离为 \(k\) 的状态期望需要多少步到达终止状态. 则 \(f(0) = 0\); 答案为 \(f(a _ n)\). 考虑转移:
-
若选择 \(a _ i < k\) 的下标 \(i\). 那么得到状态的距离为 \(k' = \max (a _ i, \max(a _ j - b _ j - 1 : j \neq i)) = \max(a _ i, k - 1) = k - 1\).
其中用到 \(\max(a _ j - b _ j - 1 : j \neq i) = \max(a _ j - b _ j : j \neq i) - 1\), 而对于 \(a _ i - b _ i < k\), 所以 \(\max(a _ j - b _ j : j \neq i) = k\).
-
若选择 \(a _ i \geq k\) 的下标 \(i\). 那么得到状态的距离为 \(k' = \max (a _ i, \max(a _ j - b _ j - 1 : j \neq i)) = a _ i\).
其中用到 \(\max(a _ j - b _ j - 1 : j \neq i) \leq \max(a _ j - b _ j - 1 : j) = k - 1 < a _ i\).
所以 \(f(k) = 1 + \dfrac{1}{n} \sum _ {i = 1} ^ {n} [a _ i < k] f(k - 1) + [a _ i \geq k] f(a _ i)\).
考虑设 \(a _ 1 \leq \cdots \leq a _ l < k \leq a _ {l + 1} \leq \cdots \leq a _ n\). 那么转移重写为 \(f(k) = 1 + \dfrac{l}{n} f(k - 1) + \dfrac{1}{n} \sum _ {i = l + 1} ^ {n} f(a _ i)\).
于是 \(f(k - 1) = \dfrac{1}{l} \left( n f(k) - n - \sum _ {i = l + 1} ^ {n} f(a _ i) \right)\).
用 \(k\) 替换 \(k - 1\) 得到 \(f(k) = \dfrac{1}{l} \left( n f(k + 1) - n - \sum _ {i = l + 1} ^ {n} f(a _ i) \right)\), 其中 \(a _ l \leq k < a _ {l + 1}\).
注意到此时边界为 \(f(0) = 0\); 答案为 \(f(a _ n)\). 这和转移的顺序不符合.
所以只需令 \(g(k) = f(a _ n) - f(k)\). 那么转移变为 \(g(k) = \dfrac{1}{l} \left( n g(k + 1) + n - \sum _ {i = l + 1} ^ {n} g(a _ i) \right)\); 边界为 \(g(a _ n) = 0\); 答案为 \(g(0)\).
直接计算预处理逆元和前缀和优化是 \(\mathcal{O}(n + V)\) 的. 考虑优化.
考虑固定 \(l\), 对于所有 \(a _ l \leq k < a _ {l + 1}\) 转移形式相同, 所以考虑设 \(G = \dfrac{n - \sum _ {i = l + 1} ^ {n} g(a _ i)}{l}\) 是定值.
那么 \(\begin{array}{l} g(a _ l) &= \dfrac{n}{l} g(a _ l + 1) - G = \dfrac{n}{l} \left( \dfrac{n}{l} g(a _ l + 2) - G \right) - G = \left( \dfrac{n}{l} \right) ^ 2 g(a _ l + 2) - G \left( 1 + \dfrac{n}{l} \right) \\ &= \cdots = \left( \dfrac{n}{l} \right) ^ {a _ {l + 1} - a _ l} g(a _ {l + 1}) - G \left( 1 + \dfrac{n}{l} + \cdots \left( \dfrac{n}{l} \right) ^ {a _ {l + 1} - a _ l - 1} \right) = \left( \dfrac{n}{l} \right) ^ {a _ {l + 1} - a _ l} g(a _ {l + 1}) - G \dfrac{1 - \left( \dfrac{n}{l} \right) ^ {a _ {l + 1} - a _ l}}{1 - \dfrac{n}{l}} \end{array}\).
于是每次只需依次计算 \(g(a _ {n - 1}), \cdots, g(a _ 1) = g(0)\) 即可. 使用前缀和优化即可做到 \(\mathcal{O}(n \log \mathrm{mod})\).
所以就做完了.
void solve(){
int n;
cin >> n;
vector<ll> a(n + 1);
for(int i = 1; i <= n; i ++)
cin >> a[i];
vector<modint> x(n + 1);
x[n] = modint(0);
modint S(0);
for(int i = n - 1; i >= 1; i --){
modint Y = (S - modint(n)) / modint(i);
modint Z = modint(n) / modint(i);
x[i] = Z.qpow(a[i + 1] - a[i]) * x[i + 1] - Y * (modint(1) - Z.qpow(a[i + 1] - a[i])) / (modint(1) - Z);
S += x[i];
}
cout << x[1].val() << "\n";
}