2020-牛客多校-6
有坑待补 具体数学 约瑟夫的Ok做法
B 线性无关的n维01向量个数
考虑每次加入元素时可取的元素个数。
假设当前已经取了i个线性无关向量，则它们可以张出一共$2^i$个向量，所以第i + 1个向量只有$2^n - 2 ^ i$种可取办法。
因而$f(n) = \prod_{i=0}^{n - 1}(2^n-2^i)/2^n$
推导可得递推关系:
$f(n) = (1 - 1/2^n)*f(n - 1)$
线性处理出来O1查询即可。
J 约瑟夫变换与置换
考虑一个k-约瑟夫变换，指的是将序列1, 2, ..., n变换到p1, p2, ..., pn，其中pi表示在约瑟夫过程中第i个出局的人的标号。
那么只要处理出k-约瑟夫变换的置换方案，就可以On地得知进行1e9次k-约瑟夫变换的结果。
所以为什么一直认为置换的幂次一定要倍增来nlogn的做出来qaq
因为nm <= 1e6,所以总共$O(nmlogn)$即可。
之前不会做xdoj1009，这次场上还是不会，不然这道题其实可以飞快的过掉。
wmx用了splay带大常数的处理出了一次k-约瑟夫变换的结果，然后TLE了牛客。
事实上可以用线段树直接更小常数的查询：
线段树维护每个元素存在的情况，存在则节点值为1，不然则值为0；支持单点修改和查询当前仍存在于线段树中的第k个元素。
如果当前有n个元素，需要查询从前往后第cnt个，直接用线段树就可以$O(logn)$查询出谁是下一个被淘汰出局的；接下来要更新$cnt$的值，淘汰完一人后在新的$n -1$长度的序列中被淘汰的人是该新序列的第几个，稍微推导研究一下就可以知道$cnt’ = (cnt + k - 2)% (n - i) + 1$，从1开始编号。反复进行上述操作即可。
1#define ls (p << 1)
2#define rs ((p << 1) | 1)
3#define mid ((l + r) >> 1)
4
5const itn maxn = 1e5 + 10;
6const int N = 20;
7int n, m;
8
9int st[maxn << 2];
10inline void up(int p){st[p] = st[ls] + st[rs];}
11void update(int p, int l, int r, int k, int op){
12 if(l == r && l == k){
13 st[p] += op;
14 return ;
15 }
16 if(k <= mid) update(ls, l, mid, k, op);
17 else update(rs, mid + 1, r, k, op);
18 up(p);
19}
20
21//查询第k个数
22int query(int p, int l, int r, int k){
23 if(l == r){ return l;}
24 if(st[ls] < k) return query(rs, mid + 1, r, k - st[ls]);
25 else return query(ls, l, mid, k);
26}
27
28
29int vis[maxn];
30vector<int> vec;
31int p[maxn], nxt[maxn][N];
32int a[maxn], temp[maxn], c[maxn];
33void update(int k, int x){
34 memset(st, 0, sizeof(st[0]) * 4 * n);
35 for(int i = 1; i <= n; i++){
36 c[i] = i;
37 update(1, 1, n, i, 1);
38 }
39 int cnt = k;
40 for(int i = 1; i <= n; i++){
41 p[i] = query(1, 1, n, cnt);
42 update(1, 1, n, p[i], -1);
43 if(i != n) cnt = (cnt + k - 2) % (n - i) + 1;
44 }
45
46 for(int i = 1; i <= n; i++) nxt[i][0] = p[i];
47 for(int i = 1; i < N; i++) for(int j = 1; j <= n; j++)
48 nxt[j][i] = nxt[nxt[j][i - 1]][i - 1];
49
50 for(int i = 1; i <= n; i++) vis[i] = 0;
51 for(int i = 1; i <= n; i++) if(!vis[i]){
52 vec.clear(); vec.push_back(i);
53 int now = i;
54 while(p[now] != i){
55 now = p[now]; vis[now] = 1;
56 vec.push_back(now);
57 }
58 int len = (int)vec.size();
59 int step = x % len;
60 for(auto x: vec){
61 for(int j = N - 1; j >= 0; j--) if(step & 1 << j){
62 c[x] = nxt[c[x]][j];
63 }
64 temp[x] = a[c[x]];
65 }
66 }
67 for(int i = 1; i <= n; i++) a[i] = temp[i];
68}
69
70int main(){
71// Fastin;
72 scanf("%d %d", &n, &m);
73 for(int i = 1; i <= n; i++) a[i] = i;
74 for(int _ = 1; _ <= m; _++){
75 int k, x; scnaf("%d %d", &k, &x);
76 update(k, x);
77 }
78 for(int i = 1; i <= n; i++) printf("%d ", a[i]);
79 printf("\n");
80 return 0;
81}J->XDOJ 1018
留坑待补《 具体数学》