CF_#449(Div. 1)简单题解

题目传送门

A.Nephren gives a riddle

水题……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//created by missever
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
char s0[] = "What are you doing at the end of the world? Are you busy? Will you save us?";
char s1[] = "What are you doing while sending \"";
char s2[] = "\"? Are you busy? Will you send \"";
char s3[] = "\"?";
LL f[maxn],mm = 1e18 + 1e5;
char solve(int n,LL k) {
if(f[n] < k) return '.';
if(n == 0) return s0[k - 1];
if(k <= strlen(s1)) return s1[k - 1];
k -= strlen(s1);
if(k <= f[n - 1]) return solve(n - 1,k);
k -= f[n - 1];
if(k <= strlen(s2)) return s2[k - 1];
k -= strlen(s2);
if(k <= f[n - 1]) return solve(n - 1,k);
k -= f[n - 1];
return s3[k - 1];
}
int main(){
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int i,q,n;
LL k;
f[0] = strlen(s0);
for(i = 1;i < maxn; i++) f[i] = min(mm,(LL)strlen(s1) + (LL)strlen(s2) + (LL)strlen(s3) + f[i - 1] * 2);
scanf("%d",&q);
while(q--) {
scanf("%d%lld",&n,&k);
printf("%c",solve(n,k));
}
return 0;
}

B.Ithea Plays With Chtholly

从左到右和从右到左分别维护一个单调队列……
那么入队次数最多也就最多$\frac{nc}{2}$次,就像一个直角三角形的两个锐角向直角延伸的样子……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//created by missever
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
vector<int> l,r;
int n;
void solvel(int x) {
if(l.empty() || l.back() <= x) {
l.push_back(x);
printf("%d\n",(int)l.size());
}
else {
int d = upper_bound(l.begin(),l.end(),x) - l.begin();
l[d] = x;
printf("%d\n",d + 1);
}
}
void solver(int x) {
if(r.empty() || r.back() >= x) {
r.push_back(x);
printf("%d\n",n - (int)r.size() + 1);
}
else {
int d;
for(d = 0;d < r.size(); d++) if(r[d] < x) break;
r[d] = x;
printf("%d\n",n - d);
}
}
int main(){
#ifdef CX_TEST
//freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int m,c,i,x;
scanf("%d%d%d",&n,&m,&c);
while(1) {
scanf("%d",&x);
if(x * 2 <= c) solvel(x);
else solver(x);
fflush(stdout);
if(l.size() + r.size() == n) break;
}
return 0;
}

C.Willem, Chtholly and Seniorious

因为操作纯随机,所以2操作不会太少,而得到的区间的期望长度是$\frac{n}{3}$,所以操作一定次数后只有较少的值不同的区间,所以暴力维护就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
//created by missever
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
typedef pair<LL,int> PL;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int add(int x,int y,int m) {
x += y;
if(x >= m) x -= m;
return x;
}
int mul(int x,int y,int m) {
LL z = 1LL * x * y;
return z - z / m * m;
}
int powt(int a,int b,int m) {
int r = 1;
while(b) {
if(b & 1) r = mul(r,a,m);
a = mul(a,a,m);
b >>= 1;
}
return r;
}
LL a[maxn];
int seed,vmax;
set<P> q;
vector<P> f;
vector<PL> g;
int rnd() {
int u = seed;
seed = add(mul(seed,7,mod),13,mod);
return u;
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int n,m,i,j,op,x,y,l,r;
scanf("%d%d%d%d",&n,&m,&seed,&vmax);
for(i = 1; i <= n; i++) a[i] = rnd() % vmax + 1;
for(i = j = 1; i <= n; i = j) {
while(a[j] ==a[i]) j++;
q.insert(P(j - 1,i));
}
for(i = 1; i <= m; i++) {
op = (rnd() & 3) + 1;
l = rnd() % n + 1;
r = rnd() % n + 1;
if(l > r) swap(l,r);
auto e = q.lower_bound(P(l,0));
if(op == 3) {
x = rnd() % (r - l + 1) + 1;
g.clear();
if(r <= (*e).first) {
printf("%lld\n",a[(*e).first]);
continue;
}
while(e != q.end() && (*e).second <= r) {
g.push_back(PL(a[(*e).first],min((*e).first,r) - max((*e).second,l) + 1));
e++;
}
sort(g.begin(),g.end());
for(auto w:g) {
x -= w.second;
if(x <= 0) {
printf("%lld\n",w.first);
break;
}
}
} else {
x = rnd() % vmax + 1;
j = 0;
if(op == 4) {
y = rnd() % vmax + 1;
while(e != q.end() && (*e).second <= r) {
//cout<<a[(*e).first]<<" "<<min((*e).first,r) - max((*e).second,l) + 1<<endl;
j = add(j,mul(powt(a[(*e).first] % y,x,y),min((*e).first,r) - max((*e).second,l) + 1,y),y);
e++;
}
printf("%d\n",j);
} else {
f.clear();
while(e != q.end() && (*e).second <= r) {
f.push_back(*e);
e++;
}
if(op == 1) {
for(auto u:f) {
q.erase(u);
if(u.first > r) q.insert(P(u.first,r + 1));
if(u.second < l) {
q.insert(P(l - 1,u.second));
a[l - 1] = a[u.first];
}
q.insert(P(min(u.first,r),max(u.second,l)));
a[min(u.first,r)] = a[u.first] + x;
}
} else {
for(auto u:f) {
q.erase(u);
if(u.first > r) q.insert(P(u.first,r + 1));
if(u.second < l) {
q.insert(P(l - 1,u.second));
a[l - 1] = a[u.first];
}
}
q.insert(P(r,l));
a[r] = x;
}
}
}
}
return 0;
}

D.Nephren Runs a Cinema

固定VIP的人数,剩下的等价于括号匹配方案数,考虑卡特兰数和组合数的那个关系式就好了?似乎以前都没注意过那个式子呀
因为模数不是质数,所以仿照扩展卢卡斯一样,用CRT合并就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
//created by missever
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
typedef pair<LL,LL> PL;
const LL mod = 1e9 + 7;
const LL maxn = 1e5 + 5;
LL add(LL x,LL y,LL m) {
x += y;
if(x >= m) x -= m;
return x;
}
LL mul(LL x,LL y,LL m) {
LL z = 1LL * x * y;
return z - z / m * m;
}
LL powt(LL a,LL b,LL m) {
LL r = 1;
while(b) {
if(b & 1) r = mul(r,a,m);
a = mul(a,a,m);
b >>= 1;
}
return r;
}
void extend_Euclid(LL a, LL b, LL &x, LL &y) {
if(b == 0) {
x = 1;
y = 0;
return;
}
extend_Euclid(b, a % b, x, y);
LL tmp = x;
x = y;
y = tmp - (a / b) * y;
}
LL Inv(LL a,LL b) {
LL x,y;
extend_Euclid(a,b,x,y);
return (x % b + b) % b;
}
LL CRT(vector<LL> &a,vector<LL> &m,LL M) {
LL ans = 0,n = a.size();
for(LL i = 0; i < n; i++) {
LL x,y;
LL Mi = M / m[i];
extend_Euclid(Mi, m[i], x, y);
x = (x % M + M) % M;
ans = add(ans,mul(mul(Mi,x,M),a[i],M),M);
}
return ans;
}
map<LL,LL> fac;
vector<LL> fa,fm;
struct node {
LL u,t,p;
LL f[maxn],g[maxn];
void init(LL a,LL b) {
LL i,x;
u = a;
t = b;
p = powt(a,b,mod * 2);
for(i = f[0] = 1;i <= 100000; i++) {
for(x = i;x % u == 0; x /= u);
f[i] = mul(f[i - 1],x,p);
}
memset(g,0,sizeof(g));
for(i = 1;i * u <= 100000; i++) g[i * u] = g[i] + 1;
for(i = 1;i <= 100000; i++) g[i] += g[i - 1];
}
LL get_mul(LL n,LL m) {
if(m < 0 || n < m) return 0;
LL tc = g[n] - g[m] - g[n - m];
if(tc >= t) return 0;
return mul(powt(u,tc,mod * 2),mul(f[n],Inv(mul(f[m],f[n - m],p),p),p),p);
}
} fs[20];
LL tot = 0;
void init(LL n) {
for(LL i = 2; i * i <= n; i++) {
while(n % i == 0) {
fac[i]++;
n /= i;
}
}
if(n > 1) fac[n]++;
for(auto e:fac) {
fs[tot].init(e.first,e.second);
fm.push_back(fs[tot++].p);
}
}
LL cal(LL n,LL m,LL p) {
fa.clear();
for(LL i = 0;i < tot; i++) fa.push_back(fs[i].get_mul(n,m));
return CRT(fa,fm,p);
}
LL solve(LL n,LL k,LL l,LL r,LL p) {
if(k + l > n) return 0;
LL ans = cal(n,k,p);
n -= k;
r = min(r,n);
if((n - r) & 1) r--;
if((n - l) & 1) l++;
r += 2;
LL d = cal(n,(n - l) >> 1,p);
if(r <= n) d = add(d,p - cal(n,(n - r) >> 1,p),p);
return mul(ans,d,p);
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int n,p,l,r,ans = 0;
scanf("%d%d%d%d",&n,&p,&l,&r);
init(p);
for(LL i = 0;i <= n; i++) ans = add(ans,solve(n,i,l,r,p),p);
printf("%d\n",ans);
return 0;
}

E.Welcome home, Chtholly

直接暴力一波即可过
分块,对于整个块的1操作,维护块内的最大最小值$v_{max},v_{min}$,如果$v_{min} + x + x \leq v_{max}$,把小于$x$的数加上$x$然后整个块减$x$即可,否则就把大于$x$的数暴力维护减去$x$的数加上$x$然后整个块减$x$即可
因为这样做是一直在缩小区间,并且每个值只会访问一次,所以可以保证对于一个块的总操作次数是$O(n)$的
为了实现这样的操作,需要用并查集维护每个数被修改后变成了哪个值,因为每次并查集修改后指向的值都是上述操作未被访问过的值,所以不会存在重叠或循环的问题……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
//created by missever
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
const int bsize = 340;
struct block {
int d[maxn], p[maxn], l, r;
void add(int x) {
d[x]++;
r = max(x, r);
}
int ff(int x) {
if(p[x] == 0) p[x] = x;
if(p[x] != x) p[x] = ff(p[x]);
return p[x];
}
void update(int x) {
if(x + l > r) return;
if(l + x + x <= r) {
for(int i = l + 1; i <= l + x; i++) {
if(d[i]) {
d[i + x] += d[i];
d[i] = 0;
p[i] = i + x;
}
}
l += x;
} else {
for(int i = l + x + 1; i <= r; i++) {
if(d[i]) {
d[i - x] += d[i];
d[i] = 0;
p[i] = i - x;
}
}
r = l + x;
}
}
int query(int x) {
if(x + l > r) return 0;
else return d[x + l];
}
} f[bsize];
int a[maxn], id[maxn], n;
void rebuild(int k, int l, int r, int x) {
for(int i = l; i <= r; i++) {
a[i] = f[k].ff(a[i]);
if(a[i] > x + f[k].l) {
f[k].d[a[i]]--;
a[i] -= x;
f[k].d[a[i]]++;
}
}
}
int query(int k, int l, int r, int x) {
int t = 0;
for(int i = l; i <= r; i++) {
if(f[k].ff(a[i]) == x + f[k].l) t++;
}
return t;
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int m, i, j, k, op, l, r, x;
scanf("%d%d", &n, &m);
for(i = 1, j = k = 0; i <= n; i++) {
scanf("%d", &a[i]);
id[i] = k;
f[k].add(a[i]);
if(++j == bsize) {
j = 0;
k++;
}
}
while(m--) {
scanf("%d%d%d%d", &op, &l, &r, &x);
if(op == 1) {
if(id[l] == id[r]) rebuild(id[l], l, r, x);
else {
rebuild(id[l], l, (id[l] + 1) * bsize, x);
rebuild(id[r], id[r] * bsize + 1, r, x);
for(i = id[l] + 1; i < id[r]; i++) f[i].update(x);
}
} else {
if(id[l] == id[r]) k = query(id[l], l, r, x);
else {
k = query(id[l], l, (id[l] + 1) * bsize, x);
k += query(id[r], id[r] * bsize + 1, r, x);
for(i = id[l] + 1; i < id[r]; i++) k += f[i].query(x);
}
printf("%d\n", k);
}
}
return 0;
}