2021-11-04 提高模拟赛 题解

发表于 分类于

2021.11.042021.11.04 提高模拟赛，题解。

T1 儒略秒 (julian)

题面

题目描述

为了使题目更复杂，天坟学家们使用儒略秒（Julian second）来表达时刻。所谓儒略秒，其定义为从公元前 47134713 年 11 月 11 日正午 1212 点 00 分 00 秒到此后某一时刻间所经过的秒数，不满一秒者用小数表达。若利用这一天坟学历法，则每一个时刻都将被均匀的映射到数轴上，从而得以很复杂的计算它们的差值。

现在，给定一个不含小数部分的儒略秒，请你帮忙计算出该儒略秒所对应的公历时刻。

我们现行的公历为格里高利历（Gregorian calendar），它是在公元 15821582 年由教皇格里高利十三世在原有的儒略历（Julian calendar）的基础上修改得到的（注：儒略历与儒略秒并无直接关系）。具体而言，现行的公历日期按照以下规则计算：

  1. 公元 15821582 年 1010 月 1515 日 00 时 00 分 00 秒（含）以后：适用格里高利历，每年一月 3131 天、 二月 2828 天或 2929 天、三月 3131 天、四月 3030 天、五月 3131 天、六月 3030 天、七月 3131 天、八月 3131 天、九月 3030 天、十月 3131 天、十一月 3030 天、十二月 3131 天。其中，闰年的二月为 2929 天，平年为 2828 天。当年份是 400400 的倍数，或日期年份是 44 的倍数但不是 100100 的倍数时，该年为闰年。
  2. 公元 15821582 年 1010 月 55 日 00 时 00 分 00 秒（含）至 1010 月 1414 日 2323 时 5959 分 5959 秒（含）：不存在，这些时间被删除，该年 1010 月 44 日 2323 时 5959 分 5959 秒之后为 1010 月 1515 日 00 时 00 分 00 秒。
  3. 公元 15821582 年 1010 月 44 日以前：适用儒略历，每月天数与格里高利历相同，但只要年份是 44 的倍数就是闰年。
  4. 尽管儒略历于公元前 4545 年才开始实行，且初期经过若干次调整，但今天人类习惯于按照儒略历最终的规则反推一切 15821582 年 1010 月 44 日之前的时间。注意，公元零年并不存在，即公元前 11 年的下一年是公元 11 年。因此公元前 11 年、前 55 年、前 99 年、前 1313 年⋯\cdots以此类推的年份应视为闰年。
  5. 为保持协调世界时接近于世界时时刻，由国际计量局统一规定在年底或年中对协调世界时增加或减少 11 秒的调整。由于地球自转的不均匀性和长期变慢性（主要由潮汐摩擦引起的），会使世界时（民用时）和原子时之间相差超过到 ±0.9\pm 0.9 秒时，就把协调世界时向前拨 11 秒（负闰秒，最后一分钟为 5959 秒）或向后拨 11 秒（正闰秒，最后一分钟为 6161 秒）；闰秒加在公历年末或公历六月末。目前，全球已经进行了 2727 次闰秒，均为正闰秒（只需要考虑这 2727 次闰秒 除非你可以模拟原子时）。
年份 66 月 3030 日 23:59:6023:59:60 1212 月 3131 日 23:59:6023:59:60
19721972 +1s+1\text{s} +1s+1\text{s}
19731973 −- +1s+1\text{s}
19741974 −- +1s+1\text{s}
19751975 −- +1s+1\text{s}
19761976 −- +1s+1\text{s}
19771977 −- +1s+1\text{s}
19781978 −- +1s+1\text{s}
19791979 −- +1s+1\text{s}
19811981 +1s+1\text{s} −-
19821982 +1s+1\text{s} −-
19831983 +1s+1\text{s} −-
19851985 +1s+1\text{s} −-
19871987 −- +1s+1\text{s}
19891989 −- +1s+1\text{s}
19901990 −- +1s+1\text{s}
19921992 +1s+1\text{s} −-
19931993 +1s+1\text{s} −-
19941994 +1s+1\text{s} −-
19951995 −- +1s+1\text{s}
19971997 +1s+1\text{s} −-
19981998 −- +1s+1\text{s}
20052005 −- +1s+1\text{s}
20082008 −- +1s+1\text{s}
20122012 +1s+1\text{s} −-
20152015 +1s+1\text{s} −-
20162016 −- +1s+1\text{s}

输入格式

从 julian.in 中读入数据。

第一行一个整数 QQ，表示询问的组数。

接下来 QQ 行，每行一个非负整数 rir_i，表示一个儒略秒。

输出格式

输出答案到 julian.out 中。

对于每一个儒略秒 rir_i，输出一行表示时刻的字符串 sis_i。共计 QQ 行。sis_i 的格式如下：

  1. 若年份为公元后，输出格式为 Day Month Year Hour Minute Second。其中日（Day）、月（Month）、年（Year）、时（Hour）、分（Minute）、秒（Second）均不含前导零，中间用一个空格隔开。例如：公元 20202020 年 1111 月 77 日正午 1212 点 00 分 00 秒，输出为 7 11 2020 12 0 0。
  2. 若年份为公元前，输出格式为 Day Month Year Hour Minute Second BC。其中年（Year）输出该年份的数值，其余与公元后相同。例如：公元前 841841 年 22 月 11 日正午 1212 点 00 分 00 秒，输出为 1 2 841 12 0 0 BC。
  3. 若时刻为闰秒，该时刻的秒（Second）为 6060。

样例

样例输入 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
19
1
12
123
1234
12345
123456
1234567
12345678
123456789
1234567890
12345678909
123456789098
1234567890987
12345678909876
123456789098765
1234567890987654
12345678909876543
123456789098765432
1234567890987654321

样例输出 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1 1 4713 12 0 1 BC
1 1 4713 12 0 12 BC
1 1 4713 12 2 3 BC
1 1 4713 12 20 34 BC
1 1 4713 15 25 45 BC
2 1 4713 22 17 36 BC
15 1 4713 18 56 7 BC
23 5 4713 9 21 18 BC
30 11 4710 9 33 9 BC
14 2 4674 11 31 30 BC
19 3 4322 7 15 9 BC
10 2 801 12 31 38 BC
18 10 34409 17 16 0
21 11 386506 16 44 9
21 10 3907477 11 25 38
19 12 39117186 6 20 27
25 7 391214278 3 28 36
16 7 3912185194 22 50 5
25 4 39121894354 0 24 54

样例输入 2

1
2
3
4
3
212207860823
212207860824
212207860825

样例输出 2

1
2
3
30 6 2012 23 59 59
30 6 2012 23 59 60
1 7 2012 0 0 0

数据范围

对于 100%100\% 的数据，1≤Q≤1051\le Q\le 10^5，0≤ri<2630\le r_i<2^{63}。

测试点编号 分值 Q=Q= ri<r_i<
1∼21\sim 2 2020 10310^3 4320043200
3∼43\sim 4 2020 10410^4 2.16×1092.16\times 10^9
5∼65\sim 6 2020 10510^5 210945556800210945556800
7∼107\sim 10 4040 10510^5 2632^{63}

题解

原题：https://www.luogu.com.cn/problem/T156694

跟儒略日是一个思路，这里讲一下出题人的实现。

先把 rr 加上 4320043200，使其从 00 时 00 分 00 秒开始。

15821582 年前，直接跳若干个四年，剩下四年处理一下，这是好做的。

15821582 年特殊处理。

再跳到 16001600 年，之后每 400400 年跳一次，然后剩下 400400 年单独处理，虽然是 O(400T)O(400T) 的，但是正常的实现都不会 TLE。

对于 2727 个闰秒，我们先打表存下这些闰秒的答案。然后对于一个 rr，如果它刚好是一个闰秒，直接输出；否则求出在它之前的闰秒个数 xx，然后先当作没有闰秒直接跳，然后再往前走 xx 秒即可。

注意如果用这种实现，rr 要开 unsigned long long。时间复杂度为 O(400T)O(400T)，空间复杂度为 O(1)O(1)。

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>
#define il inline
#define ll long long
#define ull unsigned long long
const ull O=60,H=3600,D=24*H,Y=365*D,Y1=181*D,Y2=Y-Y1,M[]={0,31*D,28*D,31*D,30*D,31*D,30*D,31*D,31*D,30*D,31*D,30*D,31*D},S1=1461*D,S2=100*S1-3*D,T1=1573*S1+731*D,T2=720*D,T3=4*S1,R[]={0,210945556800,R[1]+Y2+1,R[2]+Y+1,R[3]+Y+1,R[4]+Y+1,R[5]+Y+D+1,R[6]+Y+1,R[7]+Y+1,R[8]+Y+1,R[9]+Y+D+Y1+1,R[10]+Y+1,R[11]+Y+1,R[12]+Y+D+Y+1,R[13]+Y+Y+Y2+1,R[14]+Y+Y+D+1,R[15]+Y+1,R[16]+Y+Y1+D+1,R[17]+Y+1,R[18]+Y+1,R[19]+Y+Y2+1,R[20]+Y+D+Y1+1,R[21]+Y+Y2+1,R[22]+7*Y+D+D+1,R[23]+3*Y+D+1,212207860824,R[25]+3*Y+1,R[26]+Y+D+Y2+1},U[]={0,1972,1972,1973,1974,1975,1976,1977,1978,1979,1981,1982,1983,1985,1987,1989,1990,1992,1993,1994,1995,1997,1998,2005,2008,2012,2015,2016},V[]={0,6,12,12,12,12,12,12,12,12,6,6,6,6,12,12,12,6,6,6,12,6,12,12,12,6,6,12};

int tt,s,o,h,d,m,b; ll y; ull r,t;

il bool Run(){return y<1582?y%4==0:y%400==0||y%4==0&&y%100;}

il int GetY(){return Y+Run()*D;}

il int GetM(){if (m==2) return M[m]+Run()*D; if (m==10&&y==1582) return 21*D; return M[m];}

il void Jump()
{
    while (1) if (r>=GetY()) r-=GetY(),y++; else break;
    while (1) if (r>=GetM()) r-=GetM(),m++; else break;
    d+=r/D,r%=D,h+=r/H,r%=H,o+=r/O,r%=O,s=r; if (y==1582&&m==10&&d>4) d+=10;
}

il void Back()
{
    if (t==R[b+1]){y=U[b+1],m=V[b+1],d=30+(m>6),h=23,o=59,s=60; return;}
    while (b--)
    {
        s--; if (s<0) s+=O,o--;
        if (o<0) o+=O,h--;
        if (h<0) h+=24,d--;
        if (d<1)
        {
            if (--m<1) y--,m=12,d=31;
            else d=GetM()/D;
        }
    }
}

int main()
{
    freopen("julian.in","r",stdin),freopen("julian.out","w",stdout);

    scanf("%d",&tt);
    while (tt--)
    {
        scanf("%llu",&r),r+=D/2,y=-4712,m=d=1,b=h=o=s=0;
        if (r<=T1){y+=r/S1*4,r%=S1; goto C;} r-=T1,y=1582;
        if (r<=T2){if (r>=355*D) r-=355*D,y++; goto C;} r-=T2,y=1584;
        if (r<=T3){y+=r/S1*4,r%=S1; goto C;} r-=T3,y=1600;
        b=std::lower_bound(R+1,R+28,t=r+T1+T2+T3-D/2)-R-1,y+=r/S2*400,r%=S2;
        C: Jump(),Back(),printf("%d %d %lld %d %d %d ",d,m,y<1?1-y:y,h,o,s),puts(y<1?"BC":"");
    }

    return 0;
}

T2 躲猫猫 (hideseek)

题面

题目描述

Early 和 Vxlimo 都是卷王。

但是 Vxlimo 是光明正大卷的，是明卷王，而 Early 则喜欢偷偷卷，是鬼卷王。

Vxlimo 想把 Early 抓过来一起光明正大地卷，而 Early 则想继续掩盖其卷的事实，于是两人在教学楼里玩起了躲猫猫。

教学楼可以抽象成一个 nn 行 mm 列的网格图，两个格子是相邻的当且仅当两个格子有公共边。一个房间为若干个相邻格子的集合，教学楼里一共有 kk 个房间。

Vxlimo 会进行 qq 次搜查，每次会搜查第 aa 到 cc 行与第 bb 到 dd 列所组成的矩形范围内的格子。每次搜查前，Vxlimo 想知道她要搜查多少个不同的房间。她找到了聪明的你，请你帮她解决这个问题。

输入格式

从 hideseek.in 中读入数据。

第一行四个正整数 n,m,k,qn,m,k,q，表示教学楼的行数、列数，房间的数量和 Vxlimo 搜查的次数。

接下来 nn 行每行 mm 个正整数，第 ii 行第 jj 个正整数为 si,js_{i,j}，表示这个格子属于哪个房间。

接下来 qq 行每行四个正整数 ai,bi,ci,dia_i,b_i,c_i,d_i，表示第 ii 次搜查的范围。

输出格式

输出答案到 hideseek.out 中。

共 qq 行每行一个正整数，表示这次搜查中 Vxlimo 要搜查的不同的房间的数量。

样例

样例输入 1

1
2
3
4
5
6
7
8
9
10
11
5 6 5 5
1 1 1 1 3 3
1 1 2 1 3 4
2 2 2 3 3 4
2 2 3 3 4 4
5 5 5 5 5 4
1 1 5 6
4 5 5 6
1 2 2 3
2 1 3 4
1 1 5 5

样例输出 1

1
2
3
4
5
5
2
2
3
5

样例 2

见附加文件下 hideseek/hideseek2.in 和 hideseek/hideseek2.ans。

数据范围

对于 100%100\% 的数据，1≤n,m,k≤20001\le n,m,k\le 2000，1≤q≤50001\le q\le 5000，1≤si,j≤k1\le s_{i,j}\le k。

测试点编号 n,m,k≤n,m,k\le q≤q\le 特殊性质
1∼21\sim 2 $500 $ 500500 无
3∼43\sim 4 20002000 50005000 n=1n=1
5∼65\sim 6 20002000 50005000 k=2k=2
7∼107\sim 10 20002000 50005000 无

题解

原题：zzq 2019 省冬讲课的 ppt 的第一题，原题未知。

对于每个房间，我们随便选其中的一个点为代表点。

如果这个房间的代表点在这个矩形中，那么它一定在这个矩形中；否则如果一个房间在这个矩形中，那么它一定穿过了矩形的边界，枚举一下边界即可。

时间复杂度为 O(nm+q(n+m+k))O(nm+q(n+m+k))，空间复杂度为 O(nm+k)O(nm+k)。

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
#include <bits/stdc++.h>
#define il inline
const int N=2005;

namespace IO
{
    const int S=1<<20|500; char I[S+5],*s,*t,O[S+5],*o; int p[40],P;
    il char Gc(){if (t==s){t=(s=I)+fread(I,1,1<<20,stdin); if (t==s) return EOF;} return *s++;}
    template<class T> il void Read(T &x)
    {
        char c; while ((c=Gc())<48||c>57); x=c^48;
        while ((c=Gc())>47&&c<58) x=(x<<3)+(x<<1)+(c^48);
    }
    il void Fs(){if (o-O) fwrite(O,1,o-O,stdout); o=O;} il void Pc(char c){*o++=c; if (o-O==S) Fs();} struct F{F(){o=O;} ~F(){Fs();}}FF;
    template<class T=int> il void Print(T x){T y; do y=x/10,p[P++]=x-y*10; while (x=y); while (P) Pc(p[--P]^48);}
}
using IO::Read; using IO::Print; using IO::Pc;

int n,m,k,q,ans,s[N][N],X[N],Y[N]; bool o[N];

int main()
{
    freopen("hideseek.in","r",stdin),freopen("hideseek.out","w",stdout);
    
    Read(n),Read(m),Read(k),Read(q); int i,j,a,b,c,d;
    for (i=1; i<=n; i++) for (j=1; j<=m; j++) Read(a),X[s[i][j]=a]=i,Y[a]=j;
    
    while (q--)
    {
        Read(a),Read(b),Read(c),Read(d),memset(o,0,k+1),ans=0;
        for (i=1; i<=k; i++) if (X[i]>=a&&X[i]<=c&&Y[i]>=b&&Y[i]<=d) ans++,o[i]=1;
        for (i=a; i<=c; i++) !o[s[i][b]]&&(ans++,o[s[i][b]]=1),!o[s[i][d]]&&(ans++,o[s[i][d]]=1);
        for (j=b; j<=d; j++) !o[s[a][j]]&&(ans++,o[s[a][j]]=1),!o[s[c][j]]&&(ans++,o[s[c][j]]=1);
        Print(ans),Pc('\n');
    }

    return 0;
}

T3 摸鱼游戏 (fishing)

题面

题目描述

花生自闭了，于是开始摸🐟。

花生从🐟那里借到了 nn 缸🐟，第 ii 个🐟缸中有 aia_i 条🐟。

但是花生认为这些🐟缸不够优美，因为它们没有体现出🐮的『中庸』思想。具体而言，如果对于每个🐟缸，其中🐟的数量都不比其他🐟缸的多，也不少，就称这些🐟缸体现出🐮的『中庸』思想，即它们是优美的。

为了让🐟缸优美，花生要搞一些「骚操作」。在第 ii 次「骚操作」中，花生可以选出第 aia_i 和第 bib_i 个🐟缸，让其中的🐟进行「躺平繁殖」，若「躺平繁殖」前两缸中分别有 xx 条和 yy 条🐟，则「躺平繁殖」后可以得到 2(x+y)2(x+y) 条🐟，花生会把这些🐟平分到两个🐟缸中。

但是「骚操作」的执行很花费时间，所以花生想在 ll 次「骚操作」内让这些🐟缸变得优美。现在他找到你，想让你帮忙给出一个方案。

花生可能会摸好几次🐟，所以有多组数据。

输入格式

从 fishing.in 中读入数据。

第一行输入一个整数 TT，表示数据组数。

对于每组数据，先输入一行两个整数 l,nl,n，表示「骚操作」次数的限制和🐟缸的数量。

接下来一行 nn 个整数 p1,p2,⋯ ,pnp_1,p_2,\cdots,p_n，第 ii 个整数表示每个🐟缸中🐟的数量。

输出格式

输出答案到 fishing.out 中。

对于每组数据，先输出一行一个整数 m(0≤m≤l)m(0\le m\le l)，表示「骚操作」的数量。

接下来 mm 行，第 ii 行有两个整数 ai,bi(1≤ai,bi≤n,ai≠bi)a_i,b_i(1\le a_i,b_i\le n,a_i\ne b_i)，用一个空格隔开，表示第 ii 次「骚操作」是对第 aia_i 和 bib_i 个🐟缸执行的。

注意：如果选手未按照标准格式输出（忽略行末空格和文末换行），或者输出的量未在其该在的范围内，则会被判为格式错误。

样例

样例输入 1

1
2
3
4
5
6
7
3
1 2
1 2
4 4
1 90 8 3
1 6
2 2 2 2 1 1

样例输出 1

1
2
3
4
5
6
7
8
9
1
1 2
4
1 2
3 4
1 3
2 4
1
5 6

样例 2

见附件文件下的 fishing/fishing2.in 与 fishing/fishing2.ans。
注意 fishing2.ans 是空的，只是为了方便选手使用 checker。

样例 2

见附加文件下 hideseek/hideseek2.in 和 hideseek/hideseek2.ans。

数据范围

对于 100%100\% 的数据，1≤T≤1001\le T\le 100，1≤n≤10001\le n\le 1000，且 nn 为偶数，1≤l≤120001\le l\le 12000，1≤ai≤1091\le a_i\le 10^9，保证有解。

测试点编号 T≤T\le n≤n\le l∈l\in
11 1010 22 {1}\{1\}
22 1010 44 {4}\{4\}
3∼73\sim 7 100100 66 {16}\{16\}
8∼98\sim 9 11 100100 [5000,12000][5000,12000]
10∼1210\sim 12 100100 100100 [5000,12000][5000,12000]
13∼1513\sim 15 11 10001000 [11800,12000][11800,12000]
16∼2016\sim 20 100100 10001000 [11800,12000][11800,12000]

如何测试你的输出

附加文件下有一个可执行文件 fishing/checker 供选手调试。

打开终端，进入可执行文件 checker 所在目录下，并输入：

1
./checker <input_file> <output_file> <ans_file>

其中 <input_file>、<output_file>、<ans_file> 分别为输入文件、输出文件、答案文件。若选手需要测试第一个样例的输出，假设输出文件名叫 fishing1.out，则在终端输入：

1
./checker fishing1.in fishing1.out fishing1.ans

其将会返回如下的若干种信息：

  • Accepted：答案正确。
  • Wrong Answer：答案错误。
  • Wrong Format：格式错误。
  • Exceed The Limit：「骚操作」次数超过了限制。

每种错误信息后，都将伴随其更具体的解释，这里不再赘述。

其他

如果选手在 Windows 环境下编程，建议使用二进制文件输出，以避免在 Windows 下 \n 变成了 \r\n 而导致 checker 报错。freopen 的各参数可设置如下：

1
freopen(output_file,"wb",stdout);

当然你也可以使用 fin fout 等文件输入输出方式。

题解

原题：20212021 年空中楼阁杯第一场二试第四题。

显然和 aia_i 具体是多少没什么关系。

22 和 44 是简单的，关键是 66 的构造。

给出 66 的构造，感觉除了多手玩没有什么方法。

aabbbb4a4ab3b3b2b4a+3b4ab4a+3b3b2b4a+3b4ab4a+5b3b4a+5b4a+3b4a+3bb4a+5b4a+3b4a+5b4a+4b4a+3b4a+4b4a+5b4a+3b4a+5b8a+8b8a+8b8a+8b8a+8b8a+8b8a+8b\begin{matrix} a&a&b&b&b&b\\ 4a&4a&b&3b&3b&2b\\ 4a+3b&4a&b&4a+3b&3b&2b\\ 4a+3b&4a&b&4a+5b&3b&4a+5b\\ 4a+3b&4a+3b&b&4a+5b&4a+3b&4a+5b\\ 4a+4b&4a+3b&4a+4b&4a+5b&4a+3b&4a+5b\\ 8a+8b&8a+8b&8a+8b&8a+8b&8a+8b&8a+8b \end{matrix}

有了 66 的构造后，我们对于 n=4kn=4k，分成两个 2k2k 即可；对于 n=4k+2n=4k+2，变成前 2k2k 个 aa 后 2k+22k+2 个 bb，前后 2k−22k-2个 aa 和 bb 全部变成 8a+8b8a+8b，剩下六个也变成 8a+8b8a+8b，然后就做完了。

对于 n=6n=6 你还可以构造出全部变成 3a+2b3a+2b 的步数更少的方案，但是对正解没有什么帮助。

时间复杂度为 O(Tnlog⁡n)O(Tn\log{n})，空间复杂度为 O(l)O(l)，因为 SPJ 要写高精度，所以 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
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
#define il inline
const int N=12005;

int tt,n,m,A[N],B[N];

il void Sol(int l,int r,int o)
{
    if (r-l<2){A[++m]=l,B[m]=r; return;} int i,L=r-l+1>>1;
    if (r-l<4){Sol(l,l+1,0),Sol(r-1,r,0),A[++m]=l,B[m]=r,A[++m]=l+1,B[m]=r-1; return;}
    if (r-l<6)
    {
        if (!o) Sol(l,l+1,0),Sol(l+2,r,0);
        A[++m]=r,B[m]=r-1,A[++m]=r-2,B[m]=r-1,A[++m]=l,B[m]=l+1,A[++m]=l,B[m]=l+1,A[++m]=l,B[m]=l+3,A[++m]=r,B[m]=r-2,
        A[++m]=l+1,B[m]=r-1,A[++m]=l,B[m]=l+2,A[++m]=l,B[m]=l+2,A[++m]=l+1,B[m]=l+3,A[++m]=r,B[m]=r-1; return;
    }
    if (L&1^1){for (Sol(l,l+L-1,0),Sol(l+L,r,0),i=l; i<l+L; i++) A[++m]=i,B[m]=i+L;}
    else{for (Sol(l,l+L-2,0),Sol(l+L-1,r,0),Sol(l+L-3,l+L+2,1),i=l; i<l+L-3; i++) A[m+1]=A[m+2]=A[m+3]=A[m+4]=i,B[m+1]=B[m+2]=B[m+3]=B[m+4]=r-i+l,m+=4;}
}

int main()
{
    freopen("fishing.in","r",stdin),freopen("fishing.out","w",stdout);

    scanf("%d",&tt); int i;
    while (tt--)
    {
        for (scanf("%*d%d",&n),i=1; i<=n; i++) scanf("%*d");
        for (m=0,Sol(1,n,0),printf("%d\n",m),i=1; i<=m; i++) printf("%d %d\n",A[i],B[i]);
    }

    return 0;
}

T4 人文奇观 (wonders)

题面

题目描述

XieRujian 在玩 Vx Limo’s Civilization XVI\text{Vx Limo's Civilization XVI}。

XieRujian 再一次挑战格鲁吉亚，这次他开局就进了黄金时代，发展不断向好。现在格鲁吉亚的领土囊括了 nn 个单元格，编号为 11 到 nn。境内还有 mm 条道路，每条道路连接了两个不同的单元格。保证任意两个单元格可以通过若干条条道路互相到达。

既然选择了修城墙加旅游业绩的城墙姐塔玛丽，XieRujian 理所当然选择走文化胜利道路。现在 XieRujian 想在境内营建若干个奇观，他草拟了 100100 种建造计划，对于第 ii 个单元格，恰有 pip_i 种计划选择在这里建造奇观。

如果有若干个建有奇观的单元格通过道路相连，便会有额外的加成。我们称一些有奇观的单元格的集合为「旅游胜地」，当且仅当对于任意属于该集合的两个单元格 U,VU,V，从 UU 出发，可以通过走若干条所连接单元格均有奇观的道路到达 VV；且对于任意属于该集合的单元格 UU 和不属于该集合的单元格 VV，从 UU 出发，没法通过走若干条所连接单元格均有奇观的道路到达 VV。

游戏中还给出一个名为「奇观指数」的常数 kk，玩家获得的「奇观加成」便是所有「旅游胜地」的单元格数量的 kk 次方和。

由于每天都在赶 ddl，XieRujian 已经掌握了边划水边想题的技能。他现在在思考，如果把在第 ii 个单元格上修建奇观的概率，设为之前草拟的 100100 种计划中，有选择在此单元格建造奇观的计划的占比，即设为 pi%p_i\%，那么最后获得的「奇观加成」的期望是多少。

聪明的 XieRujian 很快就解决了这个问题，并把这道题出给了作为福建师范大学附属中学一员的你。

输入格式

从 wonders.in 中读入数据。

第一行三个整数 n,m,kn,m,k，表示单元格的数量，道路的数量与「奇观指数」。

接下来一行 nn 个整数，第 ii 个整数是 pip_i，表示在第 ii 个单元格上修建奇观的概率为 pi%p_i\%。

接下来 mm 行，第 ii 行两个整数 ui,viu_i,v_i，表示第 ii 条道路连接编号为 uiu_i 和 viv_i 的单元格。

输出格式

输出答案到 wonders.out 中。

一行一个整数，表示 XieRujian 获得的「奇观加成」的期望对 998244353998244353 取模的结果。

样例

样例输入 1

1
2
3
4
5
6
5 4 3
50 50 50 50 50
1 2
2 3
2 4
2 5

样例输出 1

1
19

样例输入 2

1
2
3
4
5
6
7
6 5 2
20 30 40 50 60 70
1 2
2 3
2 4
2 5
4 6

样例输出 2

1
397301258

样例输入 3

1
2
3
4
5
6
7
8
9
10
11
12
10 10 2
39 76 71 86 36 38 36 44 63 37 
4 5
2 10
6 10
1 8
5 10
8 10
7 10
3 10
10 9
5 3

样例输出 3

1
361859252

样例 4

见附件文件下的 wonders/wonders4.in 与 wonders/wonders4.ans。

样例 5

见附件文件下的 wonders/wonders5.in 与 wonders/wonders5.ans。

数据范围

对于 100%100\% 的数据，1≤n≤2×1051\le n\le 2\times 10^5，m=n−1m=n-1 或 m=nm=n，1≤k≤51\le k\le 5，0≤pi≤1000\le p_i\le 100，1≤ui,vi≤n1\le u_i,v_i\le n，ui≠viu_i\ne v_i，保证没有重复的道路。

数据点编号 n≤n\le m=m= k≤k\le 特殊性质 数据点编号 n≤n\le m=m= k≤k\le 特殊性质
11 1616 n−1n-1 55 无 1313 1616 nn 55 无
2∼32\sim 3 10001000 n−1n-1 55 无 14∼1714\sim 17 10001000 nn 55 无
4∼54\sim 5 2×1052\times 10^5 n−1n-1 11 无 1818 2×1052\times 10^5 nn 11 无
6∼76\sim 7 2×1052\times 10^5 n−1n-1 55 A⁡\operatorname{A} 1919 2×1052\times 10^5 nn 55 A⁡\operatorname{A}
8∼98\sim 9 2×1052\times 10^5 n−1n-1 55 B⁡\operatorname{B} 2020 2×1052\times 10^5 nn 55 B⁡\operatorname{B}
10∼1210\sim 12 2×1052\times 10^5 n−1n-1 55 无 21∼2521\sim 25 2×1052\times 10^5 nn 55 无

特殊性质 A⁡\operatorname{A}：对于任意的 1≤i<n1\le i<n，第 ii 条边连接的是编号为 ii 和 i+1i+1 的单元格。
特殊性质 B⁡\operatorname{B}：对于任意的 1≤i<n1\le i<n，第 ii 条边连接的是编号为 11 和 i+1i+1 的单元格。

题解

原题：https://www.luogu.com.cn/problem/P5575

考虑是一条链怎么做，比较显然：我们设 fi,jf_{i,j} 表示考虑到第 ii 个，点 ii 所在连通块的大小的 jj 次方的期望；再设 gig_i 表示考虑到第 ii 个，前面的连通块的大小的 kk 次方的和的期望。

那么有：

fi,j=E((x+1)j)gi=gi−1+(1−ai)fi−1,kf_{i,j}=E\left((x+1)^j\right)\\ g_i=g_{i-1}+(1-a_i)f_{i-1,k}

ff 用二项式定理展开：

fi,j=E((x+1)j)=E(∑p=0j(jp)xp)=∑p=0j(jp)fi−1,p\begin{aligned} f_{i,j}&=E\left((x+1)^j\right)\\ &=E\left(\sum_{p=0}^{j}{\dbinom{j}{p}x^p}\right)\\ &=\sum_{p=0}^{j}{\dbinom{j}{p}f_{i-1,p}} \end{aligned}

这样我们就可以在 O(nk2)O(nk^2) 的时间复杂度内，O(nk)O(nk) 的空间复杂度内解决这个问题。

放到了树上也基本是相同的，只是把 E((x+1)j)E\left((x+1)^j\right) 换成 E((x+y)j)E\left((x+y)^j\right)。

如果是基环树，我们先把环找出来，环下挂的树 DP 出来，这样就变成了环上的问题。

我们钦定一个点不建奇观，这样相当于强制断开一条边，变成了链上的问题。最后全建奇观的概率再额外算一下即可，这样我们就有了一个时间复杂度为 O(n2k2)O(n^2k^2) 的做法。

考虑慢的原因，因为每次断边我们都要重新 DP。考虑断边后变成了什么，相当于 11..110u...v，即在 u...v 后面接上 1...1。

直观想法是预处理出后缀的 ff，再单独计算 1...1 的贡献，然后把两个拼在一起，但是这样处理 ff 的结束点是 u，没有办法直接拼上去。

观察到 DP 的式子都是线性贡献的,也就是说:

设 u...v 左边跟了 ....?，对于 ....? 我们把 f?,0∼kf_{?,0\sim k} 设为 x0∼kx_{0\sim k}，则有：

fv,j=∑p=0jcixif_{v,j}=\sum_{p=0}^{j}{c_ix_i}

其中 cc 是一些常数，不难得出这些常数是由 u...v 具体控制的。

所以我们在不知道 ....? 的情况下，计算出 cc，然后任意给定一些东西接在 u...v 前面，都可以快速算出 DP 值，也就解决了不能从前面接上去的问题。

这上面的式子其实就是把 fi,jf_{i,j} 表示成了向量形式，于是我们把上面的加法换成向量加，乘法换成向量数乘，这样就可以正序预处理出 1...1 的贡献，在逆序算出 u...v 的贡献，在拼在一起即可。

时间复杂度均为 O(nk3)O(nk^3)，空间复杂度为 O(nk2)O(nk^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
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define il inline
#define ll long long
#define pb push_back
const int N=2e5+5,P=998244353;

int n,m,e,k,l,tot,ans,a[N],b[N],C[6][6],f[N][6],g[N],h[N][6][6],s[N][6],fa[N],d[N]; std::vector<int> G[N]; bool o[N];

il void Dfs(int u,int p)
{
    f[u][0]=1; int i,j,x;
    for (int v:G[u]) if (v!=p&&!o[v])
    {
        Dfs(v,u),g[u]=(g[u]+g[v]+(ll)(1-a[u]+P)*f[v][k])%P;
        for (i=k; i; f[u][i--]=x) for (x=j=0; j<=i; j++) x=(x+(ll)C[i][j]*f[u][j]%P*f[v][i-j])%P;
    }
    if (u!=e){for (i=k; i; f[u][i]=(ll)x*a[u]%P,i--) for (x=j=0; j<=i; j++) x=(x+(ll)C[i][j]*f[u][j])%P;}
}

il void Find(int u,int p)
{
    d[u]=++tot,fa[u]=p; int x;
    for (int v:G[u])
        if (!d[v]) Find(v,u);
        else if (v!=p&&d[v]<d[u]){for (x=u; ; x=fa[x]) if (o[b[++l]=x]=1,x==v) break;}
}

int main()
{
    freopen("wonders.in","r",stdin),freopen("wonders.out","w",stdout);

    scanf("%d%d%d",&n,&m,&k); int i,j,u,x,y[6],c;
    for (i=1; i<=n; i++) scanf("%d",a+i),a[i]=828542813ll*a[i]%P;
    for (x=1; x<=m; x++) scanf("%d%d",&i,&j),G[i].pb(j),G[j].pb(i);
    for (C[0][0]=i=1; i<=k; i++) for (C[i][0]=j=1; j<=i; j++) C[i][j]=C[i-1][j]+C[i-1][j-1];

    if (m<n) return Dfs(1,0),printf("%d\n",(f[1][k]+g[1])%P),0;
    for (Find(1,0),u=1; u<=l; u++) Dfs(e=b[u],0),ans=(ans+g[e])%P;
    for (i=0; i<=k; i++) h[0][i][i]=1;
    for (u=1; u<=l; u++)
    {
        for (h[u][0][0]=1,x=0; x<=k; x++) s[u][x]=(s[u-1][x]+(ll)h[u-1][k][x]*(1-a[b[u]]+P))%P;
        for (i=k; i; memcpy(h[u][i--],y,24)) for (memset(y,0,24),j=0; j<=i; j++)
            for (x=0; x<=k; x++) y[x]=(y[x]+(ll)C[i][j]*f[b[u]][j]%P*h[u-1][i-j][x])%P;
        for (i=k; i; memcpy(h[u][i--],y,24)) for (memset(y,0,24),j=0; j<=i; j++)
            for (x=0; x<=k; x++) y[x]=(y[x]+(ll)h[u][j][x]*C[i][j])%P;
        for (i=1; i<=k; i++) for (x=0; x<=k; x++) h[u][i][x]=(ll)h[u][i][x]*a[b[u]]%P;
    }
    for (u=0; u<=l; u++) for (x=0; x<=k; x++) s[u][x]=(s[u][x]+h[u][k][x])%P;
    for (memset(y,0,24),c=y[0]=1,u=l; u; u--)
    {
        for (x=i=0; i<=k; i++) x=(x+(ll)y[i]*s[u-1][i])%P;
        ans=(ans+(ll)c*(1-a[b[u]]+P)%P*x)%P,c=(ll)c*a[b[u]]%P;
        for (i=k; i; y[i--]=x) for (x=j=0; j<=i; j++) x=(x+(ll)y[i-j]*C[i][j]%P*f[b[u]][j])%P;  
        for (i=k; i; y[i--]=x) for (x=j=0; j<=i; j++) x=(x+(ll)y[j]*C[i][j])%P;
    }
    printf("%d\n",(ans+(ll)y[k]*c)%P);

    return 0;
}