|
首先：暴力！40分略，大家都会 但是 暴力的另一个用处：打表！为什么打表呢？因为$2≤n,k≤10^{12}$。 所以时间是O(1)。 要找数学规律。 打表：（输出的是没有被淘汰的人）
6 2 1 2 3 4 5 6 2 4 6 4
8 3 1 2 3 4 5 6 7 8 2 3 5 6 8 3 5 8 5 8 8
注意到：每次剩下人中第一个人是有规律的，而且到最后一定只剩一个人（也是当前剩余人中的第一个），更重要的是，这个人的编号就是我们求的答案！！!
设每次的第一个人依次是$x_1$,$x_2$,$x_3$,......,$x_m$。m是轮数。 则有$x_i+\lceil \frac{x_i}{k-1} \rceil=x_{i+1}$。 （这个需要自己找） 于是初始$x_1=1$ ，然后往后找。
#include<iostream>
using namespace std;
long long ans,n,k;//ans就是x
int main(){
scanf("%lld%lld",&n,&k);
ans=k;//前k个是依次作开头的，所以从k开始也一样
while(ans+(ans+k-2)/(k-1)<=n){
ans+=(ans+k-2)/(k-1);//套公式
}
printf("%lld",ans);//最后的开头就是最后一个人
return 0;
}
嗯。于是就过关了！But，洛谷上有个大佬出了个Hack，几乎把当时所有AC干成UAC了，这份代码也不例外。就是这个
1000000000000 10000000000
999999999907
会超时。 分块优化：于是我们继续想：每一轮都是一个人一个人淘汰的，所以我们对这一点进行优化…… 因为$x_i+\lceil \frac{x_i}{k-1} \rceil=x_{i+1}$ ，所以按$k-1$分块（$k-1$分母，按$x_i$与$k-1$的关系分块，这样每个块的跳跃次数都是一样的)，批量跳跃被淘汰数。
将整个数域$[1,n]$按每块$k−1$个数划分成若干块： 第 $1$ 块：$[1,k−1]$ 第 $2$ 块：$[k,2(k−1)]$ 第 $id$ 块：$[(id−1)(k−1)+1,id(k−1)]$ 同一区块内的被淘汰数，递推的步长$\lceil \frac{x_i}{k-1} \rceil$是固定的（等于块编号 $id$），因此可以批量计算该块内的所有被淘汰数，一次跳跃，无需逐个计算。
在第$id$块中，$\lceil \frac{x_i}{k-1} \rceil$（$x$ 属于第 $id$ 块），因此递推式简化为：$x_{next}=x+id$ 这意味着在第 $id$ 块中，被淘汰数是以$id$为步长递增的，可以直接计算出该块内最后一个被淘汰数，一次跳到下一块，大幅减少计算次数。
正片开始#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
ll n,k;
ll x=1,last_val;//x为当前待检查的被淘汰数，初始为第一个被淘汰数x1=1
//last_val是当前块中最后被淘汰的数（答案），不断更新，最终输出
int main(){
scanf("%lld%lld",&n,&k);
while(x<=n){
ll id=(x-1)/(k-1)+1;//是当前x所在块的编号
ll end=min(n,(k-1)*id);//当前块的末尾
x+=((end-x)/id+1)*id;//直接跳到当前块的末尾或跳出当前块
last_val=x-id;//计算当前块最后一个淘汰的数，也可能是所有之中的最后一个淘汰的数（即答案）
}
printf("%lld",last_val);
return 0;
}
OK
题目4322 [常州市赛 2025] 金币
评论
2026-02-28 14:42:32
|
|
|
更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19651912
大意 现在有多堆石子，其中第 $k$ 堆石子有 $p_k$ 个，先后手轮流操作。取石子时，可以选任意一堆进行操作。若记 $i$ 为在这次取之前这堆石子的个数，$j$ 为这次要取的石子数，$R$ 为给定的常数，则需满足以下条件： $$1 \leq i + j \leq R,i \geq j \geq 1$$ 使对方无法操作者即为胜者。
思路 我们首先考虑这个玩意的 $SG$ 函数，太坑了，你们可以手动的模一下。 我们来假设 $R = 5$ 的情况，首先 $SG(0) = 0$，$SG(1) = 1$，$SG(2) = 2$，但是我们发现，当 $i = 3$ 的时候，能取的只有 $1, 2$，取这两坨只会把必胜态留给对面，那这个时候的 $SG(3) = 0$，那再看 $SG(4) = 1$，然后 $SG(5) = 0$，当 $i \ge R$ 的时候 $SG(i) = 0$，这是显然的。 我们对于这个继续看其规律，不难通过注意或者推理得知，当且仅当 $i \le \lfloor \frac{R}{2} \rfloor$ 的时候，$SG(i) = i$，实际上就是简单的 Nim 博弈，但是一旦到达 $\lfloor \frac{R}{2} \rfloor + 1$，则 $SG(\lfloor \frac{R}{2} \rfloor + 1) = 0$，这是巧合吗？显然不是，但是只有这一个转折点吗？ 我赛时最初的思路是 $SG(i) = i \pmod {\lfloor \frac{R}{2} \rfloor + 1}$，可是真的对吗？不难发现当 $R = 100$ 时，转折点在 $\lfloor \frac{R}{2} \rfloor + 1 = 51$，但是当 $i = 76$ 的时候呢？我们只能取 $24$，也就是只能取到 $[52, 75]$ 这个区间，而这个区间的 $SG$ 是 ${1, 2, 3, \cdots 24}$，所以 $SG(76) = 0$，所以我刚刚的结论是错误的，继续向后模拟，发现在 $SG(89) = 0$，不难发现，什么时候等于 $0$ 呢，我们设 $pos$ 表示上次的位置，那么有： $$nxt = \lfloor \frac{pos + R}{2} \rfloor + 1$$ 这个说明了，我们的 $SG$ 是一段一段的，最多有 $\log$ 段，故我们可以直接向后跳，提前预处理所有段，在查询的时候直接二分所在段，$\mathcal{O}(1)$ 处理询问即可。
代码
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define ll long long
const int MAXN = 64;
ll R, lst[MAXN], val[MAXN];
int cnt;
inline ll Xor(ll n){
switch(n % 4){
case 1:
return n - 1;
case 2:
return 1;
case 3:
return n;
default:
return 0;
}
}
void init(ll x){
cnt = 0;
lst[0] = 0;
ll now = x / 2 + 1;
val[0] = Xor(now);
while(now < x){
lst[++ cnt] = now;
ll nxt = (now + x) / 2 + 1;
val[cnt] = val[cnt - 1] ^ Xor(nxt - now);
now = nxt;
}
}
ll ask(ll p){
int idx = upper_bound(lst, lst + cnt + 1, p) - lst - 1;
return (idx ? val[idx - 1] : 0) ^ Xor(p - lst[idx] + 1);
}
int main(){
// freopen("orange.in", "r", stdin);
// freopen("orange.out", "w", stdout);
cin.tie(0) -> ios::sync_with_stdio(0);
int T; cin >> T;
while(T --){
string op; cin >> op;
if(op == "change"){
cin >> R; init(R);
}
else{
int n; cin >> n;
ll ans = 0;
while(n --){
ll l, r; cin >> l >> r;
ans ^= ask(r) ^ ask(l - 1);
}
cout << (ans ? "1" : "0");
}
}
return 0;
}
题目4321 这是一道橙题
 2
评论
2026-02-28 13:32:57
|
|
|
更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19648636
大意 区间加，求 $a[l]^{a[l+1]^{a[l+2]^{\dots ^{a[r]}}}} \mod p$ 的值。
思路 对于这个指数塔，非常逆天，我们首先想到的肯定的是与降幂有关的内容，也就只有欧拉定理了，由于 $p$ 并非是质数，我们需要用扩展欧拉定理，那么什么是欧拉定理和扩展欧拉呢？ $\varphi(n)$ 就表示小于等于 $n$ 与 $n$ 互质的数的个数，$\varphi(1) = 1, \varphi(p) = p - 1$，这里的 $p$ 是质数。那么 $\phi(n)$ 应该怎么算呢？我们由素数分解定理，就可以有这样的公式： $$n \prod_{p | n} (1 - \frac{1}{p})$$ 这个过程我们是可以用线性筛预处理这个 $\varphi(n)$ 的。 好的，预处理讲完了，接下来讲欧拉定理，当 $\gcd(a, m) = 1$，那么 $a ^ {\varphi(m)} \equiv 1 \pmod m$，这个在模数为质数的时候就可以快速降幂，但是要是不是质数呢？没事，我们有扩展欧拉定理，其内容如下： $$a ^ b \equiv \begin{cases} a ^ {b \pmod{\varphi(m)}} & \gcd(a, m) = 1 \\ a ^ b & \gcd(a, m) \neq 1, b < \varphi(m) \\ a ^ {b \pmod{\varphi(m)} + \varphi(m)} & \gcd(a, m) \neq 1, b \ge \varphi(m) \end{cases} \pmod{m}$$ 好了，知道了这些，我们回到这个题目，对于这个指数塔，其指数一直取 $\varphi$ 显然最后会变成 $1$，那么要取多少次呢？我们想想对于 $\varphi(2 ^ k)$ 来说，其等于 $2 ^ {k - 1}$，对于质数是 $p - 1$，其如果是质数就减去一变成偶数，然后就会很快变小。 那么我们这个题直接写递归的话，递归层数最多就是 $\log$ 的层级，我们为了维护区间加和单点查询，我们直接用个树状数组维护即可，在递归的过程中，不断判断模数是否为 $1$，注意快速幂的地方，也要改一下。
代码
#include<iostream>
using namespace std;
#define int long long
const int MAXN = 2 * 1e7 + 5;
int a[MAXN], n, m;
int pri[MAXN], phi[MAXN], tot = 0;
int sum[MAXN];
bool vis[MAXN];
void init(){
phi[1] = 1;
for(int i = 2;i < MAXN;i ++){
if(!vis[i]){
phi[i] = i - 1;
pri[++ tot] = i;
}
for(int j = 1;j <= tot && i * pri[j] < MAXN;j ++){
vis[i * pri[j]] = 1;
if(i % pri[j] == 0){
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
}
}
// for(int i = 1;i < 5;i ++){
// cout << phi[i] << ' ';
// }
}
int lowbit(int x){
return x & -x;
}
void add(int x, int k){
while(x <= n){
sum[x] += k;
x += lowbit(x);
}
}
int ask(int x){
int res = 0;
while(x){
res += sum[x];
x -= lowbit(x);
}
return res;
}
int qpow(int a, int b, int p){
int res = 1;
bool flag = 0;
if(a >= p){
flag = 1;
a %= p;
}
while(b){
if(b & 1) res = res * a;
if(res >= p){
res %= p;
flag = 1;
}
a = a * a;
if(a >= p){
a %= p;
flag = 1;
}
b >>= 1;
}
return flag ? res + p : res;
}
int solve(int l, int r, int p){
int val = a[l] + ask(l);
if(p == 1) return 1;
if(l == r){
if(val >= p) return val % p + p;
else return val;
}
int cnt = solve(l + 1, r, phi[p]);
return qpow(val, cnt, p);
}
signed main(){
cin.tie(0) -> ios::sync_with_stdio(0);
init();
cin >> n >> m;
for(int i = 1;i <= n;i ++){
cin >> a[i];
}
for(int i = 1;i <= m;i ++){
int op, l, r, x;
cin >> op >> l >> r >> x;
if(op == 1) add(l, x), add(r + 1, -x);
else cout << solve(l, r, x) % x << '\n';
}
return 0;
}
题目4228 [Ynoi Easy Round 2016] Nephren Ruq Insania
2
评论
2026-02-28 13:31:34
|
|
|
更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19648636
大意 区间加，求 $a[l]^{a[l+1]^{a[l+2]^{\dots ^{a[r]}}}} \mod p$ 的值。
思路 对于这个指数塔，非常逆天，我们首先想到的肯定的是与降幂有关的内容，也就只有欧拉定理了，由于 $p$ 并非是质数，我们需要用扩展欧拉定理，那么什么是欧拉定理和扩展欧拉呢？ $\varphi(n)$ 就表示小于等于 $n$ 与 $n$ 互质的数的个数，$\varphi(1) = 1, \varphi(p) = p - 1$，这里的 $p$ 是质数。那么 $\phi(n)$ 应该怎么算呢？我们由素数分解定理，就可以有这样的公式： $$n \prod_{p | n} (1 - \frac{1}{p})$$ 这个过程我们是可以用线性筛预处理这个 $\varphi(n)$ 的。 好的，预处理讲完了，接下来讲欧拉定理，当 $\gcd(a, m) = 1$，那么 $a ^ {\varphi(m)} \equiv 1 \pmod m$，这个在模数为质数的时候就可以快速降幂，但是要是不是质数呢？没事，我们有扩展欧拉定理，其内容如下： $$a ^ b \equiv \begin{cases} a ^ {b \pmod{\varphi(m)}} & \gcd(a, m) = 1 \\ a ^ b & \gcd(a, m) \neq 1, b < \varphi(m) \\ a ^ {b \pmod{\varphi(m)} + \varphi(m)} & \gcd(a, m) \neq 1, b \ge \varphi(m) \end{cases} \pmod{m}$$ 好了，知道了这些，我们回到这个题目，对于这个指数塔，其指数一直取 $\varphi$ 显然最后会变成 $1$，那么要取多少次呢？我们想想对于 $\varphi(2 ^ k)$ 来说，其等于 $2 ^ {k - 1}$，对于质数是 $p - 1$，其如果是质数就减去一变成偶数，然后就会很快变小。 那么我们这个题直接写递归的话，递归层数最多就是 $\log$ 的层级，我们为了维护区间加和单点查询，我们直接用个树状数组维护即可，在递归的过程中，不断判断模数是否为 $1$，注意快速幂的地方，也要改一下。
代码
#include<iostream>
using namespace std;
#define int long long
const int MAXN = 2 * 1e7 + 5;
int a[MAXN], n, m;
int pri[MAXN], phi[MAXN], tot = 0;
int sum[MAXN];
bool vis[MAXN];
void init(){
phi[1] = 1;
for(int i = 2;i < MAXN;i ++){
if(!vis[i]){
phi[i] = i - 1;
pri[++ tot] = i;
}
for(int j = 1;j <= tot && i * pri[j] < MAXN;j ++){
vis[i * pri[j]] = 1;
if(i % pri[j] == 0){
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
}
}
// for(int i = 1;i < 5;i ++){
// cout << phi[i] << ' ';
// }
}
int lowbit(int x){
return x & -x;
}
void add(int x, int k){
while(x <= n){
sum[x] += k;
x += lowbit(x);
}
}
int ask(int x){
int res = 0;
while(x){
res += sum[x];
x -= lowbit(x);
}
return res;
}
int qpow(int a, int b, int p){
int res = 1;
bool flag = 0;
if(a >= p){
flag = 1;
a %= p;
}
while(b){
if(b & 1) res = res * a;
if(res >= p){
res %= p;
flag = 1;
}
a = a * a;
if(a >= p){
a %= p;
flag = 1;
}
b >>= 1;
}
return flag ? res + p : res;
}
int solve(int l, int r, int p){
int val = a[l] + ask(l);
if(p == 1) return 1;
if(l == r){
if(val >= p) return val % p + p;
else return val;
}
int cnt = solve(l + 1, r, phi[p]);
return qpow(val, cnt, p);
}
signed main(){
cin.tie(0) -> ios::sync_with_stdio(0);
init();
cin >> n >> m;
for(int i = 1;i <= n;i ++){
cin >> a[i];
}
for(int i = 1;i <= m;i ++){
int op, l, r, x;
cin >> op >> l >> r >> x;
if(op == 1) add(l, x), add(r + 1, -x);
else cout << solve(l, r, x) % x << '\n';
}
return 0;
}
题目4318 数据结构题
2
评论
2026-02-28 13:30:07
|
|
|
# T5 数据结构题 题解 我们将询问转化为如下问题 定义 $f(l,r)$ $(l \le r)$ 如下： 当 $l=r$ 时，$f(l,r)=a_l$；否则，$f(l,r)=a_l^{f(l+1,r)}$ 每次操作 $2$，输出 $f(l,r)\bmod p$ 那我们该如何维护呢？ 这里我们需要一个前置知识，叫做扩展欧拉定理，即： $$a^b\equiv \begin{cases}a^{b \bmod \varphi(p)}(b<\varphi(p))\\a^{b \bmod \varphi(p)+\varphi(p)}(b\ge\varphi(p))\end{cases}\pmod p$$ 那么 $$f(l,r)\equiv a^{f(l+1,r)\bmod \varphi(p)+[b\ge \varphi(p)]\times \varphi(p)}\pmod p$$ 那么，求解 $f(l,r)\bmod p$ 就变成了求解 $f(l+1,r)\bmod \varphi(p)$，并判断 $f(l+1,r)$ 与 $p$ 的关系 然后我们就可以递归求解了 递归边界的话，则有三个 当 $l=r$ 时，$f(l,r)\bmod p\equiv a_l\pmod p$ 当 $p=1$ 时，$f(l,r)\bmod p\equiv 0\pmod p$ 当 $a_l=1$ 时，$f(l,r)\bmod p\equiv 1\pmod p$ 那么这个递归的复杂度是多少呢？ 我们分析一下将 $\varphi(p)\to p$ 直到 $p=1$ 的时间复杂度是多少 由 $\varphi(p)=p\prod_{i=1}^{n} \frac{p_i-1}{p_i}$ $(p=\prod_{i=1}^{n}{p_i}^{k_i})$可知 当 $p$ 为偶数时，上述式子必有一项是 $\frac{1}{2}$，所以 $\varphi(p)\le\frac{1}{2}p$ 当 $p$ 为奇数时，上述式子的 $p_i-1$ 必是偶数，因此 $\varphi(p)$ 为偶数，回到 $p$ 为偶数的情况 因此最多经过 $O(logn)$ 次递归就可以得出答案 至于判断 $f(l+1,r)$ 与 $p$ 的关系，可以让递归函数返回一个结构体，结构体第一项存 $f(l+1,r)\bmod \varphi(p)$ 的值，第二项存 $f(l+1,r)$ 与 $\varphi(p)$ 的大小关系，前者大于等于后者，这一项就是 $1$，反之则为 $0$ 区间和我们用树状数组维护差分即可 时间复杂度：$O(mlogqlogn)$
题目4318 数据结构题
AAAAAAAAAA
评论
2026-02-28 13:04:35
|
|
|
题目4323 十二重计数法(第一关)
AAAAA
4
评论
2026-02-27 20:33:10
|