| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 12/12 | Ø | Ø | O | O | Ø | O | Ø | Ø | O | Ø | O | Ø |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
给一个 $n\le 1e5$ 的元素互不相同的序列，问有多少个区间可以排序成等差数列。
解题思路
设 $a_l,a_{l+1},\cdots a_r$ 构成等差数列，有 $max_ia_i-min_ia_i=(r-l)\gcd_i(|a_i-a_{i-1}|)$
考虑枚举右端点 $i$，用线段树维护一下有多少个左端点 $j$ 满足条件。
因为固定端点的 $\gcd$ 只有 $O(\log)$ 个，可以枚举 $\gcd$ ，判断有多少个 $max-min+\gcd \cdot j=\gcd \cdot i$。由于等式左端取最小值时才能满足等式，考虑维护左式的最小值。于是令线段树每点维护 $tr_{l,r}=min_{j\in[l,r]}(max_{j…i}-min_{j…i}+\gcd_{j …i}\cdot j)$，并设 $cnt_{l,r}$ 为区间取到最小值的元素个数。
单调栈可以容易地维护 $max-min$ 的变化。$j\cdot \gcd$ 似乎比较难以维护，但考虑每一个左端点 $j$ 到右端点的 $\gcd$ 值最多只会被修改 $O(\log)$ 次，于是可以暴力地修改每一个被更改的左端点 $j$，因此也可以使用一个栈来维护 $\gcd$ 出现的区间。
AC代码
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
134
135
136
137
138
139
140
141
typedef long long ll;
using namespace std;
ll tr[N],lazy[N]; // tr: min of (max - min + i * gcd)
int L[N],R[N],cnt[N]; // cnt: count of same tr in [l, r]
int a[N];
void pushup(int p){
tr[p]=min(tr[p<<1],tr[p<<1|1]);
cnt[p]=0;
if(tr[p]==tr[p<<1])cnt[p]+=cnt[p<<1];
if(tr[p]==tr[p<<1|1])cnt[p]+=cnt[p<<1|1];
}
void pushdown(int p){
ll t=lazy[p];
if(!t)return;
lazy[p<<1]+=t;
lazy[p<<1|1]+=t;
tr[p<<1]+=t;
tr[p<<1|1]+=t;
lazy[p]=0;
}
void build(int p,int l,int r){
L[p]=l;R[p]=r;
lazy[p]=0;
if(l==r){
tr[p]=0;
cnt[p]=1;
return;
}
build(p<<1,l,(l+r)>>1);
build(p<<1|1,((l+r)>>1)+1,r);
pushup(p);
}
void modify(int p,int l,int r,ll x){
if(L[p]>r||R[p]<l)return;
if(L[p]>=l&&R[p]<=r){
tr[p]+=x;
lazy[p]+=x;
return;
}
pushdown(p);
modify(p<<1,l,r,x);
modify(p<<1|1,l,r,x);
pushup(p);
}
// update i*d, each position modified at most log times
void modifyEach(int p,int l,int r,ll x){
if(L[p]>r||R[p]<l)return;
if(L[p]==R[p]){
tr[p]+=x*L[p];
return;
}
pushdown(p);
modifyEach(p<<1,l,r,x);
modifyEach(p<<1|1,l,r,x);
pushup(p);
}
int query(int p,int l,int r,ll x){
if(L[p]>r||R[p]<l)return 0;
if(L[p]>=l&&R[p]<=r){
assert(tr[p]>=x);
return tr[p]==x?cnt[p]:0;
}
pushdown(p);
return query(p<<1,l,r,x)+query(p<<1|1,l,r,x);
}
int stmx[N],stmxp,stmn[N],stmnp,stgcd[N],stgcdp,gcd[N];
int main(){
int i,j,T,n;
scanf("%d",&T);
while(T--){
ll ans=0;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,1,n);
stmxp=stmnp=stgcdp=0;
for(i=1;i<=n;i++){
// max
while(stmxp&&a[stmx[stmxp]]<a[i]){
modify(1,stmx[stmxp-1]+1,stmx[stmxp],a[i]-a[stmx[stmxp]]);
stmxp--;
}
// min
stmx[++stmxp]=i;
while(stmnp&&a[stmn[stmnp]]>a[i]){
modify(1,stmn[stmnp-1]+1,stmn[stmnp],-a[i]+a[stmn[stmnp]]);
stmnp--;
}
stmn[++stmnp]=i;
if(i==1)continue;
// gcd
int delta=abs(a[i]-a[i-1]);
stgcd[++stgcdp]=i-1;
gcd[stgcdp]=delta;
modifyEach(1,i-1,i-1,delta);
for(j=1;j<stgcdp;j++){
int g=delta?__gcd(gcd[j],delta):0;
if(g==gcd[j])continue;
modifyEach(1,stgcd[j],stgcd[j+1]-1,g-gcd[j]);
gcd[j]=g;
}
int tp=stgcdp;
stgcdp=0;
for(j=1;j<=tp;j++){
if(j>1&&gcd[j]==gcd[j-1])continue;
stgcd[++stgcdp]=stgcd[j];
gcd[stgcdp]=gcd[j];
}
stgcd[stgcdp+1]=i;
for(j=1;j<=stgcdp;j++){
ans+=query(1,stgcd[j],stgcd[j+1]-1,1LL*i*gcd[j]);
}
}
printf("%lld\n",ans+n);
}
return 0;
}
B
题目描述
有两排炮，第一排 $x$ 个炮，第二排 $y$ 个炮。
每一步可以按象棋规则任意找一个炮吃掉另一个炮（不分敌我），问：
- 任意吃 $i$ 步的方案数
- 吃了第二排就不许再吃第一排的方案数（考虑排之间的顺序）
$x,y\in [2,5e6]$
解题思路
一排 $n$ 个吃一手的方案数是 $2(n-2)$，吃 $m$ 手的方案数是 $2^m\frac{(n-2)!}{(n-2-m)!}$。
于是 $a=x-2,b=y-2$。
不考虑顺序走 $i$ 步的方案数设为 $f_i$，枚举第一排吃的个数 $j$ ，则
$\begin{aligned}f_i&=2^i\sum_{j}\frac{a!}{(a-j)!}\frac{b!}{(b-i+j)!}\cdot \frac{i!}{j!(i-j)!}\\&=2^ii!\sum_{j}\frac{a!}{(a-j)!j!}\frac{b!}{(b-i+j)!(i-j)!}\\&=2^ii!\sum_j\binom{a}{j}\binom{b}{i-j}\\&=2^ii!\binom{a+b}{i}\end{aligned}$
考虑顺序方案数的方案数设为 $g_i$，同样枚举第一排吃的个数为 $j$，有
$\begin{aligned}g_i&=2^i\sum_{j}\frac{a!}{(a-j)!}\frac{b!}{(b-i+j)!}\\&=2^i\frac{a!b!}{(a+b-i)!}\sum_j\frac{(a+b-i)!}{(a-j)!(b-i+j)!}\\&=2^i\frac{a!b!}{(a+b-i)!}\sum_j\binom{a+b-i}{a-j}\end{aligned}$
考虑计算 $h_i=\sum_j\binom{a+b-i}{a-j}$，不妨设 $a\le b$。这是一个明显的前缀和形式，可线性维护，于是就做完了。下面是一些细节。
$j\in[0,i], a-j\ge 0,b-i+j\ge 0$
于是 $i>b$ 时 $h_i=\sum_{j=0}^{n-i}\binom{n-i}{j}=2^{n-i}$
$a\le i\le b$ 时 $h_i=\sum_{i=0}^{a}\binom{a+b-i}{j}$，而 $h_{i+1}=\sum_{i=0}^{a}\binom{a+b-i}{j}$，于是 $h_i=2h_{i+1}-\binom{a+b-i-1}{a}$
$i<a$ 时 $h_i=\sum_{i=a-i}^{a}\binom{a+b-i}{j}$，维护上下两个前缀和 $p,q$ 做差。$p$ 和上一种情况的递推相同， $q$ 也可以类似递推 $q_{i}=2q_{i+1}+\binom{a+b-i-1}{a-i-1}$
AC代码
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
typedef long long ll;
using namespace std;
const int mod=1000000009;
int fac[N],inv[N],pw[N];
int qp(ll a,int p){
ll ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
int c(int n,int m){
if(n<m)return 0;
return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
int i,a,b;
fac[0]=pw[0]=1;
for(i=1;i<N;i++)fac[i]=1LL*fac[i-1]*i%mod,pw[i]=pw[i-1]*2LL%mod;
inv[N-1]=qp(fac[N-1],mod-2);
for(i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1LL)%mod;
scanf("%d%d",&a,&b);
if(a>b)swap(a,b);
a-=2;b-=2;
// first part
int ans=0;
for(i=0;i<=a+b;i++)ans^=1LL*fac[i]*pw[i]%mod*c(a+b,i)%mod;
printf("%d ",ans);
// second part
ans=0;
int p=0,q=0;
for(i=a+b;i>=0;i--){
ll tmp=1LL*pw[i]*fac[a]%mod*fac[b]%mod*inv[a+b-i]%mod;
ll t;
if(i>b)t=p=pw[a+b-i];
else if(i>=a){
t=p=(2LL*p-c(a+b-i-1,a)+mod)%mod;
}else{
p=(2LL*p-c(a+b-i-1,a)+mod)%mod;
q=(2LL*q+c(a+b-i-1,a-i-1))%mod;
t=(p-q+mod)%mod;
}
ans^=1LL*tmp*t%mod;
}
printf("%d",ans);
return 0;
}
C
题目描述
签到题。
解题思路
AC代码
2
D
题目描述
签到题。
解题思路
AC代码
2
E
题目描述
一棵树 $n\le 1e5$，每点能够加 $a_i$ 油，每条边消耗 $w_i$ 油。
$q\le 1e5$ 次询问，每次询问从 $x_i$ 开始，有 $d_i$ 的初始油量，不经过 $p_i$ 能经过的节点数。
解题思路
将询问离线做点分治，求每个询问跨过当前根节点能到的点数。
先不考虑 $p_i$，每个询问就变成了能到达多少个不在 $x_i$ 子树中的点。可以预处理出来每个询问到根剩余油量、根到每个点所需油量。对询问和点做排序，就可以求出每个询问走到根节点再走下来的点数；但需要减掉 $x_i$ 所在子树的点，因此考虑使用 $dfs$ 序上做前缀和，树状数组进行维护。
考虑 $p_i$。当 $p_i$ 是 $x_i$ 祖先的时候，无法跨过根节点，贡献为 $0$，直接舍弃掉该询问。当 $p_i$ 与 $x_i$ 在根的不同子树中时，需要减掉 $p_i$ 子树的贡献，这同样可以使用上面的方法维护。
AC代码
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
typedef long long ll;
using namespace std;
vector<pii>G[N];
int n;
void add(int a,int b,int w){
G[a].pb(mp(b,w));
}
// lay on each node
struct query{
int x,p,i;
ll d;
};
vector<query>queries[N];
// when dealing with root p
struct Q{
int i; // id
int flag; // 1 or -1
ll fuel; // remaining fuel at root
int p; // query p's subtree
Q(int _i,int _f,ll _fu,int _p){
i=_i;flag=_f;fuel=_fu;p=_p;
}
bool operator<(const Q&q)const{
return fuel<q.fuel;
}
};
int rt,sum,mxt[N],siz[N],vis[N];
void getrt(int p,int f){
int i;
siz[p]=1;mxt[p]=0;
for(auto pr:G[p]){
auto q=pr.fi;
if(vis[q]||q==f)continue;
getrt(q,p);
siz[p]+=siz[q];
mxt[p]=max(mxt[p],siz[q]);
}
mxt[p]=max(mxt[p],sum-siz[p]);
if(mxt[p]<mxt[rt])rt=p;
}
// dfn
vector<int>nodes;
int dfn[N],dfnp,L[N],R[N],top[N];
// need 0: from (root to p], 1: from [p to root)
// cost 0: from (root to p], 1: from [p to root)
// cur: is in current rooted tree
ll need[2][N],cost[2][N],a[N];
int cur[N];
void dfs(int p,int f,int t){
// t: top ancestor of p, rooted at p
nodes.pb(p);
top[p]=t;
L[p]=dfn[p]=++dfnp;
for(auto pr:G[p]){
auto q=pr.fi,l=pr.se;
if(vis[q]||q==f)continue;
if(need[0][p]-cost[0][p]>=l)need[0][q]=need[0][p],cost[0][q]=cost[0][p]+l-a[q];
else need[0][q]=cost[0][p]+l,cost[0][q]=need[0][q]-a[q];
need[1][q]=max(0LL,need[1][p]+l-a[q]);
cost[1][q]=cost[1][p]+l-a[q];
dfs(q,p,t);
}
R[p]=dfnp;
}
// query
int ans[N],bit[N];
int querybit(int p){
int ans=0;
for(;p;p-=p&(-p))ans+=bit[p];
return ans;
}
void addbit(int p,int x){
for(;p<N;p+=p&(-p))bit[p]+=x;
}
void calc(int root){
// get dfn, precalculate cost & need
L[root]=dfn[root]=1;dfnp=1;
nodes.clear();
nodes.pb(root);
top[root]=0;
need[0][root]=cost[0][root]=0;
need[1][root]=cost[1][root]=0;
for(auto pr:G[root]){
auto q=pr.fi;
if(vis[q])continue;
need[0][q]=pr.se;cost[0][q]=pr.se-a[q];
need[1][q]=max(0LL,pr.se-a[q]);cost[1][q]=pr.se-a[q];
dfs(q,root,q);
}
R[root]=dfnp;
// distribute queries
vector<Q>vq;
for(auto p:nodes)cur[p]=1;
for(auto p:nodes){
for(auto que:queries[p]){
if(need[1][que.x]>que.d)continue;
int x=que.x,p=que.p,id=que.i;
ll d=que.d;
// x in subtree of p
if(cur[p]&&L[p]<=L[x]&&L[x]<=R[p])continue;
ll fuel=d-cost[1][x]+a[root]; // fuel after reaching root
if(cur[p]&&top[x]!=top[p])vq.pb(Q(id,-1,fuel,p));
vq.pb(Q(id,1,fuel,root));
if(x!=root)vq.pb(Q(id,-1,fuel,top[x]));
}
}
sort(vq.begin(),vq.end());
sort(nodes.begin(),nodes.end(),[&](const ll&a, const ll&b){
return need[0][a]<need[0][b];
});
// calculate queries
memset(bit,0,sizeof(int)*(dfnp+2));
int np=0;
for(auto que:vq){
ll fuel=que.fuel;
while(np<nodes.size()&&need[0][nodes[np]]<=fuel){
addbit(L[nodes[np]],1);
np++;
}
ans[que.i]+=que.flag*(querybit(R[que.p])-querybit(L[que.p]-1));
}
for(auto p:nodes)cur[p]=0;
}
void sol(int p){
vis[p]=1;
calc(p);
for(auto pr:G[p]){
auto q=pr.fi;
if(vis[q])continue;
mxt[rt=0]=n;sum=siz[q];getrt(q,0);
sol(rt);
}
}
int main(){
int i,Q;
scanf("%d%d",&n,&Q);
for(i=1;i<n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
}
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
for(i=0;i<Q;i++){
query q;
q.i=i;
scanf("%d%lld%d",&q.x,&q.d,&q.p);
queries[q.x].pb(q);
}
rt=0;sum=mxt[0]=n;getrt(1,0);
sol(rt);
for(i=0;i<Q;i++)printf("%d\n",ans[i]);
return 0;
}
F
题目描述
求两个球交的体积。
解题思路
solved by qxforever
和求圆交一样，讨论相离、包含和相交三种情况。
AC代码 - by qxforever
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
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 1e6 + 10;
const double pi = acos(-1.0);
struct P {
double x, y, z;
void read() { scanf("%lf%lf%lf", &x, &y, &z); }
P(double x = 0, double y = 0, double z = 0) : x(x), y(y), z(z) {}
P operator+(const P& p) { return P(x + p.x, y + p.y, z + p.z); }
P operator-(const P& p) { return P(x - p.x, y - p.y, z - p.z); }
void norl() {
double s = x * x + y * y + z * z;
s = sqrt(s);
x /= s, y /= s, z /= s;
}
void div(double v) { x /= v, y /= v, z /= v; }
void print() {
cerr << x << ' ' << y << ' ' << z << '\n';
}
};
double pw(double x) {
return x * x;
}
P calcir(P a, P b, double k, double &r) {
double dis = sqrt(pw(a.x - b.x) + pw(a.y - b.y) + pw(a.z - b.z));
r = k * dis / (k * k - 1);
P l = b - a;
l.norl();
l.div(1 / (r - dis / (k + 1)));
return b + l;
}
double calc(double r) {
return 4.0 / 3 * pi * r * r * r;
}
double calc2(double h, double r) {
return pi / 3.0 * h * h * (3.0 * r - h);
}
void solve() {
P a, b, c, d;
a.read();
b.read();
c.read();
d.read();
double k1, k2;
scanf("%lf%lf", &k1, &k2);
double r1, r2;
P c1 = calcir(a, b, k1, r1), c2 = calcir(c, d, k2, r2);
double dis = pw(c1.x - c2.x) + pw(c1.y - c2.y) + pw(c1.z - c2.z);
dis = sqrt(dis);
double sum = 0;
// c1.print();
// c2.print();
// cerr << dis << ' ' << r1 << ' ' << r2 << '\n';
if (dis >= r1 + r2) {
sum = 0;
}
else if (dis <= abs(r1 - r2)) {
sum = calc(min(r1, r2));
}
else {
double h = r1 - (r1 * r1 - r2 * r2 + dis * dis) / (2.0 * dis);
sum += calc2(h, r1);
h = r2 - (r2 * r2 - r1 * r1 + dis * dis) / (2.0 * dis);
sum += calc2(h, r2);
}
printf("%.10f\n", sum);
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
G
题目描述
给 $n\le 5e3$ 个区间 $[l_i,r_i]$，求分成 $k$ 组使得每组区间交不为空，并求满足条件的区间交之和的最大值。
解题思路
直接考虑 $f_{i,j}$ 表示排好序后选到了区间 $i$，共分成了 $j$ 组，不容易转移，因为不满足 $\forall i<j, L_i\le L_j\text{ and }R_i\le R_j$，即有区间覆盖的情况。
如果不考虑有区间覆盖的情况，有显然 $dp$：
$f_{i,j}=max_{k=1,r_k>l_i}^{i-1}(f_{k,j-1}+r_{k+1}-l_{i})$，决策点明显是单调的，可以单调队列优化。
考虑处理掉这些覆盖其他区间的区间（称为大区间）。如果设区间 $i$ 覆盖了区间 $j$，则去掉所有大区间后，区间 $i$ 可以放入 $j$ 所在组不影响答案，或者单独成一组。因此枚举一下独自成组的大区间个数即可统计答案。
AC代码
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
typedef long long ll;
using namespace std;
struct T{
int l,r;
bool operator<(const T&a)const{
return l==a.l?r>a.r:l<a.l;
}
}a[N],b[N];
int cnt,f[N][N],hd[N],tl[N];
pii g[N][N];
vector<int>big;
int main(){
int n,k,i,j;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)scanf("%d%d",&a[i].l,&a[i].r);
sort(a+1,a+1+n);
for(i=1;i<=n;i++){
int flag=0;
for(j=i+1;j<=n;j++){
if(a[i].r>=a[j].r){
flag=1;
break;
}
}
if(flag)big.pb(a[i].r-a[i].l);
else b[++cnt]=a[i];
}
sort(big.begin(),big.end(),greater<int>());
// for(auto p:big)printf("%d ",p);puts("");
for(i=0;i<=cnt;i++){
for(j=0;j<=k;j++){
g[i][j]=mp(0,-1e9);
f[i][j]=-1e9;
}
}
f[0][0]=0;
g[1][++tl[1]]=mp(b[1].r,b[1].r);
for(i=1;i<=cnt;i++){
for(j=k;j>=1;j--){
while(hd[j]<tl[j]&&g[j][hd[j]+1].fi<=b[i].l)hd[j]++;
if(hd[j]>=tl[j]||g[j][hd[j]+1].fi<=b[i].l)continue;
// printf("(%d %d) <- (%d %d)\n",i,j,g[j][hd[j]+1].fi,g[j][hd[j]+1].se);
f[i][j]=-b[i].l+g[j][hd[j]+1].se;
while(tl[j+1]>hd[j+1]&&f[i][j]+b[i+1].r>g[j+1][tl[j+1]].se)
tl[j+1]--;
g[j+1][++tl[j+1]]=mp(b[i+1].r,f[i][j]+b[i+1].r);
}
}
int sum=0,ans=0;
for(i=0;i<=big.size()&&i<=k;i++){
ans=max(ans,sum+f[cnt][k-i]);
if(i<big.size())sum+=big[i];
}
printf("%d",ans);
return 0;
}
H
题目描述
给一个 $n$ 长度 $01$ 串表示一个单链烯烃，每次可以任意位置加成（选择一段区间翻转 $01$），问 $k$ 次被 $H_2$ 加成的方案数。
解题思路
容易想到求出每一段连续 $1010\cdots 101$ 序列，对每一段求指数生成函数之后卷起来。于是问题变成快速求出 $n$ 个 $1$ 出现的序列中，加成 $k$ 步的方案数 $f_{n,k}$。
对于一个终态（$2n-1$ 个位置任选 $n-k$ 个不相邻 $1$ 的状态），无论 $1$ 在哪里，考虑有多少父态能转移到改终态，设有 $x$ 段连续且分立的 $0101\cdots 010$ （含有 $1$ 的、$0$ 开头结尾）串，则可以从 $1010\cdots 101$ 转移过来，因此共有 $x$ 种父态可以纯通过翻转连续多个 $1$ 构成的串而成；再考虑仅加成了一个 $1$ 的情况，整个串去除 $01010$ 式串得到的所有剩余位置都可以从 $1$ 转化而来，容易算出是 $2n-1-(n-k)-(n-k+x)=2k-1-x$ 个。于是有 $2k-1$ 个父态可以转移到终态，数学归纳一下就能知道有 $\prod_{i=1}^{k}(2i-1)$ 种从初态转移过来的方法。
举一个例子，$[01010]0000[010]00$ 框起来的是共 $x=2$ 个含有 $1$ 的、$0$ 开头结尾的段，剩余位置均可以单独加成填 $1$。
再举一个例子，$[01010]00[0101$，这样某端点是 $1$ 的情况，不能通过连续加成得到，但由于其长度也比 $01010$ 要短一个，贡献恰好抵消，相当于拼到了某个正常 $01010$ 串上，所以不用管这种情况。
而终态共有 $\binom{(2n-1)-(n-k-1)}{n-k}$，这可以用插板法或者暴力拿走 $1$ 中的 $0$ 等方法计算。
于是 $f_{n,k}=\binom{n+k}{n-k}\prod_{i=1}^{k}(2i-1)$。
AC代码
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
134
135
136
137
138
139
140
141
142
143
144
145
146
typedef long long ll;
using namespace std;
const int mod=998244353;
int qpow(ll x,int p){
int ans=1;
for(;p;p>>=1,x=x*x%mod)if(p&1)ans=ans*x%mod;
return ans;
}
namespace NTT{
const int g=3,invg=332748118;
int rev[M+5];
int mx,lim;
int w[3][M+5];
void fft_prepare(int _mx,int _lim){
int i;
mx=_mx;lim=_lim;
for(i=0;i<lim;i++)rev[i]=rev[i>>1]>>1|((i&1)<<(mx-1));
}
void fft_prepare(int n){
int i;
mx=0,lim=1;
while(lim<n)lim<<=1,mx++;
fft_prepare(mx,lim);
}
inline void ntt(int *a,int len,int flag){
int i,mid,j;
int inv=qpow(len,mod-2);
for(i=0;i<len;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
for(mid=1;mid<len;mid<<=1){
ll gn=qpow(flag==1?g:invg,(mod-1)/(mid<<1));
for(i=0;i<len;i+=(mid<<1)){
ll g0=1;
for(j=0;j<mid;++j,g0=g0*gn%mod){
int x=a[i+j],y=g0*a[i+j+mid]%mod;
a[i+j]=(x+y)%mod,a[i+j+mid]=(x-y+mod)%mod;
}
}
}
if(flag==-1)for(i=0;i<len;i++)a[i]=1LL*a[i]*inv%mod;
}
void conv(int *x,int *y,int *z,int n,int m,int mod){
assert(mod==998244353);
int i;
static int X[M+5],Y[M+5];
for(i=0;i<=n;i++)X[i]=(x[i]+mod)%mod;
for(;i<lim;i++)X[i]=0;
for(i=0;i<=m;i++)Y[i]=(y[i]+mod)%mod;
for(;i<lim;i++)Y[i]=0;
ntt(X,lim,1);
ntt(Y,lim,1);
for(i=0;i<lim;i++)X[i]=1LL*X[i]*Y[i]%mod;
ntt(X,lim,-1);
for(i=0;i<lim;i++)z[i]=X[i];
}
}
struct Poly: vector<int>{
Poly(){}
bool operator<(const Poly&b)const{
return size()>b.size();
}
int at(ll n){return n>=size()?0:(*this)[n];}
Poly(int n): vector<int>(n){}
Poly operator*(const Poly& b)const{return (Poly(*this)*=b);}
Poly operator*(const int& b)const{return (Poly(*this)*=b);}
Poly &operator*=(const int &a) {
for(int i=0;i<size();++i)(*this)[i]=(*this)[i]*(a%mod+mod)%mod;
return *this;
}
Poly &operator*=(const Poly &fs){
if (empty()||fs.empty()) return *this={};
const int n=size()-1,m=fs.size()-1;
static int x[M+5],y[M+5],z[M+5];
int i;
for(i=0;i<=n;i++)x[i]=(*this)[i];
for(i=0;i<=m;i++)y[i]=fs[i];
NTT::fft_prepare(n+m+1);
NTT::conv(x,y,z,n,m,mod);
resize(n+m+1);
for(i=0;i<=n+m;i++)(*this)[i]=z[i];
return *this;
}
}poly;
char a[M];
int fac[M],inv[M];
int c(int n,int m){
if(n<m)return 0;
return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
int i,t,n,k;
scanf("%d%d%s",&n,&k,a);
fac[0]=1;
for(i=1;i<M;i++)fac[i]=1LL*fac[i-1]*i%mod;
inv[M-1]=qpow(fac[M-1],mod-2);
for(i=M-2;i>=0;i--)inv[i]=inv[i+1]*(i+1LL)%mod;
vector<int>v;
for(t=0;t<n;){
int cnt=0;
while(t<n&&a[t]!='1')t++;
if(a[t]=='1')t++,cnt++;
while(t+1<n&&a[t]=='0'&&a[t+1]=='1')t+=2,cnt++;
v.pb(cnt);
}
priority_queue<Poly>Q;
for(auto x:v){
Poly v(x+1);
ll ff=1;
v[0]=1;
for(i=1;i<=x;i++){
ff=ff*(2*i-1)%mod;
v[i]=ff*c(x+i,x-i)%mod*inv[i]%mod;
}
Q.push(v);
}
while(!Q.empty()){
Poly p=Q.top();Q.pop();
if(Q.empty()){
printf("%d",1LL*p.at(k)*fac[k]%mod);
break;
}
Poly q=Q.top();Q.pop();
Q.push(p*q);
}
return 0;
}
I
题目描述
签到题。
解题思路
AC代码
2
J
题目描述
给一个 $4e4$ 的数列 $a(a_i\le 8e4)$，求全部大小恰为 $k\le 30$ 的子集 $\gcd$ 之积，对 $p\in[1e6,1e14]$ 取模。
解题思路
设 $cnt_i=\sum_{j}[i|a_j]$，即序列中 $i$ 的倍数个数。
枚举 $\gcd$，$i$ 作为 $\gcd$ 时方案数为 $f_i$，则容斥一下有 $f_i=\binom{cnt_i}{k}-\sum_{i|j,j>i}f_j$，答案为 $\prod_{d}d^{f_d}$。
逐质数统计一下，$p^q$ 的贡献为 $f_{p^q}=\binom{cnt_{p^q}}{k}-\sum_{q’>q}f_{p^{q’}}$ ，从大到小推一下能获得 $p$ 的总贡献为 $sf_p=\sum_{q=1}\binom{cnt_{p^q}}{k}$。由于只需要加法，可以应用扩展欧拉定理进行对 $\varphi(p)$ 的取模。答案为 $\prod_{p}p^{sf_p}$。
傻逼出题人卡常数，如果只计算 $f$ 而不推每个质数总贡献 $sf$ 的话，是同样复杂度的做法，但常数卡不过去。
AC代码
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
typedef long long ll;
using namespace std;
bool isnp[M];
int pri[M/10],ct;
void sieve(){
int i,j;
isnp[0]=isnp[1]=1;
for(i=2;i<M;i++){
if(!isnp[i])pri[ct++]=i;
for(j=0;j<ct;j++){
if(1LL*i*pri[j]>=M)break;
isnp[i*pri[j]]=1;
if(i%pri[j]==0)break;
}
}
}
ll getphi(ll x){
ll ans=1;
int i;
for(i=0;i<ct;i++){
if(x%pri[i]==0){
x/=pri[i];
ans*=pri[i]-1;
while(x%pri[i]==0)x/=pri[i],ans*=pri[i];
}
}
if(x>1)ans*=x-1;
return ans;
}
inline ll qmul(__int128 a,__int128 b,ll mod){
return a*b%mod;
}
ll qp(ll a,ll p,ll mod){
ll ans=1;
a%=mod;
for(;p;p>>=1,a=qmul(a,a,mod))if(p&1)ans=qmul(ans,a,mod);
return ans;
}
int cnt[N],a[N];
ll c[N][K];
inline ll add(ll a,ll b,ll phi){
ll tmp=a+b;
while(tmp>=2*phi)tmp-=phi;
return tmp;
}
int main(){
int i,j,T;
sieve();
// T=60;
scanf("%d",&T);
while(T--){
int n,k;ll p,phi,mod;
memset(cnt,0,sizeof(cnt));
// n=40000;k=30;mod=100000000000000LL;
scanf("%d%d%lld",&n,&k,&mod);
phi=getphi(mod);
int mx=0;
for(i=1;i<=n;i++){
// a[i]=1LL*rand()*rand()%80000+1;
scanf("%d",&a[i]);
cnt[a[i]]++;
mx=max(mx,a[i]);
}
for(i=1;i+i<=N-1;i++)
for(j=i+i;j<=N-1;j+=i)
cnt[i]+=cnt[j];
int mxcnt=*max_element(cnt,cnt+mx+1);
mx=min(mx,N-1);
for(i=0;i<=mx;i++)c[i][0]=1;
for(i=1;i<=mxcnt;i++)
for(j=1;j<=k&&j<=i;j++)
c[i][j]=add(c[i-1][j],c[i-1][j-1],phi);
ll ans=1;
for(i=0;pri[i]<=mx&&i<ct;i++){
int p=pri[i];
ll t=p,e=0;
while(t<=mx&&cnt[t]>=k){
e=add(e,c[cnt[t]][k],phi);
t*=p;
}
ans=(__int128)ans*qp(p,e,mod)%mod;
}
printf("%lld\n",ans);
}
// printf("%lf\n",1.0*clock()/CLOCKS_PER_SEC);
return 0;
}
K
题目描述
对于 $a$ 序列，$b$ 序列是构建 $a$ 单调栈时的长度序列。给定 $b$ 的某些项，求构造 $a$。
解题思路
solved by qxforever
首先，有解当且仅当 $b$ 序列任意相邻两项只能 $+1$ 或者减到某一个大小，因此获得 $b$ 序列。
对于 $b$ 为 $1$ ，可以从后到前填 $1,2,…,k$。然后继续填 $b=2,b=3,…b=n$ 的情况即可。
AC代码 - by qxforever
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
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 1e6 + 10;
int a[maxn], b[maxn], c[maxn], n, k;
vector<int> pos[maxn];
int main() {
cin >> n >> k;
vector<pii> bs;
for (int i = 0; i < k; i++) {
int x, y;
scanf("%d%d", &x, &y);
b[x] = y;
}
for (int i = 1; i <= n; i++) {
if (!b[i]) b[i] = b[i - 1] + 1;
pos[b[i]].push_back(i);
}
for (int i = 1; i <= n; i++) {
if (b[i] - b[i - 1] > 1) {
puts("-1");
return 0;
}
}
int pre = 0;
for (int i = 1; i <= n; i++) {
int m = pos[i].size();
for (int j = m - 1; ~j; j--) {
a[pos[i][j]] = ++pre;
}
}
for (int i = 1; i <= n; i++) printf("%d ", a[i]);
}
L
题目描述
有 $n$ 个人，$m$ 个朋友关系和 $q$ 个时间点，$n,m,q\le 2e5$。在时间点 $i$，$a_i$ 走了 $l_i$ 步。
在某个时刻，如果 $i$ 比他朋友走的都多，那么说该时刻 $i$ 是他自己的榜单冠军。问每个人分别当了多久冠军。
解题思路
对每个人 $i$，可以拆成多个步数区间：$(t_j,x_j)$，表示在 $[t_j,t_{j+1}]$ 走了 $x_j$ 步。
将所有 $x$ 从大向小考虑，每次枚举一个 $(t_i,x_i)$，计算 $i$ 在 $[t_i,t_{i+1}]$ 时刻共走 $x$ 步，对每个人的贡献。
维护每个人 $p$ 在被枚举时刻的最小 $t_j$ 并记为 $f_p$，则 $i$ 榜单上所有人 $P$ 中最小的 $f_p$ 就是 $t_i$ 能够贡献到的最远处，容易统计答案。
但这种方式会被菊花图卡掉，考虑分块。设度数大于等于 $\sqrt n$ 的称为”大点“，反之是“小点”。于是每个小点周围点的个数是 $O(\sqrt n)$，每个点周围大点的个数是 $O(\sqrt n)$。
如果 $i$ 是“小点”，可以直接用上述过程维护。否则是大点，可以被其他点维护。
AC代码
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
typedef long long ll;
using namespace std;
int f[N],g[N],last[N],cnt[N],ans[N];
vector<int>G[N],big[N];
int main(){
int i,n,m,q,_sqrtn;
scanf("%d%d%d",&n,&m,&q);_sqrtn=sqrt(n);
for(i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
G[u].pb(v);G[v].pb(u);
}
for(i=1;i<=n;i++){
if(G[i].size()>=_sqrtn){
for(auto p:G[i])
big[p].pb(i);
}
f[i]=g[i]=last[i]=q;
}
map<int,vector<pii>>v;
for(i=1;i<=q;i++){
int x,y;
scanf("%d%d",&x,&y);
cnt[x]+=y;
v[-cnt[x]].pb(mp(x,i));
}
for(auto pr:v){
vector<pii>v=pr.se;
for(auto pr:v){
auto x=pr.fi,t=pr.se;
for(auto p:big[x])
g[p]=min(g[p],t);
last[x]=f[x];
f[x]=t;
}
for(auto pr:v){
auto x=pr.fi,t=pr.se;
if(G[x].size()>=_sqrtn)ans[x]+=max(min(last[x],g[x])-t,0);
else{
int mx=last[x];
for(auto p:G[x])
mx=min(mx,f[p]);
ans[x]+=max(mx-t,0);
}
}
}
for(i=1;i<=n;i++)printf("%d\n",ans[i]);
return 0;
}