NOIP五校联考暴零记

作者:ZqlwMatt
支持:杭州二中 成都七中 长郡中学 南京外国语学校 衡阳市八中
......

目录[TOC]

Day 1

毛一琛(subsets)

时间限制:1s空间限制:512MB

问题描述:

历史学考后,MYC 和 ztr 对答案,发现选择题他们没有一道选的是一样的。最后他们都考了个C。现在问题来了,假设他们五五开,分数恰好一样(问答题分数也恰好一样,只考虑选择题)。已知考题是 NN 道选择题(第 ii 题分数为 M(i)M(i))。问 ztr 和 MYC 做对的题的并有多少种可能?众所周知,历史学考选择题有 25 题,但是 MYC 为了给你降低难度,NN 不超过20。

一句话题意:有多少个非空子集,能划分成和相等的两份。

输入格式: 第一行:整数 NN 第 2..1+N 行:第 i+1 行是 M(i)M(i)

输入样例:

4
1
2
3
4

输出样例:

3

数据范围: N20,M108N \le 20, M \le 10^{8}

Solution

每次按照 不选,MYC选对,ztr选对 暴搜,时间复杂度 O(3n)O(3^{n}),试着用 Meet in the Middle,搜一边将分数差值放入map,搜另一边将分数差值加上前一边的结果,仔细想后发现不是很好做。

就比如说 1 2 3 1 2 3 的时候就有这样的情况......

zzz.png

不妨考虑每一个集合是否符合条件,我们对前半部分构成的差值记录所构成的集合。然后搜索另一半时将与自己差值相反的值所构成的集合与当前集合取并。最后统计有多少个集合合法即可。实现时可能状态数较多,对相同的集合可以去重。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0

map<int,int> mp;
set<int> s[1234567];
int n, p, a[21], id;
int vis[1<<20], ans;

void dfs(int x, int now, int r) {
if(x==p) {
int cnt = mp[r];
if(!cnt) cnt=mp[r]=++id;
s[cnt].insert(now);
return ;
}
dfs(x+1, now, r);
dfs(x+1, now|(1<<x-1), r+a[x]);
dfs(x+1, now|(1<<x-1), r-a[x]);
}
void DFS(int x, int now, int r) {
if(x > n) {
int cnt = mp[r];
if(!cnt) return ;
for(set<int>::iterator it=s[cnt].begin();it!=s[cnt].end();++it)
vis[*it|now]=1; return ;
}
DFS(x+1, now, r);
DFS(x+1, now|(1<<x-1), r+a[x]);
DFS(x+1, now|(1<<x-1), r-a[x]);
}

int main() {
cin >> n, p=n>>1;
rep(i,1,n) cin >> a[i];
dfs(1,0,0);
DFS(p,0,0);
for(int i=1;i<1<<n;++i) ans+=vis[i];
printf("%d\n", ans);
return ~~(0^_^0);
}

毛二琛(swap)

时间限制:1s空间限制:512MB

MYC 在 NOI2018 中,遇到了 day1T2 这样一个题,题目是让你求有多少“好”的排列。MYC 此题没有获得高分,感到非常惭愧,于是回去专心研究排列了。如今数排列的题对 MYC 来说已经是小菜一碟了。于是 MYC 想考考你,扔给你了一个非常 naive 的数排列题给你。

给定一个 的排列 pp 。一个 的排列 qq 被认为是优美的排列,当且仅当 qq 满足下列条件:

对排列 s={0,1,2,3,...,n1}s = \{0, 1, 2, 3, ..., n - 1\} 进行 n–1 次交换。

  1. 交换 s[q0],s[q0+1]s[q_{0}],s[q_{0} + 1]
  2. 交换 s[q1],s[q1+1]s[q_{1}],s[q_{1} + 1]
    ...

最后能使得排列 s=ps=p. 问有多少个优美的排列,答案对 109+710^{9}+7 取模。

输入格式: 第一行一个正整数 nn. 第二行 nn 个整数代表排列 pp.

输出格式: 仅一行表示答案。

样例输入:

3
1 2 0

样例输出:

1

数据范围: n5000n \le 5000

Solution

问题等价于对于排列 pp,倒序 qq 操作,翻转后的结果是否是 发现每次交换只能交换相邻的两项,且结果成立时翻转存在先后顺序。

如下图,我们目标将①号点转移到②号,这会产生限制。

无标题.png

  1. 对于 ①~② 之间的连续两个操作 ③-④ ④-⑤,操作 ③-④ 一定在 ④-⑤ 之前。
  2. ⑥-① 操作一定在 ① 向右翻转之后。(否则①被转走...
  3. ②-⑦ 操作一定在 ② 向左翻转之前。

那么我们可以发现,我们要求的排列 pp,其实就是 n1n-1 个时间,时间两两之间有先、后限制的求方案数。

考虑dp,f[i][j] 表示前 i 个数中第 i 个数是第 j 大的,且 f[i][j] 表示这些数的相对位置(并不严格相差1),那么转移就非常方便了。前缀和优化后时间复杂度为 O(n2)O(n^{2})

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0

int n, p[5005], o[5005], f[5005][5005], g[5005][5005];
#define GG puts("0"),exit(0),0
#define M 1000000007

void geto() {
memset(o, -1, sizeof o);
for(int i=0; i<n; ++i) {
if(p[i] > i) { // =>
if(i) o[i-1]==0?GG:o[i-1]=1;
for(int j=i;j<p[i]-1;++j) o[j]==1?GG:o[j]=0;
if(p[i] < n-1) o[p[i]-1]==0?GG:o[p[i]-1]=1; // o[p[i]-1]<o[p[i]]
}
else if(p[i] < i) { // <=
if(p[i]) o[p[i]-1]==1?GG:o[p[i]-1]=0; // o[p[i]-1]<o[p[i]]
for(int j=p[i];j<i-1;++j) o[j]==0?GG:o[j]=1;
if(i < n-1) o[i-1]==1?GG:o[i-1]=0; // o[i-1]<o[i]
}
else GG;
}
}

int main() {
freopen("swap.in","r",stdin);
freopen("swap.out","w",stdout);
cin >> n;
for(int i=0;i<n;++i) cin>>p[i];
geto();
f[0][1] = g[0][1] = 1;
for(int i=1; i<n-1; ++i)
for(int j=1; j<=i+1; ++j) {
if(o[i-1]==0) // o[i-1] < o[i]
(f[i][j]+=g[i-1][j-1])%=M;
else
(f[i][j]+=(g[i-1][i]-g[i-1][j-1])%M)%=M;
g[i][j] = (g[i][j-1]+f[i][j])%M;
}
int ans = 0;
for(int i=1; i<n; ++i) (ans+=f[n-2][i])%=M; // (n-1)-1
printf("%d\n", (ans+M)%M);
return ~~(0^_^0);
}

毛三琛(moiezen)

时间限制:1s空间限制:512MB

题目描述

MYC 带着他的行李去考清华集训了。对 MYC 来说,进候选队不在话下。。。

MYC 有n 件行李,编号为 1n1 \sim n。行李的质量是模 PP 意义下的(PP 不一定是质数)。MYC 有 kk 个背包,要装下这些行李,为了方便MYC 在背包中找行李,每个背包中的行李编号是连续的,允许有背包为空。MYC 想让最重的背包尽量轻。

由于MYC 毕竟是要进候选队的人,他有特技可以用。他会选择一个 x(0x<P)x(0 \le x<P),给所有行李的质量+x+x mod P\text{mod~P},然后才装到背包里去。

你要帮助 MYC 先选择一个xx,再选择一种行李分配方案,使得最重的背包尽量轻。

MYC 相信,你一定能帮他装好行李,给拼搏于候选队的逐梦之路上的MYC,提供一个有力的援助。

输入格式: 第一行正整数 。 第二行 nn 个自然数 aia_{i}(0<=ai<P)(0<=a_{i}<P)

输出格式: 仅一个数表示最重的背包的质量。

样例输入:

5 5 2
0 4 2 1 3

样例输出:

5

数据范围: n10000,P10000n \le 10000, P \le 10000

Solution

一个随机排列中比前面所有数都大的数的数量期望为 log\text{log}

考虑对x枚举的顺序随机一下,这样枚举到一个x时候,可以先去check一下是否比目前的最优解要优,如果是,那么再去二分,否则直接 continue。然后暴力枚举 x 二分答案。 时间复杂度 O(nP+nlog n log P)O(nP+nlog~n~log~P)

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
int n, p, k, a[10005], b[10005], z[10005], ans=0x3f3f3f3f;

int check(int x) {
int r=0;
for(int pos=1,m=0;pos<=n;++pos) {
if(b[pos]>x) return 0;
if(m+b[pos]>x) m=b[pos], ++r;
else m+=b[pos];
} ++r;
return r<=k;
}

int main() {
freopen("moiezen.in","r",stdin);
freopen("moiezen.out","w",stdout);
cin >> n >> p >> k;
rep(i,1,n) cin >> a[i];
rep(i,1,p) z[i]=i; random_shuffle(z+1, z+p+1);
rep(x,1,p) {
rep(i,1,n) b[i]=(a[i]+z[x])%p;
if(!check(ans)) continue;
int l=0, r=ans, mid;
while(l<=r) {
mid = (l+r)>>1;
if(check(mid)) r=mid-1;
else l=mid+1;
}
ans = min(ans, l);
}
printf("%d\n", ans);
return ~~(0^_^0);
}

Day 2

梦境(dream)

时间限制:1s空间限制:512MB

【问题描述】

题意简述:直线上有 mm 个点,现在给出 nn 条线段,每条线段只能覆盖它上面的一个点,求最多有多少点能被覆盖。

【输入格式】

输入文件名为 dream.in

文件的第一行为有两个正整数 n,mn,m

第 2 至第 n+1 行,每行两个正整数 li,ril_{i},r_{i},第 i+1 行的两个数刻画了 IcePrincess_1968 的第 i 段梦境,含义如题面中所述。

第 n+2 至第 n+m+1 行,每行一个正数tit_{i},第 i 行的两个数刻画了 IcePrince_1968 的第 i-n-1 个梦境转折点,含义如题面中所述。

样例输入:

2 2
1 3
2 4
1
3

样例输出:

2

【数据规模和约定】 n200000,m200000,1li,ri1000000000,1ti1000000n \le 200000, m \le 200000, 1 \le l_{i}, \le r_{i} \le 1000000000, 1 \le t_{i} \le 1000000 ,保证对于每段梦境 liril_{i} \le r_{i}

Solution

贪心。 将右端点排序,枚举线段每次覆盖最左边的点。可以用 set 维护点的坐标,将选过的点删掉。(考试的时候没处理好迭代器挂了50分qwq

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0

int n, m;
struct S {
int l, r;
bool operator < (const S&B)const{return r<B.r;}
}s[200005];
multiset<int> p;
multiset<int>::iterator it;

int main() {
freopen("dream.in","r",stdin);
freopen("dream.out","w",stdout);
cin >> n >> m;
rep(i,1,n) cin>>s[i].l>>s[i].r;
sort(s+1, s+n+1);
int x;
rep(i,1,m) cin>>x, p.insert(x);
rep(i,1,n) {
it = p.lower_bound(s[i].l);
if(it==p.end()||*it>s[i].r) continue;
p.erase(it);
}
printf("%d\n", m-p.size());
return ~~(0^_^0);
}

玩具(toy)

时间限制:1s空间限制:512MB

【问题描述】

这个故事发生在很久以前,在 IcePrincess_1968IcePrince_1968 都还在上幼儿园的时候。
IcePrince_1968 最近迷上了一种玩具,这种玩具中有两种零件:圆球和棍子。棍子的两头可以插在两个圆球上的各一个空洞中,从而将两个圆球连接起来。为了保证玩具的娱乐性,任意一个圆球上的空洞个数总是多于玩具套装中的棍子数。你可以认为圆球是没有体积的,所有棍子的长度均为 11
IcePrince_1968 喜欢这样玩这种玩具:他先摸出玩具袋里的一个圆球放在地上,然后重复下面的操作 n1n-1 次:每次从袋中取出一个圆球和一根棍子,然后等概率的从地上的圆球中选择一个,将该圆球和选择的圆球用棍子连起来,使得新的圆球在选中圆球的正上方。
IcePrince_1968 对自己搭出的艺术品很满意,便决定把这个物品送给 IcePrincess_1968 作为生日礼物。然而生日礼物是需要包装的,因为默认圆球没有体积,所以 IcePrince_1968 不用考虑包装盒的长和宽,但是包装盒的高是需要确定的,这里我们假设 IcePrince_1968 是一个非常节俭的孩子,所以包装盒的高总是等于艺术品的高度。IcePrince_1968 想知道自己需要的包装盒的高的期望对质数 pp 取模后的值,但他还在上幼儿园,怎么会算呢,于是就请你来帮助他。

【输入格式】

输入文件名为 toy.in

输入数据仅一行,包含两个正整数 n,pn,p,表示最终的艺术品中圆球的个数和模数 pp

【输出格式】

输出文件名为 toy.out

输入文件仅一行,一个正整数,表示包装盒的高的期望对质数 pp 取模后的值。

样例输入:

3 998244353

样例输出:

499122178

【数据规模与约定】 n200,p1000000007,pn \le 200, p \le 1000000007, p是质数。

Solution

考试时真的不会写啊,看了题解后才会写,水平低呀......

52t2.png

补充:f[i][j] 可以从 g[i-1][j-1] 转移,因为 g[i-1][j-1] 的 i-1 个点构成的森林,将 i 作为每棵树的父亲。其它的应该很好理解吧。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
typedef long long ll;

int n, p;
int dp[202][202], inv[202], f[202][202], g[202][202];
int F[202];
// dp[i][j] i个点森林,j个在第一棵树
// f[i][j] i个点树,深度不超过j概率 g[i][j] i个点森林,深度不超过j概率

inline int qpow(int a,int b){int r=1;for(;b;b>>=1,a=1ll*a*a%p)if(b&1)r=1ll*r*a%p;return r;}

int get(int i,int j);
int get2(int i, int j) {
if(i<=j) return 1;
if(~g[i][j]) return g[i][j];
int r=0;
rep(k,1,i)
(r+=1ll*get(k,j)*get2(i-k,j)%p*dp[i][k]%p)%=p;
return g[i][j]=r;
}
int get(int i, int j) {
if(~f[i][j]) return f[i][j];
return f[i][j]=get2(i-1, j-1);
}

int main() {
freopen("toy.in","r",stdin);
freopen("toy.out","w",stdout);
cin >> n >> p;
inv[1]=1;rep(i,2,n)inv[i]=1ll*(p-p/i)*inv[p%i]%p;
dp[1][1]=1;
rep(i,2,n)rep(j,1,i)
dp[i][j]=(1ll*dp[i-1][j-1]*(j-1)%p*inv[i]%p+1ll*dp[i-1][j]*(i-j)%p*inv[i]%p)%p;
memset(f, -1, sizeof f);
memset(g, -1, sizeof g);
rep(i,1,n) f[0][i]=g[0][i]=1, f[i][0]=g[i][0]=0;
rep(i,2,n) F[i]=get(n,i); F[1]=0;
int ans=0;
rep(i,2,n) (ans+=1ll*(F[i]-F[i-1])*i%p)%=p;
printf("%d\n", (ans+p-1)%p);
return ~~(0^_^0);
}

飘雪圣域(icekingdom)

时间限制:1s空间限制:512MB

【问题描述】

飘雪圣域有 nn 个城镇,编号 1,2,3...n1,2,3...n 。有些城镇之间有道路,且满足任意两点之间有且仅有一条路径。将来会发生 qq 场暴风雪,这场暴风雪之后,只有编号属于 [li,ri][l_{i},r_{i}] 的城市没有受到暴风雪的影响。

请你求出未被暴风雪影响的城市构成的极大连通块数量。

【输入格式】

输入文件名为 icekingdom.in

第一行包含两个正整数 n,qn,q,表示 IceKingdom 的城镇个数和暴风雪次数。

第 2 至第 n 行,每行两个正整数 x,yx,y,表示城镇 xx 和城镇 yy 之间有一条道路。

第 n+1 至第 n+q 行,每行两个正整数 li,ril_{i},r_{i},描述一场暴风雪,含义如题面所述。

【输出格式】

输出文件名 icekingdom.out

输出文件共有 qq 行,第 i 行表示在第 i 场暴风雪之后农业生产地域的个数。

样例输入:

4 3
1 2
2 3
2 4
1 2
1 3
3 4

样例输出:

1
1
2

【数据规模和约定】 n200000,q200000n \le 200000, q \le 200000,对于所有的暴风雪,li<=ril_{i}<=r_{i}

Solution

问题等价于 [l,r][l,r] 间的点之间的连边数记为 num,求 r-l+1-num。 对于 num,我们可以记录一下每个点的连边情况,然后跑莫队。优化下常数,卡着时限可以过......

还有一种 O(n log n)O(n~log~n) 的离线做法(也有在线做法)。 先将询问按照 rr 从大到小排序,考虑持续缩小 rr,解决询问。若当前指针在 rr 处有询问,只需要维护出 querylquery_{l}rr 之间的边数num即可。容易发现只需保证一条边的左端点 >queryl>query_{l} ,并且指针移动前删掉该点 rr 贡献的 ll 端点即可。问题转化为求 [l,r][l,r] 间边的左端点数,用树状数组维护即可。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
#define pii pair<int,int>
#define fi first
#define se second
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

int n, T;
struct Q {
int l, r, id;
bool operator < (const Q &rhs)const{return r>rhs.r;}
}q[200005];
struct E {
int l, r;
bool operator < (const E &rhs)const{return r>rhs.r;}
}e[200005];
int ans[200005];

int t[200005];
#define lowbit(x) (x&-x)
inline void upd(int x, int d) {for(;x<=n;t[x]+=d,x+=lowbit(x));}
inline int get(int x) {
int r=0;
for(;x;r+=t[x],x-=lowbit(x));
return r;
}

int main() {
freopen("icekingdom.in","r",stdin);
freopen("icekingdom.out","w",stdout);
read(n), read(T);
int u, v;
rep(i,1,n-1) read(e[i].l), read(e[i].r);
sort(e+1, e+n);
rep(i,1,T) read(q[i].l),read(q[i].r), q[i].id=i;
sort(q+1, q+T+1);

int cnt=1, skd=1;
rep(i,1,n-1) upd(e[i].l, 1);
for(int i=n;i>=1;--i) {
while(q[skd].r==i) ans[q[skd].id]=q[skd].r-q[skd].l+1-(get(i)-get(q[skd++].l-1));
while(e[cnt].r==i) upd(e[cnt++].l,-1);
}
rep(i,1,T) printf("%d\n", ans[i]);
return ~~(0^_^0);
}

Day 3

今天的题...好难啊qwq 【出题人:租酥雨】           好像被观众们喷了...

zsy.png

基础分治练习题 (cdq)

时间限制:1.5s空间限制:512MB

题目描述

这是一道基础分治练习题。 给你三个数列 {ai},{bi},{ci}\{a_{i}\}, \{b_{i}\}, \{c_{i}\},保证每个数列都恰好是一个排列。你需要求出满足 ai<aj,bi<bj,ci<cja_{i} < a_{j} , b_{i} < b_{j} , c_{i} < c_{j} 的有序对 (i,j)(i, j) 的数目。

输入格式

从文件 cdq.in 中读入数据。

数据的第一行包含一个正整数 nn,表示数列的长度。接下来一行三个非负整数 SA,SB,SCSA, SB, SC

为了避免过量的输入对程序的运行效率产生影响,{ai},{bi},{ci}\{a_{i}\}, \{b_{i}\}, \{c_{i}\} 由以下代码生成:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int N = 2e6+5;
unsigned int SA,SB,SC;int n,a[N],b[N],c[N];
unsigned int rd(){
SA^=SA<<16;SA^=SA>>5;SA^=SA<<1;
unsigned int t=SA;SA=SB;SB=SC;SC^=t^SA;return SC;
}
void gen(int *P){
for (int i=1;i<=n;++i) P[i]=i;
for (int i=1;i<=n;++i) swap(P[i],P[1+rd()%n]);
}
int main(){
scanf("%d%u%u%u",&n,&SA,&SB,&SC);
gen(a);gen(b);gen(c);return 0;
}

输出格式

输出到文件 cdq.out 中。

输出一行一个正整数 ans,表示满足条件的有序对 (i,j)(i, j) 的对数。

样例输入:

5
233 666 667
100000
123 456 789

样例输出:

4
1258889897

数据范围

对于 100%100\% 的数据,保证

Solution

考场真写了个 CDQ 分治...... O(n log2n)O(n~log^{2}n) 显然过不去的吧。

我们考虑计算下面三个东西。

X=i,j[ai<aj][bi<bj]X =\sum_{i,j}[a_{i} < a_{j}][b_{i} < b_{j}]Y=i,j[ai<aj][ci<cj]Y =\sum_{i,j}[a_{i} < a_{j}][c_{i} < c_{j}]Z=i,j[bi<bj][ci<cj]Z =\sum_{i,j}[b_{i} < b_{j}][c_{i} < c_{j}]

对于一对需要算答案的点对 (i,j)(i, j),它一定在 X,Y,ZX,Y,Z 中都被算过 一遍。对于不需要算答案的点对,它一定恰好在 X,Y,ZX,Y,Z 中的一 个里面被计算过一次。

Ans=12(X+Y+Z(2n))Ans =\frac{1}{2}(X + Y + Z -(^{n}_{2}))

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
const int N = 2e6+5;
unsigned int SA,SB,SC;int n,a[N],b[N],c[N];
unsigned int rd(){SA^=SA<<16;SA^=SA>>5;SA^=SA<<1;unsigned int t=SA;SA=SB;SB=SC;SC^=t^SA;return SC;}
void gen(int *P){rep(i,1,n)P[i]=i;rep(i,1,n)swap(P[i],P[1+rd()%n]);}
struct P {int a,b,c;}p[2000005];
bool cmpa(const P&A,const P&B){return A.a<B.a;}
bool cmpb(const P&A,const P&B){return A.b<B.b;}
bool cmpc(const P&A,const P&B){return A.c<B.c;}
#define lowbit(x) (x&-x)
int t[2000005], q[2000005], l[2000005];
inline void upd(int *a,int x){for(;x<=n;++a[x],x+=lowbit(x));}
inline int get(int *a,int x){int r=0;for(;x;r+=a[x],x-=lowbit(x));return r;}

int main(){
scanf("%d%u%u%u",&n,&SA,&SB,&SC);
gen(a);gen(b);gen(c);
register long long X=0, Y=0, Z=0;
rep(i,1,n) p[i].a=a[i],p[i].b=b[i],p[i].c=c[i];
sort(p+1, p+n+1, cmpa);rep(i,1,n)X+=get(t,p[i].b),upd(t,p[i].b);
sort(p+1, p+n+1, cmpb);rep(i,1,n)Y+=get(q,p[i].c),upd(q,p[i].c);
sort(p+1, p+n+1, cmpc);rep(i,1,n)Z+=get(l,p[i].a),upd(l,p[i].a);
printf("%lld\n", (X+Y+Z-1ll*n*(n-1)/2)/2);
return ~~(0^_^0);
}

大火题 (easy)

时间限制:3s空间限制:512MB

题目描述

Cyhlnj 天天切大火题。 有一天他突然觉得切火题没什么意思,于是就翻开了这样的一道题目:

  • 给你三个数 n,G,Ln, G, L,要你求从 {1,2,...,n}\{1, 2, ..., n\} 中选出一个非空子集使这个子集中所有数的最大公因数 (greatest common divisor,GCD) 恰好为 GG,最小公倍数 (least common multiple,LCM) 恰好为 LL 的方案数。

Cyhlnj 觉得这个题太傻逼了,于是他对此进行了一些加强:他会给出 QQ 次询问,每次询问选出的子集必须包含某个正整数 aia_{i} 的前提下,方案数会是多少。

因为答案可能很大,所以你需要输出答案对 998244853998244853 取模后的结果。

输入格式

从文件 easy.in 中读入数据。

数据第一行包含四个正整数 n,G,L,Qn, G, L, Q,意义见题目描述。

接下来 QQ 行每行一个正整数 aia_{i},表示询问选出的子集必须包含某个正整数 aia_{i} 的前提下,方案数会 是多少。

输出格式

输出到文件 easy.out 中。

输出包括 Q+1Q + 1 行,其中第一行一个数表示不加任何限制的情况下满足条件的方案数对 998244853998244853 取模后的结果,接下来 QQ 行每行一个数表示选出的子集中包含某个正整数 aia_{i} 且满足条件的方案数对 998244853998244853 取模后的结果。

样例输入:

6 1 6 4
1
2
3
6

样例输出:

7
5
5
5
5

数据范围

对于 100%100\% 的数据,保证

Solution

Q=0Q=0 时(部分分),对于 gcdgcdlcmlcm 的唯一分解,我们可以分别记录两个数每个质因子的最高次方。那么选出的数的 pp 次幂下界为 gcdgcd 的最高次幂,上界为 lcmlcm 的最低次幂。我们求出的合法方案,每一个质因子 pp,选出的数中里至少有一个数为其下界,至少有一个数为其上界。每个数用两个 01 串维护每个质因子是否为下界/上界即可。

我们可以先预处理出 dp[i][j] 为构成两个串的方案数。如果 aia_{i} 一定要选,那么只需统计 ia[i]i|a[i]的第一个串全为11ja[i]j|a[i]的第二个串全为11 的 dp[i][j] 即可。注意到若 dp[i][j] 符合,dp[i|a[i].first][j|a[i].second] 也是符合的,故 dp[i][j] 被贡献了两次,所以最终答案需要 。 答案同样也是可以预处理的。

时间复杂度

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
#define pii pair<int,int>
#define fi first
#define se second
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}
typedef long long ll;
#define p 998244853
int n, G, L, T, a, S;
int cnt=0, pri[35], num[35];
map<int,pii> R;
map<int,int> ans;
inline void add(int &x,int y){x+=y;if(x>=p)x-=p;}
int dp[666][666];

void init(int x) {
for(int i=2;i*i<=x;++i)if(x%i==0) {
pri[cnt]=i;
while(x%i==0) x/=i,++num[cnt]; ++cnt;
}
if(x>1) pri[cnt]=x,num[cnt++]=1;S=(1<<cnt)-1;
}
void dfs(int u, int res, int R1, int R2) {
if(res>n) return ;
if(u==cnt) {R[res]=make_pair(R1,R2);return ;}
dfs(u+1,res,R1|(1<<u),R2); //empty
int t=pri[u];for(int i=1;i<num[u];++i,t*=pri[u])dfs(u+1,res*t,R1,R2); //else
dfs(u+1,res*t,R1,R2|(1<<u)); //full
}

int main() {
freopen("easy.in","r",stdin);
freopen("easy.out","w",stdout);
read(n),read(G),read(L),read(T);
if(L%G){rep(i,0,T)puts("0");return 0;}
n/=G, L/=G, init(L), dfs(0,1,0,0); **dp=1;
for(auto x:R)for(int i=S;~i;--i)for(int j=S;~j;--j)
add(dp[i|x.se.fi][j|x.se.se],dp[i][j]);
for(auto x:R){ int tmp(0);
for(int i=S;~i;--i)for(int j=S;~j;--j)
if((x.se.fi|i)==S&&(x.se.se|j)==S)add(tmp,dp[i][j]);
ans[x.fi]=(1ll*tmp*(p+1)>>1)%p;
} // dp
printf("%d\n", dp[S][S]);
while(T--) {
read(a);
if(a%G||L%(a/G)) puts("0");
else printf("%d\n", ans[a/G]);
}
return ~~(0^_^0);
}

Day 4

成都七中的 NOIP 模拟赛,好像进错场了。

Day 5

序列(sequence)

时间限制:1s空间限制:512MB

【题目描述】

对于一个长度为偶数的序列 a1,a2,a3,...,ana_{1}, a_{2}, a_{3}, ... , a_{n},定义这个序列为好的序列,当且仅当

定义一个对序列的翻滚操作,使所有元素向前移一个位置,第一个元素移到最后的位置。
现在小 A 有一个长度为偶数的序列 b1,b2,b3,...,bnb_{1}, b_{2}, b_{3}, ... , b_{n},他想知道至少需要翻滚多少次才能使这个序列成为好的序列。

【输入格式】

第一行一个整数 nn 表示序列的长度,保证 nn 为一个偶数。
第二行 nn 个正整数,第 ii 个数表示 bib_{i}

【输出格式】

如果有解,输出一个正整数,表示最少需要翻滚多少次才能使这个序列成为好的序列。
如果没有解,输出 IMPOSSIBLE

样例输入:

6
2 8 7 9 1 3

样例输出:

1

【数据范围】

对于 100%100\% 的数据,

Solution

观察易知,翻滚 kk 次序列为好的等价于 b1,b2,...,b2kb_{1},b_{2},...,b_{2k}b2k+1,...,bnb_{2k+1},...,b_{n} 都为好的。

字符串哈希

可以将串哈希一遍,再反着哈希一遍,枚举 kkO(1)O(1) 判断是否成立即可。时间复杂度 O(n)O(n)

大家应该都会写吧......

KMP字符串匹配

好的序列的本质就是两两匹配之和相同,并且是一个奇数位和一个偶数位匹配。设序列平均数为 xx ,那么设奇数位构成的串为 aa,偶数位构成的串为 bb。变换 bb 串为 2xb1,2xb2,...,2xbn2x-b_{1},2x-b_{2},...,2x-b_{n} ,那么将 bb 翻转后与 aa 求第一个长度为 nn 的匹配即可。时间复杂度 O(n)O(n)

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

#define N 1000005
int n, a[N], b[N], p[N];
long long s;

void kmp() {
reverse(a+1, a+n/2+1);
int j=0; p[1]=0;
rep(i,2,n/2) {
while(j && a[i]!=a[j+1]) j=p[j];
if(a[i]==a[j+1]) j++;
p[i]=j;
} j=0;
rep(i,1,n) {
while(j && b[i]!=a[j+1]) j=p[j];
if(b[i]==a[j+1]) j++;
if(j==n/2) {
printf("%d\n", i-n/2);
exit(0);
}
}
}

int main() {
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
read(n);
int x;
rep(i,1,n) {
read(x); s+=x;
i&1?a[i/2+1]=x:b[i/2]=x;
}
if(s*2%n) return puts("IMPOSSIBLE"), 0;
s=s*2/n; // bas
rep(i,1,n/2) {
b[i+n/2]=b[i]=s-b[i];
if(b[i]<=0) return puts("IMPOSSIBLE"), 0;
}
kmp(); puts("IMPOSSIBLE");
return ~~(0^_^0);
}

拉密(rummikub)

时间限制:1s空间限制:512MB

Description

......

“这个游戏的规则取之于拉密牌。
“每张拉密牌的颜色用 K(黑),R(红),B(蓝),O(橙)中的一个字母表示,点数为 111313 中的一个整数。
“游戏中只使用其中 pp 张固定的、不重复的牌,剩余的牌不使用。游戏进行 rr 轮,每轮独立进行。 游戏开始时,你将得到 kk 张手牌,其余牌均匀随机打乱后组成牌堆。
“此后,你可以从牌堆中摸取牌加入你的手牌,一次只取一张。
“你需要将所有的手牌组成若干个牌组,每张牌在恰好一个牌组中。在摸到任一张牌后达成这个目标即获胜;牌堆为空且未达成目标为失败。
“牌组分为两种:
“群组:不少于三张相同点数的牌,如 R1, B1, O1 或 K2, R2, B2, O2;
“顺组:不少于三张连续点数的同花牌,如 K3, K4, K5 或 R9, R10, R11, R12。需要注意的是,131311 并不能顺次相接。
“获胜时,仍留在牌堆中牌的点数之和即为得分;失败时的得分为零。”
Bendit 思忖片刻,“好啊,来啊!”
这当然是个真正的全靠运气的辣鸡游戏。帮助 Bendit 计算游戏的期望得分吧!

Input
第一行包含两个空格分隔的整数 —— 分别表示游戏牌的数量和游戏的轮数;
第二行包含 pp 个空格分隔的字符串,每个字符串形如 XyXy,其中字符 XX 为花色,正整数 yy 为点数,
描述一张游戏中的拉密牌。游戏牌依输入顺序编号为 1,2,...,p1,2,...,p
接下来r 行每行描述一轮游戏,包含空格分隔的整数 kkh1,h2,...,hkh_{1}, h_{2},..., h_{k} —— 本轮的手牌数量,以及手牌的编号。

Output
对于每一轮游戏依次输出一行,包含一个整数,表示Bendit 的期望得分,对 109+710^{9} + 7 取模。

具体而言,设期望得分为有理数 nd\frac{n}{d} ,输出一个整数 mm,使得 0m<109+70 \leq m < 10^{9} + 7mdn(mod 109+7)m \cdot d \equiv n (\text{mod}~10^{9} + 7)。可以证明,对于任意的nndd,整数 mm 存在且惟一。

样例输入:

6 5
K1 K2 K3 K4 K5 K7
4 1 2 3 4
2 5 1
1 5
1 3
2 3 5
12 6
K1 K3 K4 K5 R1 R2 B1 B2 B3 O1 O2 O3
8 5 6 7 8 9 10 11 12
7 2 1 4 7 8 3 6
7 3 1 4 5 9 2 6
4 1 2 3 4
2 2 3
2 5 6

样例输出:

12
750000007
266666671
233333340
41666671
250000005
200000003
0
880357151
80674606
428095242

数据范围

对于所有数据,有 .

对于所有牌有 X{K,R,B,O},1y13X \in \{'K','R', 'B', 'O'\},1 \leq y \leq 13,同一种牌在游戏牌中出现不超过一次。

Solution

显然,只有某时刻手上的牌为"顺组"和"群组"的组合,才对答案有贡献,否则贡献为 00

考虑状态压缩DP,f[i] 表示初始手上牌的状态。容易发现,"必胜"状态少于 ,那么我们可以预处理出所有"必胜"状态下的答案。

对于 f[i] 的转移,若 ii 二进制下的第 zz 位为 00,则:

f[i|(1<<z-1)]+=f[i]ncount(i)\frac{f[i]}{n-count(i)}       count(i)表示 ii 二进制下 11 的数量

时间复杂度

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define pii pair<int,int>
#define fi first
#define se second
#define mod 1000000007
int n, r, o[500], v[5][15], can[1<<20];
int dp[1<<20], inv[22];
pii p[22]; //卡牌
inline void init() {
char ch; int x;
rep(i,1,n) {
do{ch=getchar();}while(ch!='K'&&ch!='R'&&ch!='B'&&ch!='O');
if(ch=='K')x=1;if(ch=='R')x=2;if(ch=='B')x=3;if(ch=='O')x=4;
p[i].fi=x; scanf("%d",&x); p[i].se=x;
v[p[i].fi][p[i].se] = i;
}
rep(i,1,4)rep(j,1,13) {
int s=0;
rep(k,j,13) {
if(!v[i][k]) break;
s|=1<<v[i][k]-1;
if(k-j>=2) o[++*o]=s;
}
}
rep(j,1,13) {
int a=v[1][j],b=v[2][j],c=v[3][j],d=v[4][j], s;
s=(1<<a-1)|(1<<b-1)|(1<<c-1)|(1<<d-1);
if(a && b && c) o[++*o]=s^(1<<d-1);
if(a && b && d) o[++*o]=s^(1<<c-1);
if(a && c && d) o[++*o]=s^(1<<b-1);
if(b && c && d) o[++*o]=s^(1<<a-1);
if(a && b && c && d) o[++*o]=s;
}

inv[1]=1; rep(i,2,n) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
can[0]=1;
for(int i=0;i<1<<n;++i)if(can[i]) {
rep(j,1,*o)if(!(i&o[j])) can[i|o[j]]=1;
for(int z=0;z<n;++z)if(!(1<<z&i)) dp[i]+=p[z+1].se;
}

for(int i=(1<<n)-1;i;--i)if(dp[i]) {
int t=1ll*dp[i]*inv[n-__builtin_popcount(i)+1]%mod;
for(int z=0;z<n;++z)if(1<<z&i)
if(!can[i^(1<<z)]) (dp[i^(1<<z)]+=t)%=mod;
}
}

int main() {
scanf("%d%d", &n, &r);
init();
int k, h;
while(r--) {
int s=0;
scanf("%d", &k);
while(k--) scanf("%d",&h), s|=1<<h-1;
printf("%d\n", dp[s]);
}
return 0;
}

Day 6

最大公约数(gcd)

时间限制:1s空间限制:512MB

题目描述

最大公约数 GCD(a,b)GCD(a,b) 是指 a,ba,b 共有的因子中最大的那一个。比如说,GCD(12,18)=6GCD(12,18)=6,因为 66 既是 1212 的因子,也是 1818 的因子,而且不存在其他比 66 大的而且也是 12,1812,18 的因子的数。

小明想知道如果给定 n,mn,m,对于 1in,GCD(i,m)1 \leq i \leq n,GCD( i , m ) 的最大值是多少。

输入格式

从文件 gcd.in 中读入数据 第一行有两个用空格隔开的正整数 n,mn,m,含义见题目描述

输出格式

输出到文件 gcd.out 中 一行,只有一个整数,表示对于 1in,GCD(i,m)1 \leq i \leq n , GCD( i , m ) 的最大值。

Solution
mm 质因数分解,找到最大的比 nn 小的数。

数据范围
1n,m1091 \leq n,m \leq 10^{9}

Code


最短路(route)

时间限制:1s空间限制:512MB

题目描述

给出一个包含 nn 个点,mm 条有向边的图,每个点都有独特的标号,点的标号范围为 11nn
对于每条边做一次询问,询问将该条边的方向取反,长度不变,其他边都保持不变是否会使得从 11 号点到 22 号点的最短路径长度相比原始的图变长,变短或者不变。
可能存在重边,即两条边的起点和终点都对应相同;但不存在自环,即不存在某一条边的起点和终点是同一个点。保证原图中存在从 11 号点到 22 号点的路径。

注意,每次只做询问,不对原图产生任何影响。

输入格式

从文件 route.in 中读入数据
第一行包括 2 个用空格隔开的整数,n,mn,m,表示图中有 n(n2)n(n \geq 2)个点,mm 条边。
接下来有 mm 行,描述了原始图中的每条边。
每行有 3 个用空格隔开的正整数,ai,bi,ci(1im)a_{i},b_{i},c_{i}(1 \leq i \leq m)。表示原始的图中有一条从 aia_{i}号点到 bib_{i} 号点的有向边,长度为 cic_{i}。(保证 aia_{i} 不等于 bib_{i}

输出格式

输出到文件 route.out
mm 行,每行 1 个整数,其中第i行的整数 ansians_{i}表示如果将第 ii 条边的方向变成相反的方向,长度不变,其他边都保持不变使得从 11号点到 22 号点的最短距离相对于原图变化的结果。ansians_{i} 的含义如下:

  1. ansians_{i}11 时表示最短距离相对于原图变长或者不存在从1号点到2号点的路径;
  2. ansians_{i}00 时表示最短距离相对于原图不变;
  3. ansians_{i}1-1 时表示最短距离相对于原图变短;
4 5
4 2 7
3 4 6
1 3 5
2 1 18
2 3 12
1
1
1
0
-1

Solution

我们称 1122 的所有最短路径中一定经过的边为 “必经路”。

不妨将本次取反的边记作

若取反的边不在最短路上,那么最短路不会变长。

  • 时,最短路变短。

  • 否则,最短路长度不变。

若取反的边在最短路上,那么最短路不会变短。若不然,可得出矛盾。

route.png

  • 若该边为 “必经路”,那么最短路一定变长。
  • 否则,最短路长度不变。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
#define pii pair<int,int>
#define fi first
#define se second
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}
const int N = 100005;

int h1[N], h2[N], vis[N];
struct Edge {int nxt,v,w;}e1[N],e2[N];
priority_queue<pii,vector<pii>,greater<pii> > q;
long long dis1[N], dis2[N], f[N], g[N];

int n, m;
#define p 998244353

void Dijkstra1() {
memset(vis,0,sizeof vis); memset(dis1,0x3f,sizeof dis1);
q.push(make_pair(0,1)); dis1[1]=0, f[1]=1;
int v;
while(!q.empty()) {
auto u=q.top(); q.pop();
if(vis[u.se]) continue;
vis[u.se]=1;
for(int i=h1[u.se];i;i=e1[i].nxt) {
v = e1[i].v;
if(dis1[v]>dis1[u.se]+e1[i].w) {
dis1[v]=dis1[u.se]+e1[i].w; f[v]=f[u.se];
q.push(make_pair(dis1[v], v));
}
else if(dis1[v]==dis1[u.se]+e1[i].w) {
(f[v]+=f[u.se])%=p;
q.push(make_pair(dis1[v], v));
}
}
}
}
void Dijkstra2() {
memset(vis,0,sizeof vis); memset(dis2,0x3f,sizeof dis2);
q.push(make_pair(0,2)); dis2[2]=0, g[2]=1;
int v;
while(!q.empty()) {
auto u=q.top(); q.pop();
if(vis[u.se]) continue;
vis[u.se]=1;
for(int i=h2[u.se];i;i=e2[i].nxt) {
v = e2[i].v;
if(dis2[v]>dis2[u.se]+e2[i].w) {
dis2[v]=dis2[u.se]+e2[i].w; g[v]=g[u.se];
q.push(make_pair(dis2[v], v));
}
else if(dis2[v]==dis2[u.se]+e2[i].w) {
(g[v]+=g[u.se])%=p;
q.push(make_pair(dis2[v], v));
}
}
}
}

int main() {
read(n), read(m);
int a,b,c;
rep(i,1,m) {
read(a),read(b),read(c);
e1[i]=Edge{h1[a],b,c}; h1[a]=i;
e2[i]=Edge{h2[b],a,c}; h2[b]=i;
}
Dijkstra1(); Dijkstra2();
long long dist=dis1[2], num=f[2];
rep(i,1,m) {
if(dis1[e2[i].v]+dis2[e1[i].v]+e1[i].w==dist) {
if(f[e2[i].v]*g[e1[i].v]%p==num) puts("1");
else puts("0");
}
else {
if(dis1[e1[i].v]+dis2[e2[i].v]+e1[i].w<dist) puts("-1");
else puts("0");
}
}
return ~~(0^_^0);
}

Day 7

树(tree)

时间限制:0.5s空间限制:128MB

【题目描述】

cwystccwystc 是天才学院最优秀的学生。在成功AKNOINOI之后,cwystccwystc 开始思考他智商为什么这么高,他翻出了族谱,开始探究生命的本源。

家谱可以看做一棵以 11 为根的树,第 ii 个人的智商为 wiw_{i}cwystccwystc 会进行 qq 次探究,对于第 ii 次探究,cwystccwystc 初始智商为 cic_{i} ,他将从第 uiu_{i} 个人开始向树根方向探索,直到第 viv_{i} 个人。对于路径上某个人 kk ,若 kk 的智商严格大于 cwystccwystc 的智商,cwystccwystc 会努力学习以达到与 kk 相等的智商。cwystccwystc 想知道对于每次探究,他需要努力学习多少次。

【输入格式】

第一行输入两个整数 n,qn , q ,表示节点数和询问数。第二行输入 nn 个整数 ,表示第 ii 个点的智商。

第三行至第 n+1n+1 行每行输入两个数 x,yx ,y ,表示树上一条边。第 n+2n+2 行至第 n+q+1n+q+1 行每行三个数 u,v,cu,v ,c,表示一次探究。 保证 uuvv 的祖先。

【输出格式】

输出 qq 行,每行一个数表示探究过程中 cwystccwystc 需要努力学习的次数。

【数据规模】

对于 10%10\% 的数据: n1000n \leq 1000
对于另外 30%30\% 的数据:家谱树为一条链。
对于 100%100\% 的数据:1nqwic1000001 \leq n \leq q \leq w_{i} \leq c \leq 100000

Solution

显然,我们只要求出每个点向上跳到的第一个权值比它大的点 pp 就好了。

我们可以用倍增维护向上 2k2^{k} 步的祖先,并维护这段路径上的最大权值,只要这段路径上的最大值 wi\leq w_{i} 就一直往上跳。因此可以在 O(log n)O(log~n) 的时间内处理出一个点的 pp 是谁。

再对 pp 进行倍增,就可以在 O(log n)O(log~n) 的时间内回答一次询问(每跳一步累加次数 2k2^{k} )。

细节处理:若给出的 cwic \geq w_{i} ,则在祖先中先找到第一个比它大的结点。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

int n, q, f[100005][18], dep[100005], p[100005][18], Max[100005][18];
vector<int> d[100005];

void dfs(int u,int fa) {for(int v:d[u])if(v!=fa)dep[v]=dep[u]+1,*f[v]=u,dfs(v,u);}

int main() {
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
read(n), read(q);
rep(i,1,n) read(*Max[i]);
int u, v, c;
rep(i,2,n) {
read(u),read(v);
d[u].push_back(v), d[v].push_back(u);
}
dep[1]=1; dfs(1,0);
rep(i,1,17)rep(x,1,n) {
f[x][i]=f[f[x][i-1]][i-1];
Max[x][i]=max(Max[x][i-1],Max[f[x][i-1]][i-1]);
}
rep(i,1,n) {
u = i;
for(int z=17;~z;--z)if(Max[u][z]<=*Max[i]) u=f[u][z];
*p[i]=u;
}
rep(i,1,17)rep(x,1,n) p[x][i]=p[p[x][i-1]][i-1];

while(q--) {
int tim=0;
read(u),read(v),read(c);
for(int z=17;~z;--z)if(Max[u][z]<=c) u=f[u][z];
if(dep[u]<dep[v]) {puts("0");continue;}

++tim; for(int z=17;~z;--z)if(dep[p[u][z]]>=dep[v]) u=p[u][z],tim+=1<<z;
printf("%d\n", tim);
}
return ~~(0^_^0);
}

环(circle)

时间限制:1s空间限制:128MB

【题目描述】

cwystccwystc 是天才学院最优秀的学生。在成功保送之后, cwystccwystc 开始每天陪妹子散步。天才学院共有 nn 个景点,每两个景点之间有且仅有一条有向边相连,但是 cwystccwystc 只确定了其中的 ee 条边。

妹子希望每天的路线都不相同,而且她还希望 cwystccwystc 能够送她回家 (即回到路径的起点) ,但是 cwystccwystc 很懒,他每天只希望走最短的路线。他想知道他能陪伴妹子的期望天数。(mod=1000000007)(\text{mod}=1000000007)

如果天才学院中不存在满足的路线,那我们会认为 cwystccwystc 在该方案中陪伴妹子的天数为 00

一句话题意:求竞赛图的期望最小环的个数。

【输入格式】

第一行读入两个整数 n,en,e, 表示节点数及已确定的有向边边数。

接下来 ee 行,每行两个整数 x,yx,y 描述 cwystccwystc 确定的边。

【输出格式】

输出一个整数表示期望陪伴妹子的天数。

【数据规模】

对于 100%100\% 的数据,n100000n \leq 100000e1000000e \leq 1000000

Solution

竞赛图中的最小环为三元环

若不然,设存在 nn (n4)(n \geq 4) 元环,那么蓝色边不受方向影响,必构成三元环。

竞赛图最小环.png

首先,没有确定边时,构成三元环个数的期望为

若两点间确定了一条有向边,那么期望个数仍为 122\frac{1}{2^{2}} ,期望不变。

若一点确定了一进一出的有向边,那么期望个数为 12\frac{1}{2} ,期望增加 14\frac{1}{4}

若三点已经确定了一个三元环,那么期望个数为 11,期望增加 34\frac{3}{4} 。但三元环可以在上一步进行 33 次,每次贡献 14\frac{1}{4} 。故可忽略三元环。

若一点确定了两进或两出的有向边,那么期望个数为 00 ,贡献 14-\frac{1}{4}

circle.png

这样我们已经讨论了所有的情况,故只需要统计每个点入边和出边的个数即可。Orz

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

int n, ans;
long long e;
int ru[100005], chu[100005];
#define LL long long
#define p 1000000007

int main() {
int u, v;
read(n), read(e);
ans = 1ll*n*(n-1)%p*(n-2)%p*41666667ll%p;
rep(i,1,e)
read(u),read(v),++ru[v],++chu[u];
rep(i,1,n) {
ans += 250000002ll*((LL)ru[i]*chu[i]%p-((LL)ru[i]*(ru[i]-1)/2%p+(LL)chu[i]*(chu[i]-1)/2%p)%p)%p;
if(ans>=p) ans-=p;
if(ans<0) ans+=p;
}
printf("%d\n", ans%p);
return ~~(0^_^0);
}

礼物(gift)

时间限制:2s空间限制:512MB

【题目描述】

cwystccwystc 是 天才学院最优秀的学生。在成为人生赢家之后, 开始陪妹子逛商店。

商店中总共 nn 个礼物,对于第 ii 个礼物,包含 aia_{i} 个红宝石和 bib_{i} 个绿宝石,cwystccwystc 和妹子想各买一个礼物,然后将其中的宝石串成一条链, cwystccwystc 想知道对于每一种购买方案的排放方案数的和。

由于方案数过大,所以输出对 10000000071000000007 取模。

一句话题意:

【输入格式】

第一行输入一个正整数 nn

第二行到第 n+1n+1 行每行两个正整数 aia_ibib_i 表示第 个礼物中包含 aia_i 个红宝石和 bib_i 个绿宝石。

【输出格式】

输出一个整数表示方案数。

【数据规模】

对于 100%100\% 的数据,n100000,ai+bi20000000n \leq 100000, \sum a_{i}+\sum b_{i} \leq20000000

Solution

考虑维护每个 (aj+bjajt)\binom{a_{j}+b_{j}}{a_{j}-t} ,然后枚举 ii ,暴力枚举 tt 计算。

时间复杂度 O(ai+bi+n)O(\sum a_i +\sum b_i + n)

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}
#define ll long long
#define p 1000000007
#define N 20000000
inline void add(int &x) {if(x>=p)x-=p;}
inline int inc(int x) {return x<0?x+p:x;}
int n, ans, Max;
int fac[N+2], inv[N+2], iinv[N+2], s[N+N+2];
int a[100002], b[100002];

int qpow(int a,int b) {
int r=1;
for(;b;b>>=1,a=(ll)a*a%p)if(b&1) r=(ll)r*a%p;
return r;
}
inline int C(int a,int b) {
if(b<0) return 0;
return (ll)fac[a]*iinv[b]%p*iinv[a-b]%p;
}

int main() {
read(n);
rep(i,1,n) read(a[i]),read(b[i]),Max=max(Max,a[i]+b[i]);
fac[0]=1; rep(i,1,Max) fac[i]=(ll)fac[i-1]*i%p;
iinv[Max]=qpow(fac[Max],p-2);
for(re i=Max-1;i>=0;--i) iinv[i]=(ll)iinv[i+1]*(i+1)%p;

rep(i,1,n)
rep(t,-b[i],a[i]) add(s[t+N]+=C(a[i]+b[i],a[i]-t));
rep(i,1,n)
rep(t,-a[i],b[i])
add(ans+=(ll)inc(s[t+N]-C(a[i]+b[i],a[i]-t))*C(a[i]+b[i],a[i]+t)%p);
printf("%d\n", ans);
return ~~(0^_^0);
}

Day 8

小凯的疑惑(string)

时间限制:1s空间限制:1024MB

【题目描述】

你有一个长度为 nn 的 01 串 ss (下标从 11 开始),现在有 qq 个询问,每次取出一个子串,并将该子串从左到右读,所组成的二进制数计为 PP。你需要进行若干次操作,每次操作可以将 PP 加上或减去 2k2^{k}, kk 可以由你任意选定,但是必须保证 PP 在任意时刻大于等于0,希望你能求出最小的操作步数使 PP 变为 0。另外,题目可能会修改 01 串的任意一位。

【输入格式】

第一行一个数 nn
第二行一个长度为 nn 的字符串 ss
第三行一个数 qq 表示询问与修改次数之和
以下 qq 行,每行格式如下
第一个数 1type21 \leq type \leq 2 表示类型
type=1type = 1 表示是一次询问接下来两个数 l,rl , r 表示询问的区间。
type=2type = 2 表示一次修改接下来两个数 表示把 s[x]s[x] 改为 yy.

【输出格式】

对于每个询问输出一个数表示最少次数。

样例输入:

4
1101
1
1 1 4

样例输出:

3

【数据范围】
对于 20%20\% 的数据,n,q10n, q \leq 10
对于 50%50\% 的数据, n,q5000n, q \leq 5000
对于另外 20%20\% 的数据, 没有 22 操作
对于 100%100\% 的数据, n,q300000n, q \leq 300000

Solution

50pts

我们考虑每一段数的二进制表示,不妨设为 2i\sum 2^{i}

若二进制表示中存在 iii+1i+1,那么将其合并 2i+2i+12i+22i2^{i}+2^{i+1} \Rightarrow 2^{i+2}-2^{i}

当有两个相同的 2i2^{i} 时,将其合并成一个 2i+12^{i+1} 。显然,这样贪心是正确的。时间复杂度 O(n2)O(n^{2})

100pts

既然贪心难以维护, 不妨考虑 dpdp. 设 dpi,0/1dp_{i,0/1} 表示在 ii 处, 之前的状态是 ”000000” 或者 ”000111”,即代表全部被消成 0 或者是有一段后缀的 1.

那么有状态转移方程:

  • 若该位为 00
    • dp[i][0] = min(dp[i-1][0], dp[i][1]+2)
    • dp[i][1] = min(dp[i-1][0]+1, dp[i-1][1]+1)
  • 若该位为 11
    • dp[i][0] = min(dp[i-1][0]+1, dp[i-1][1]+2)
    • dp[i][1] = min(dp[i-1][0], dp[i-1][1])

如果我们把 dpdp 的状态看成一个向量 (c0,c1)(c_{0}, c_{1}),那么每次转移相当于乘上了一个矩阵. 其中矩阵的 ”+” 变成了 ” 取min”, ”×” 变成了 ” + ”。 显然, 这样的矩阵乘法还是满足结合律的。

用一个线段树维护这些矩阵就好了。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0

int n, T, a[300005];
char s[300005];

class Matrix {
public:
int a[2][2];
inline void clean() {a[0][0]=a[0][1]=a[1][0]=a[1][1]=1e9;}
inline void init(int x) {a[1][0]=a[0][1]=1,a[0][0]=x,a[1][1]=x^1;}
Matrix operator *(const Matrix &b) {
Matrix r; r.clean();
rep(i,0,1)rep(j,0,1)rep(k,0,1)r.a[i][j]=min(r.a[i][j],a[i][k]+b.a[k][j]);
return r;
}
};

Matrix t[1200005];
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
inline void update(int x) {t[x]=t[lson(x)]*t[rson(x)];}
void build(int x,int l,int r) {
if(l==r) {t[x].init(a[l]);return;}
int mid=(l+r)>>1;
build(lson(x), l, mid); build(rson(x), mid+1, r); update(x);
}
Matrix get(int x,int l,int r,int ll,int rr) {
if(l==ll&&r==rr) return t[x];
int mid=(l+r)>>1;
if(rr<=mid) return get(lson(x),l,mid,ll,rr);
else if(ll>mid) return get(rson(x),mid+1,r,ll,rr);
else return get(lson(x),l,mid,ll,mid)*get(rson(x),mid+1,r,mid+1,rr);
}
void modify(int x,int l,int r,int p,int z) {
if(l==r) {t[x].init(z);return;}
int mid=(l+r)>>1;
if(p<=mid) modify(lson(x),l,mid,p,z);
else modify(rson(x),mid+1,r,p,z);
update(x);
}

int main() {
scanf("%d%s", &n, s+1);
rep(i,1,n) a[i]=s[i]-48;
build(1,1,n);
scanf("%d", &T);
int opt, l, r;
while(T--) {
scanf("%d%d%d", &opt, &l, &r);
if(opt==1) printf("%d\n", get(1,1,n,l,r).a[0][0]);
else modify(1,1,n,l,r);
}
return ~~(0^_^0);
}

大凯的疑惑(safpar)

时间限制:1s空间限制:1024MB

【题目描述】

你有一个长度为 nn 的序列 {ai}\{ a_i \},现在你需要将这个序列划分成若干段。你需要保证,对于每一段 SS,都有 min(Si)Smax(Si)min ( S_i ) \leq |S| \leq max ( S_i ) 。其中 min(Si)min(S_{i}) 是这一段 aia_{i} 的最小值, max(Si)max(S_{i}) 是这一段 aia_{i} 的最大值,S|S| 是这一段的长度。

你需要求出所有的划分方案数,由于答案很大,你需要对 109+710^{9} + 7 取模。

【输入格式】

一行两个正整数 nn ,表示序列 aia_{i} 的长度。

接下来一行 nn 个正整数,表示序列 aia_{i}

不保证序列 aia_{i} 是一个排列。

【输出格式】

输出一行一个数 ansans, 代表所有的划分方案数对 109+710^{9} + 7 取模的结果。

样例输入:

7
1 6 2 3 4 3 4

样例输出:

6

【样例解释】

所有的划分方案如下

  • [1],[6,2,3,4,3,4]
  • [1,6,2],[3,4,3,4]
  • [1,6,2,3],[4,3,4]
  • [1],[6,2],[3,4,3,4]
  • [1],[6,2,3],[4,3,4]
  • [1,6],[2,3],[4,3,4]

【数据范围】

对于 100%100\% 的数据,保证 n5105n \leq 5 \leq 10^{5}

Solution

注意到 S|S| 增大, min(Si)min(S_{i}) 减小可以枚举确定边界,而 max(Si)max(S_{i} ) 增大,较难维护。故我们可以考虑枚举 max(Si)max(S_{i})

首先从后往前枚举左端点 ll ,再枚举最大值 max(Si)max(S_{i}) (可以用单调栈维护),则右端点 rr 在单调栈下一位之前。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

int n, a[500005], f[500005], s[500005], Min[500005][21];
int top, sta[500005];
#define p 1000000007

int main() {
read(n);
rep(i,1,n) read(a[i]), *Min[i]=a[i];
rep(i,1,20)rep(x,1,n)
Min[x][i] = min(Min[x][i-1],Min[min(x+(1<<i-1),n)][i-1]);
f[n+1]=s[n+1] = 1;
for(int i=n;i>=1;--i) { //枚举左端点
s[i]=s[i+1];
int l=i, w=1e9;
for(int z=20;~z;--z)
if(min(w,Min[l][z])>l+(1<<z)-i&&l+(1<<z)-1<=n) {
w=min(w, Min[l][z]);
l += 1<<z;
}
while(top && a[i]>=a[sta[top]]) --top; //最大值
sta[++top] = i;
for(int j=top;j>=1;--j) {
int r = min(i+a[sta[j]]-1, n);
if(j>1 && r>=sta[j-1]) r=sta[j-1]-1; //右端点
if(sta[j]>r||l>r) continue;
(f[i]+=(s[max(l,sta[j])+1]-s[r+2])%p)%=p;
}
(s[i]+=f[i])%=p;
}
printf("%d\n", (f[1]+p)%p);
return ~~(0^_^0);
}

Day 9

装饰(decoration)

时间限制:1s空间限制:256MB

【题目描述】

林先森家的花园里种着一棵 nn 个点的树,其中 11 号点为根,对于 1<in1 < i \leq nii 号点的父亲节点为 fif_i 号点。

这天,林先森想将这棵树装饰一下,便在每一个节点上挂了一串彩灯,并按照树的结构将所有节点的彩灯连了起来。这样一来,奇妙的现象出现了:若林先森拨动 ii 号点的开关,ii 号点的彩灯状态会发生改变,并且 ii 号节点会在一秒后将这个拨动效果传递给其父亲节点,即在接下来的第 jj 秒钟,ii 号点的距离为 jj 的祖先节点的彩灯状态会发生改变。(开 关/关 开)特别地,如果有多个拨动效果(无论是来自子节点或者林先森的)同时发生在一个节点上,这些效果会两两抵消,若可以正好全部抵消,则该节点的彩灯不会改变状态,也不会继续传递拨动效果。

开始时,所有节点的彩灯都是关闭状态。林先森告诉了你他期望看到的树的样子,并且他每秒钟可以拨动至多一个节点的开关。他希望知道,至少需要几秒钟才能看到他期望看到的树。(不需要是稳定的状态)

【输入格式】

第一行一个正整数 nn

接下来一行 n1n - 1 个正整数,第 ii 个数为 fi+1f_{i}+1

接下来一行 nn 个数,若第 ii 个数为 00 则表示林先森希望 ii 号点的彩灯是关闭状态,若第 ii个数为 11 则表示林先森希望 ii 号点的彩灯是开启状态。

【输出格式】

输出一行一个整数,表示林先森最少需要几秒才能看到他期望看到的树。

样例输入:

4
1 2 3
0 1 1 0

样例输出:

2

【数据范围】

对于 30%30\% 的数据,n8n \leq 8。 对于另 30%30\% 的数据,林先森希望看到所有彩灯都被点亮。 对于 100%100\% 的数据,1n161 \leq n \leq 16

Solution

考虑按时间难以确定状态,那么我们可以考虑时间倒序。

用 f[i][j] 表示倒数第 ii 秒状态为 jj 是否可行。若 f[i-1][j]=1,则枚举这次染哪个点,因为是倒数第 ii 秒将该点染色,故它到它的 i1i-1 级祖先都会被取反,这一步暴力做即可。

另外答案是不超过 nn 的,考虑从下到上染色,当一个节点的子树都被确定,总有一种确定的染色方法,使该点染成目标状态。这样之多只会染 nn 个节点。

Code

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
#include <cstdio>
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0

int n, fa[17], f[17][1<<16];

int main() {
scanf("%d", &n);
rep(i,2,n) scanf("%d",fa+i);
int S=0, b;
rep(i,1,n) {scanf("%d",&b);if(b)S|=1<<i-1;} f[0][S]=1;
if(!S) puts("0"), 0;
rep(k,1,n) {
for(int i=0;i<1<<n;++i)if(f[k-1][i]) {
f[k][i]=1;
rep(z,1,n) {
int r=i;
for(int u=z,t=k;u&&t;--t,u=fa[u]) r^=1<<u-1;
f[k][r] = 1;
}
}
if(f[k][0]) return printf("%d\n",k), ~~(0^_^0);
}
}

Day 10

白色糖果(leset)

时间限制:1s空间限制:512MB

【题目描述】

今天是万圣节!Leaves准备将自己的最喜欢的糖果送给你们!

最初,善良可爱爱党爱国友善敬业严谨严肃认真体贴暖心感性而又不失理性的 Leaves 手上有含有三个数字糖果的可重集合:

{01,11,10}\left \{ \frac{0}{1} , \frac{1}{1} , \frac{1}{0} \right \}

其中 {10}\{ \frac{1}{0} \} 可看作是无穷大。

在很久很久以前,Leaves 最喜欢的数是 11\frac{1}{1}众所周知,男人都是善变的。你需要支持以下两个 操作。

  • L 操作,选中这个集合中,小于等于当前你喜欢的数的最大的数(不 包含当前这个数)。
  • R 操作,选中这个集合中,大于等于当前你喜欢的数的最小的数(不 包含当前这个数)。

若你当前最喜欢的数是 ab\frac{a}{b} ,选中的数字是 cd\frac{c}{d},则将 a+cb+d\frac{a+c}{b+d} 约分后放入这个集合。众所周知,男人都是喜新厌旧的。所以会把新加入的这个数作为自己喜欢的数。

但是 Leaves 是这样子的人,加之最近心情烦闷,所以咕咕了。于是 Leaves 就把这个任务交给看起来更合适的你啦,他想请你回答,最喜欢的那个数字糖果是多少?

【输入格式】

第一行一个整数。表示字符串 SS 长度。

第二行一个字符串 SS,包含若干个复合操作。一个复合操作由两部分组成。操作串和重复次数。

具体表现形式为一个由 LR 组成的字符串和一个整数。例如 LRL3 ,其意义为将 LRL 这个操作重复三次。

【输出格式】

一行一个整数。

表示答案对 998244353998244353 取模的结果:即设答案化为最简分数后的形式为 ,其中 aabb 互质,你需要输出整数 xx 使得 bxa(mod 998244353)bx \equiv a (\text{mod}~998244353)0x9982443530 \leq x \leq 998244353。(可以证明这样的是唯一的)

样例输入:

2
R4
6
L1R2L1

样例输出:

5
285212673

【数据范围】

保证在每一次操作结束后,Leaves 喜欢的数字的分母不 会是 998244353998244353 的倍数。
对于 10%10\% 的数据,保证字符串中只会出现 R 或只出现 L
对于另外 40%40\% 的数据,保证 S105|S| \leq 10^{5},所有出现数字 10\leq 10
对于 100%100\% 的数据,保证 S106|S| \leq 10^{6},所有出现数字

Solution

day10-1.png

约分是逗你玩的,显然每次操作后的分数都是最简分数。

考虑递推,每次新加的数都是从之前的两个数变换过来的,并且次递推后,递推式只会变化一个数。(具体见程序 Subtask2

设递推式的两个分数为 a,b(ab)a , b ( a \leq b ),生成的数为 cc ,那么 cc 一定在 a,ba,b 的中间(a<c<ba < c < b

  • 进行L操作: b=c,c=a+cb=c, c=a+c
  • 进行R操作: a=c,c=b+ca=c, c=b+c

100pts

递推我们可以用矩阵优化。

设原矩阵为:

[000acb000]\begin{bmatrix} 0 & 0 & 0 \\ a & c & b \\ 0 & 0 & 0 \end{bmatrix}

对于 LR 操作,我们可分别视作以下两个矩阵运算:

[110011000][000110011]\begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix}

就好了。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
#define pii pair<int,int>
#define fi first
#define se second
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

int n;
char s[1000005];
#define p 998244353

int qpow(int a, int b) {
int r=1;
for(;b;b>>=1,a=1ll*a*a%p)if(b&1) r=1ll*r*a%p;
return r;
}

inline void subtask1() {
int num=1, vis[2]={0,0};
rep(i,1,n) {
if(s[i]=='L') vis[0]=1;
if(s[i]=='R') vis[1]=1;
}
if(vis[0]&&vis[1]) return ;
int tot=0;
rep(i,2,n) {
if(!isdigit(s[i])) ++num;
else (num*=s[i]-48)%=p, tot+=num, num=0;
}
if(*vis) printf("%d\n", qpow(tot+1,p-2));
else printf("%d\n", tot+1);
exit(0);
}

pii operator + (const pii&a, const pii&b) {return make_pair(a.fi+b.fi, a.se+b.se);}
inline void MOD(pii &a) {if(a.fi>=p)a.fi-=p;if(a.se>=p)a.se-=p;}
int q[1000005], siz;
inline void subtask2() {
pii a=make_pair(0,1), b=make_pair(1,0), c=make_pair(1,1);
rep(i,1,n) {
if(!isdigit(s[i])) q[++siz]=s[i]=='L'?0:1;
else {
int k=0;
while(isdigit(s[i])) k=k*10+s[i++]-48;
while(k--)rep(z,1,siz) {
if(!q[z]) b=c, c=a+c;
else a=c, c=b+c;
MOD(c);
}
siz=0; --i;
}
}
printf("%d\n", (int)(1ll*c.fi*qpow(c.se,p-2)%p));
}

class Matrix {
public:
int a[3][3];
Matrix() {memset(a,0,sizeof a);}
inline void init() {memset(a,0,sizeof a);rep(i,0,2)a[i][i]=1;}
inline void init1() {memset(a,0,sizeof a);a[0][0]=a[0][1]=a[1][1]=a[1][2]=1;}
inline void init2() {memset(a,0,sizeof a);a[1][0]=a[1][1]=a[2][1]=a[2][2]=1;}
Matrix operator *(const Matrix &b) {
Matrix r;
rep(i,0,2)rep(j,0,2)rep(k,0,2) {
r.a[i][j]+=1ll*a[i][k]*b.a[k][j]%p;
if(r.a[i][j]>=p) r.a[i][j]-=p;
}
return r;
}
void operator *=(const Matrix &b) {*this = *this * b;}
};

Matrix qpow(Matrix a,int b) {
Matrix r; r.init();
for(;b;b>>=1,a*=a)if(b&1) r=r*a;
return r;
}

inline void debug(Matrix M) {
rep(i,0,2) {
rep(j,0,2) printf("%d ", M.a[i][j]);
putchar('\n');
}
puts("-------------------------");
}

inline void subtask3() {
Matrix r, M, t; r.init();
rep(i,1,n) {
if(!isdigit(s[i])) q[++siz]=(s[i]=='L'?0:1);
else {
int k=0;
while(isdigit(s[i])) k=k*10+s[i++]-48;
M.init();
rep(z,1,siz) {
if(!q[z]) t.init1(), M *= t;
else t.init2(), M *= t;
}
r *= qpow(M, k);
siz=0; --i;
}
}
int a=0, b=0;
b+=r.a[0][1], a+=r.a[1][1], b+=r.a[1][1];
if(b>=p) b-=p;
a+=r.a[2][1];
if(a>=p) a-=p;
printf("%d\n", (int)(1ll*a*qpow(b,p-2)%p));
}

int main() {
freopen("leset.in","r",stdin);
freopen("leset.out","w",stdout);
read(n);
scanf("%s", s+1);
// subtask1();
// subtask2();
subtask3();
return ~~(0^_^0);
}

小U的女装(femaledress)

时间限制:1s空间限制:512MB

【题目描述】

S 国的小 U 立过了无数的女装 flag。他为了偿还,决定去 S 国的首都 Girlfriend 城买女装。

GirlFriend 城由 nn 个小镇组成,其中小镇之间有 mm 条双向道路,每条道路连接着两个小镇。不过由于 Girlfriend 城的城市建设者因为找不到 Girlfriend 而无心工作,不保证任意两个小镇可以通过这些双向道路直接或间接地到达。其中每一个小镇和每一条道路的中间都设有一个女装店。在每家店最多只能购买一件女装。 而道路中间的女装店的店主与道路两端的女装店的店主构成竞争关系,如果他在道路中间和道路两端中的一端同时买了女装,那么这两家店就会由于嫉妒抛弃自己的 Girlfriend 打起来。因此,如果小 U 在道路上的女装店买女装,就不能在道路连接的两个小镇买女装。

现在小 U 想知道他自己最多能够买多少件女装,以及他有多少种方案能够买到这么多女装。可是小 U 已经有一段时间不去处理这些有趣的问题了,所以,他想让你帮他解决这两个问题。由于第二个问题的答案太大,请你输出答案模 998244353998244353 的结果。

【输入格式】

第一行两个用空格分隔的正整数 n,mn,m,分别表示 Girlfriend 城的小镇数和道路数。

接下来 mm 行,第 ii 行两个正整数 ui,viu_{i},v_{i},表示第 ii 条道路连接的两个城市的编号.(1ui,vin1 \leq u_{i},v_{i} \leq n)

【输出格式】 共两行,第一行表示他最多能够买多少件女装,第二行表示他买女装的最优方案的数量。

即便你不能解决两个问题中的一个,你也需要输出两行答案,否则会因为格式错误而无法得分。具体的得分细则将在子任务中解释。

样例输入:

2 1
1 2
7 7
1 2
2 3
3 1
4 5
5 6
4 6
4 7

样例输出:

2
1
7
6

此处省略500字......

【数据范围】

对于所有数据,1100000,m3000001 \leq 100000, m \leq 300000

如果你答对第一问,你会得到该测试点 50%50\% 的分数。在答对第一问的基础上答对第二问,你才能得到 100%100\% 的分数。
保证给出的道路没有连接同一个小镇,且没有两条道路连接的小镇相同。

Solution

对于一个强联通的图,那么在选择图中的所有边是最优的。若一个强联通的图有一个分支形如一棵树,那么分支可以任意选择(因为强联通图全选边)。

分支有一条边连在强联通上,所以有 nn 条边 nn 个点。于是可以将相邻的点和指向父亲的边组成一组,两者之间只能选一个,所以最多选 nn 个。那么第一问就解决了(题解中有严格证明......

对于方案数,在强联通上的点有两种可能。

  • 为一个简单环,多了一种强联通全取点的情况,该联通块方案额外+1
  • 另外的,每个点都可能连出一个分支,这个点可以贡献它子树的方案数,可以用树形dp解决。

所以拓扑一遍,在强联通的点的子树上作dp就行了。注意细节。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}
#define N 600005
#define p 998244353
int __,h[N],to[N],nxt[N],used[N],ru[N];
inline void add(int u,int v) {
nxt[__]=h[u],to[h[u]=__++]=v,++ru[u];
nxt[__]=h[v],to[h[v]=__++]=u,++ru[v];
}

int n, m, point, edge;
int vis[N], f[N][2], o;

void get(int u) {
vis[u]=1, ++point;
for(int i=h[u];~i;i=nxt[i])if(!used[i>>1]) {
used[i>>1]=1, ++edge;
if(!vis[to[i]]) get(to[i]);
}
}
queue<int> q;
void topo() {
rep(i,1,n)if(ru[i]==1) q.push(i),vis[i]=1;
while(!q.empty()) {
int u=q.front(); q.pop();
for(int i=h[u];~i;i=nxt[i])if(!vis[to[i]]) {
--ru[to[i]];
if(ru[to[i]]==1) q.push(to[i]),vis[to[i]]=1;
}
}
}
void dfs(int u,int fa) {
f[u][0]=f[u][1]=1;
for(int i=h[u];~i;i=nxt[i])if(to[i]!=fa) {
dfs(to[i],u);
f[u][0]=(long long)f[u][0]*f[to[i]][0]%p;
f[u][1]=(long long)f[u][1]*(f[to[i]][0]+f[to[i]][1])%p;
}
}
int DFS(int u) {
int s=1; vis[u]=1;
if(ru[u]!=2) o=0;
for(int i=h[u];~i;i=nxt[i]) {
if(ru[to[i]]==1) {
dfs(to[i],u);
s=1ll*s*(f[to[i]][0]+f[to[i]][1])%p;
}
else if(!vis[to[i]]) s=1ll*s*DFS(to[i])%p;
}
return s;
}

int main() {
//freopen("femaledress.in","r",stdin);
//freopen("femaledress.out","w",stdout);
memset(h,-1,sizeof h);
read(n), read(m);
static int u, v;
while(m--) read(u),read(v),add(u,v);
int ans=0;
rep(i,1,n)if(!vis[i]) point=edge=0,get(i),ans+=max(point,edge);
printf("%d\n", ans);
memset(vis,0,sizeof vis);
topo(); ans=1;
rep(i,1,n)if(!vis[i]) o=1,ans=1ll*ans*(DFS(i)+o)%p;
printf("%d\n", ans);
return ~~(0^_^0);
}

Day 11

这出题人写的题面......体验好差......

练功(practice)

时间限制:1s空间限制:128MB

【题目描述】

题意简述:给定三个正整数 a,b(ab),ka,b(a \geq b),k ,每次可以对 aa 进行两种操作:

  • aa 变为 a1a-1
  • [2,k][2,k] 中的选择数 pp ,将 aa 变为 aa%pa-a\%p

求使得 aa 变为 bb 的最小次数。

【输入格式】

一行一个整数 TT,表示有 TT 场练功预约。
接下来 TT 行,每行三个整数 a,b,ka,b,k,分别表示 Luvwgyx 的铁布衫的两个参数和 AKMer 最大会打出的功力成数。
数据保证 ab,k2a \leq b, k \leq 2

【输出格式】

一共 TT 行,每行一个整数表示 AKMer 至少要打多少拳。

样例输入:

3
10 1 4
6 3 10
1000000000000000000 1 3

样例输出:

6(6拳:4成功力,3成功力,4成功力,1成功力打3拳;铁布衫变化:10-->8-->6-->4-->3-->2-->1)
2
666666666666666667

【数据范围】

对于 30%30\% 的数据: ,因为 LuvwgyxAKMer 双排修行太累了,所以发挥不出全部功力。
对于另外 10%10\% 的数据: k=2k=2,因为 AKMer 干了太多不可描述之事之后最多发挥两成功力。
对于100%的数据: T10T \leq 10ba108b \leq a \leq 10^{8}k15k \leq 15 ,两人皆尽全力,练个酣畅淋漓。

Solution

注意到 kk 非常小,尝试往这方面想。
首先观察到操作二的本质是将 aa 变为小于 aa 且为 pp 的倍数的最大数。那么当 aa 跳到 lcm{2,3,...,k}lcm\{2,3,...,k\} 时,一定不能进行操作2。

lcm{2,3,...,15}=360360lcm\{2,3,...,15\}=360360,所以可以对序列进行分块,预处理出给定 kk 时,跳一个 360360360360 的倍数的完整的(从 360359360359 跳到 00 mod p\text{mod}~p)块需要多少步。那么对于 aa 跳到 bb 只要暴力跳两端到 360360360360 的倍数就可以直接算了。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
const int s = 360360;

int T, k, f[s+1];
long long a, b, ans;

inline int sol(int a,int b,int k){
memset(f,0x3f,sizeof f); f[a]=0;
for(int i=a;i>b;i--) {
f[i-1] = min(f[i-1],f[i]+1);
rep(z,3,k) f[i-i%z]=min(f[i-i%z],f[i]+1);
}
return f[b];
}

int main() {
scanf("%d", &T);
while(T--){
scanf("%lld%lld%d",&a, &b, &k);
ans=1ll*sol(s,0,k)*(a/s-b/s-1)+sol(a%s,0,k)+sol(s,b%s,k);
printf("%lld\n",ans);
}
return ~~(0^_^0);
}

Day 12

石子(stone)

时间限制:0.5s空间限制:128MB

【题目描述】

AlexAlex 正在和 zywzyw 玩游戏,总共有 nn 堆石子,AlexAlex先手,两人轮流操作。
定义一个操作为选择 nn 堆中的任意一堆,若当前选择的石子数 <n < n 则当前操作者胜利,否则移除剩下的 n1n-1 堆,然后将选择的那堆石子分为 nn 堆。
AlexAlex 想知道他能否有必胜的策略,这样 zywzyw 就会觉得 AlexAlex 很强。

【输入格式】

第一行一个正整数 TT,表示总共有 TT 组数据
对于每组数据,共两行。
第一行一个正整数 nn 表示石子堆数
第二行 nn 个非负整数, aia_{i} 表示第 ii 堆的石子个数。

【输出格式】

输出 TT
对于第 ii 组询问,若 AlexAlex 必胜,则输出 Win ,否则输出 Lose

【数据范围】

对于 30%30\% 的数据,n=2n=2
对于 60%60\% 的数据,n5,ai100n \leq 5, a_{i} \leq 100
对于 100%100\% 的数据,n100000,ai1018,n1000000n \leq 100000, a_{i} \leq 10^{18}, \sum n \leq 1000000

Solution

显然,拿出的石子数 [n,n21]\in [n,n^{2}-1] 先手必输,拿出的石子数 [n2,n3n]\in [n^{2},n^{3}-n] 先手必胜。其区间跨度为 n32n+1n^{3}-2n+1

下面归纳证明,当且仅当石子数在模 n32n+1n^{3}-2n+1[n,n21]\in [n,n^{2}-1] 先手必败。

首先,设结论对 kk 成立,即石子数 时,先手必败。现证明结论对 k+1k+1 也成立。

石子数模 n32n+1n^{3}-2n+1 [n,n21][n , n^{2}-1] 先手必败,其和为 [n2,n3n][n^{2},n^{3}-n] 故当且仅当石子数 可以均分石子使得先手必胜,且两端分别为符合要求的上下界。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
int n, T;

int main() {
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
scanf("%d", &T);
while(T--) {
scanf("%d", &n); long long x; int f=0;
rep(i,1,n) {
scanf("%lld", &x);
if(x<n) f=1;
else {
x-=n-1;
x=(x-1)%(1ll*n*n*n-2*n+1)+1;
if(x>1ll*n*n-n) f=1;
}
}
puts(f?"Win":"Lose");
}
return ~~(0^_^0);
}