• 欢迎光临~

# 暑假集训七

## 和迪哥推了一个多小时，终于被贯通了

• 方法一
here
``````#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD long double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(long long x = y; x <= z; x ++)
#define fp(x, y, z)for(long long x = y; x >= z; x --)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr pair<long long, long long>
#define mk(x, y) make_pair(x, y)
using namespace std;
namespace kiritokazuto{
LL x = 0;
int f = 1;
char c;
while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
return x * f;
};
template <typename T> fuc(void, write)(T x){
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10); putchar(x % 10 | '0');
}
}

using namespace kiritokazuto;

bool Mbg = false;
const int maxn = 1e7 + 1000, Mod = 998244353;
const int Inf = 2147483647;
bool Med = true;
//先打个暴力,等会用来拍把
int per[maxn];
int pos;
int turn;
int t, n;
int vis[maxn];
int cnt;
int main(){
// frein(data);
// freout(A);
int x = 0;
while (t--){
x = 0;
fr(i, 2, n) x = (n - i + 1 + x) % i;
write(x + 1);
ki;
}

// if (1.0 * (&Mbg - &Med) / 1024 / 1024 > 0.1) fprintf(stderr, "memo: %lf MBn", 1.0 * (&Mbg - &Med) / 1024 / 1024);
// else fprintf(stderr, "memo: %lf KBn", 1.0 * (&Mbg - &Med) / 1024);
// fprintf(stderr, "time: %lf sn", 1.0 * (clock() - _tme) / CLOCKS_PER_SEC);
}
``````
• 解释一下那个柿子
• 假设我上一把死的人的位置在(x),即它上一把的编号为(x),那么我序列总共还剩下两种数字
• (id > x)
• (id < x)
• 考虑他们在新序列里边的编号
• (id > x) (id_{new} = id - x)
• (id < x) (id_{new} = id - n_{old} + x)
• 手摸一下很显然
• 然后我们就可以考虑将两个柿子合并,
因为(id > x)(id - x)一定大于(0),所以它加一个(n_{old})再模一个(n_{old})值是不变的,所以两个柿子可以都合并为

[ id_{new} = (id - n_{old} + x) % n_{old} ]