\(1 \sim 100\) 的题目在 做题笔记 II。
\(\texttt{Le0**an}\)：我写了四篇做题笔记、一篇生成函数详解和一篇模拟赛复盘了！
\(\texttt{xl****13}\)：我写了零篇做题笔记了！！！111
\(101 \sim 125\)
\(\color{blue}(101)\) ARC172E Last 9 Digits
难度 \(^*2400\)。数论
抽象题。
有一个结论，对于 \(k \ge 2\)，若 $x \bmod 2 \ne0 $ 且 \(x \bmod 5 \ne 0\) 则 \(n^n \equiv x \pmod {10^k}\) 一定有唯一解。可以考虑打表验证。
考虑如果 \(n^n \equiv x \pmod {10^k}\)，则一定 \(n^n \equiv x \pmod {10^{k-1}}\)。那么我们从 \(k=2\) 开始，先暴力枚举找到 \(n^n \equiv x \pmod {10^{2}}\) 的 \(n\)，然后考虑 \(n,n+10^k,n+2\cdot 10^k,\ldots,n+9\cdot10^k\) 一定是 \(n^n \equiv x \pmod {10^{k+1}}\) 的所有可能解，暴力检验即可。时间复杂度 \(\mathcal O(\log^2 x)\)，带 \(10\) 倍常数。
代码
/**
* author: sunkuangzheng
* created: 20.02.2024 09:42:18
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
int T,n,x,pw[11],d;
int qp(int a,int b,int mod){
int r = 1;
for(;b;b >>= 1,a = 1ll * a * a % mod) if(b & 1) r = 1ll * r * a % mod;
return r;
}void los(){
cin >> x; int ans = -1;
for(int i = 0;i <= 99;i ++) if(qp(i,i,100) == x % 100) ans = i;
for(int i = 3;i <= 9;i ++)
for(int j = 0;j < 10;j ++)
if(d = ans + j * pw[i - 1],qp(d,d,pw[i]) == x % pw[i]) ans = d;
cout << ans << "\n";
}int main(){
ios::sync_with_stdio(0),cin.tie(0);
pw[0] = 1;
for(int i = 1;i <= 9;i ++) pw[i] = pw[i - 1] * 10;
for(cin >> T;T --;) los();
}
\(\color{blue}(102)\) ABC313G Redistribution of Piles
难度 \(^*2800\)。数学
首先先进行一次 \(2\) 操作再进行 \(1\) 操作没有意义，我们的操作序列形如 \(11\ldots 122\ldots 2\)。
考虑对 \(a\) 升序排序，如果当前所有数字都大于 \(0\)，那你先进行一次 \(1\) 再进行一次 \(2\) 也没有意义。设当前 \(a_{i-1}\) 已经等于 \(0\)，则背包里有 \(s = a_{i-1}(n-i+1)+\sum \limits_{j=1}^{i-1} a_j\) 个数字。设对 \(a_i\) 操作 \(k\) 次，则和会增加 \(k(n-i+1)\)，容易发现这些操作后序列互不相同。也就是说，我们会得到 \(\sum \limits_{k=1}^{a_i-a_{i-1}} \lfloor\dfrac{s+k(n-i+1)}{n} \rfloor\)，可以用 atcoder::floor_sum 求解。时间复杂度 \(\mathcal O(n \log m)\)。有一些实现细节。
代码
/**
* author: sunkuangzheng
* created: 20.02.2024 10:54:20
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5,mod = 998244353;
using namespace std;
#include <atcoder/all>
using Z = atcoder::modint998244353;
int T,n,a[N];
void los(){
cin >> n; Z ans = 0; ll sum = 0;
for(int i = 1;i <= n;i ++) cin >> a[i];
sort(a+1,a+n+1); ans = a[1] + 1;
for(int i = 1;i < n;i ++)
sum += a[i],
ans += atcoder::floor_sum(a[i + 1] - a[i] + 1,n,n - i,sum + 1ll * a[i] * (n - i)),
ans -= atcoder::floor_sum(1,n,n - i,sum + 1ll * a[i] * (n - i)),
ans += a[i + 1] - a[i];
cout << ans.val();
}signed main(){
ios::sync_with_stdio(0),cin.tie(0);
for(T = 1;T --;) los();
}