| Solved | A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|---|
| 10/11 | Ø | 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 Enju With math problem
题目描述
给定一个数列，问是不是欧拉函数前$1.5e8$项中的子列。
解题思路
考虑内存和时间限制，对质数$31$的倍数三元组打表进行$check$。
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
using namespace std;
const int maxn = (int)1.5e8+2;
const int N = 5e6;
const int B = 31 ;
int phi[N],prime[1000000],cnt,ans,n,tot,a[500][103],t,p;
bool mark[N];
struct Triple
{
int x,y,z;
Triple (int x=0,int y=0,int z=0): x(x),y(y),z(z) {}
bool operator < (const Triple &b) const
{
if(x!=b.x) return x<b.x;
if(y!=b.y) return y<b.y;
return z<b.z;
//return x<b.x||y<b.y||z<b.z;
}
bool operator == (const Triple &b) const
{
return x==b.x&&y==b.y&&z==b.z;
}
};
struct Triple_hash
{
std::size_t operator() (const Triple &p) const
{
int h1=std::hash<int>{}(p.x);
int h2=std::hash<int>{}(p.y);
int h3=std::hash<int>{}(p.z);
return h1^h2^h3;
}
};
unordered_map<Triple,int,Triple_hash> m;
int T;
void getphi()
{
int maxn = N ;
phi[1]=1;cnt=0;
for(int i=2;i<maxn;i++){
if(!mark[i]){
prime[cnt++]=i;
phi[i]=i-1;
}
for(int j=0;j<cnt;j++){
if(1LL*i*prime[j]>=maxn) break;
mark[i*prime[j]]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
int calphi(int n)
{
int m=sqrt(n+0.5);
int ans=n;
for(int i=2;i<=m;i++){
if(n%i==0){
ans=ans/i*(i-1);
while(n%i==0) n/=i;
}
}
if(n>1) ans=ans/n*(n-1);
return ans;
}
int main()
{
getphi();
int x,y,z;
scanf("%d",&T);n=100;
for(int i=0;i<T;i++){
for(int j=0;j<n;j++) scanf("%d",&a[i][j]);
}
for(int i=0;i<T;i++){
for(int j=0;j+(B<<1)<n;j++){
m[Triple(a[i][j],a[i][j+B],a[i][j+(B<<1)])]=0;
}
}
x=phi[31],y=phi[62],z=phi[93];
for(int i=4,j=93;j<=maxn;i++,j+=B){
//if(j<1000) printf("%d %d\n",phi[j],z);
if(m.find(Triple(x,y,z))!=m.end()) m[Triple(x,y,z)]=j-(B<<1);
x=y,y=z;
if(i%B==0) z=B*phi[i];
else z=(B-1)*phi[i];
}
for(int k=0;k<T;k++){
bool flag=false;
for(int i=0;i<B;i++){
t=m[Triple(a[k][i],a[k][i+B],a[k][i+(B<<1)])]-i;
if(t>=1){
for(int j=0;j<100;j++){
if(a[k][j]!=calphi(j+t)) goto A;
}
flag=true;
}
A:;
if(flag) {printf("YES\n%d\n",t);break;}
}
if(!flag) printf("NO\n");
}
}
B Fire-Fighting Hero
题目描述
有一个消防英雄和一些消防队，消防英雄速度为$c$，消防队每个人速度都为$1$。
有一张无向图，所有人初始时都在其特定位置，问消防队厉害还是消防英雄厉害，厉害的标准是到所有点最短路的最大值最小。
解题思路
跑多次$dijkstra$比较一下即可。
AC代码 - by Mogg
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
using namespace std;
typedef long long ll;
const int ms = 1010;
const int mx = 1000;
int g[ms][ms], point[ms], d[ms],d1[ms];
vector<int> gr[ms];
int n, m, cnt;
priority_queue<pair<int, int>>q;
bool vis[ms];
void dij(int begin)
{
memset(d, 0x3f, sizeof(d));
memset(vis, false, sizeof(vis));
q.push({ 0,begin }); d[begin] = 0;
while (!q.empty())
{
int x = q.top().second; q.pop();
if (vis[x]) continue;
vis[x] = true;
for (int i : gr[x])
{
int y = i, z = g[x][i];
if (d[y] > d[x] + z)
{
d[y] = d[x] + z;
q.push({ -d[y],y });
}
}
}
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int s, k, c;
scanf("%d%d%d%d%d", &n, &m, &s, &k, &c);
for (int i = 0; i < k; ++i)
{
scanf("%d", &point[i]);
}
memset(g, 0x3f, sizeof(g));
memset(d1, 0x3f, sizeof(d1));
int x, y, z;
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &x, &y, &z);
if (g[x][y] == 0x3f3f3f3f)
{
gr[x].push_back(y);
gr[y].push_back(x);
}
g[x][y] = min(g[x][y], z);
g[y][x] = min(g[y][x], z);
}
dij(s); int t1 = *max_element(d + 1, d + n + 1); int res = 0, t2 = 0;
for (int i = 0; i < k; ++i)
{
dij(point[i]);
for (int j = 1; j <= n; ++j)
{
d1[j] = min(d1[j], d[j]);
}
}
t2 = max(t2, *max_element(d1 + 1, d1 + n + 1));
if (1ll*t2*c >= 1ll * t1) res = t1;
else res = t2;
printf("%d\n", res);
for (int i = 0; i < n; ++i)
{
gr[i].clear();
}
}
return 0;
}
C Hello 2019
题目描述
一个字符串称为好串，当且仅当它包含$9102$而不包含$8102$，多次询问一个串$S$中$[l,r]$区间中最少删除多少个元素才能形成一个好串。
解题思路
考虑将字符串倒置，问题转化成在区间中找包含$2019$的串而不包含$2018$的串。
建立一个有限状态自动机，设当前构成的串具有$2019$前缀长度为$l_1$的子串转化成长度为$l_2$的子串需要至少删掉$f[l_1][l_2]$个元素，则当当前元素为$2,0,1,9$其中某一个时，有$f[pos][pos]=1$（保持前缀长度不变需要删掉这个元素，比如当前为$2$，那么有$f[0][0]=1$，即前缀长度为$0$的保持为$0$必然需要删掉当前元素，否则前缀长度会变成$1$），$f[pos][pos+1]=0$（用这个元素将前缀加一）；当当前元素为$8$时，有$f[4][4]=1,f[3][3]=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
typedef long long ll;
using namespace std;
struct node{
int a[5][5];
void init(){
memset(a,0x3f,sizeof(a));
int i;
for(i=0;i<5;i++)a[i][i]=0;
}
};
node emp;
node tr[N<<2];
int L[N<<2],R[N<<2];
char a[N];
node merge(node a,node b){
int i,j,k;
node temp;
memset(temp.a,0x3f,sizeof(temp.a));
for(i=0;i<5;i++)
for(j=i;j<5;j++)
for(k=i;k<=j;k++)
temp.a[i][j]=min(temp.a[i][j],a.a[i][k]+b.a[k][j]);
return temp;
}
int id[257];
void build(int p,int l,int r){
L[p]=l;R[p]=r;
if(l==r){
tr[p].init();
if(a[l]=='2'||a[l]=='0'||a[l]=='1'||a[l]=='9'){
tr[p].a[id[a[l]]][id[a[l]]]=1;
tr[p].a[id[a[l]]][id[a[l]]+1]=0;
}else if(a[l]=='8'){
int i;
tr[p].a[4][4]=tr[p].a[3][3]=1;
}
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}
node query(int p,int l,int r){
if(L[p]>r||R[p]<l)return emp;
if(L[p]>=l&&R[p]<=r)return tr[p];
return merge(query(p<<1,l,r),query(p<<1|1,l,r));
}
int main(){
int n,q;
id['2']=0;id['0']=1;id['1']=2;id['9']=3;
emp.init();
scanf("%d%d",&n,&q);
scanf("%s",a);
reverse(a,a+n+1);
build(1,1,n);
while(q--){
int l,r;
scanf("%d%d",&l,&r);
node ans=query(1,n-r+1,n-l+1);
if(ans.a[0][4]<1e9)printf("%d\n",ans.a[0][4]);
else printf("-1\n");
}
return 0;
}
D Interesting Series
题目描述
定义函数$F_i=aF_{i-1}+1,F_1=1$，并定义一个集合$s$的$value$为其中所有元素和的$F$（即$value(s)=F_{sum_s}$）。
给定$S,K$，求$\sum_{s\in subsets\space of\space S\space and\space |s|=K}value(s)$。
解题思路
化简$F$，$F_i=\frac{a^i-1}{a-1}$。只考虑与$i$有关的东西，即求$g_i=a^i$。
于是有生成函数$(x+a^{S_1})(x+a^{S_2})\cdot …\cdot (x+a^{S_n})$，答案即为这个多项式$x^{n-k}$的系数。
对生成函数分治$FFT$，剩余部分组合数学。
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
typedef long long ll;
using namespace std;
struct comp{
double x,y;
comp():x(0),y(0){}
comp(const double &_x,const double &_y):x(_x),y(_y){}
};
comp operator+(const comp &a,const comp &b){return comp(a.x+b.x,a.y+b.y);}
comp operator-(const comp &a,const comp &b){return comp(a.x-b.x,a.y-b.y);}
comp operator*(const comp &a,const comp &b){return comp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
comp conj(const comp &a){return comp(a.x,-a.y);}
double PI=acos(-1);
comp w[M+5];
int rev[M+5];
int A[M+5],B[M+5],C[M+5],lim,mx,mod=100003;
void fft(comp *a,int n){
int i,j,k,lyc;
for(i=0;i<n;i++)if(i<rev[i]) swap(a[i],a[rev[i]]);
for(i=2,lyc=n>>1;i<=n;i<<=1,lyc>>=1)
for(j=0;j<n;j+=i){
comp *l=a+j,*r=a+j+(i>>1),*p=w;
for(k=0;k<(i>>1);k++){
comp tmp=*r**p;
*r=*l-tmp,*l=*l+tmp;
++l,++r,p+=lyc;
}
}
}
void fft_prepare(){
int i;
for(i=0;i<lim;i++)rev[i]=rev[i>>1]>>1|((i&1)<<(mx-1));
for(i=0;i<lim;i++)w[i]=comp(cos(2*PI*i/lim),sin(2*PI*i/lim));
}
comp a[M+5],b[M+5],ta[M+5],tb[M+5];
void conv(int *x,int *y,int *z){
int i,j;
for(i=0;i<lim;i++)(x[i]+=mod)%=mod,(y[i]+=mod)%=mod;
for(i=0;i<lim;i++){
ta[i]=comp(x[i]&32767,x[i]>>15);
tb[i]=comp(y[i]&32767,y[i]>>15);
}
fft(ta,lim);fft(tb,lim);
for(i=0;i<lim;i++){
j=(lim-i)%lim;//0的特判
comp da,db,dc,dd;
da=(ta[i]+conj(ta[j]))*comp(0.5,0);
db=(ta[i]-conj(ta[j]))*comp(0,-0.5);
dc=(tb[i]+conj(tb[j]))*comp(0.5,0);
dd=(tb[i]-conj(tb[j]))*comp(0,-0.5);
a[j]=da*dc+da*dd*comp(0,1);
b[j]=db*dc+db*dd*comp(0,1);
}
fft(a,lim);fft(b,lim);
for(i=0;i<lim;i++){
ll da,db,dc,dd;
da=(ll)(a[i].x/lim+0.5)%mod;
db=(ll)(a[i].y/lim+0.5)%mod;
dc=(ll)(b[i].x/lim+0.5)%mod;
dd=(ll)(b[i].y/lim+0.5)%mod;
z[i]=(da+((db+dc)<<15)+(dd<<30))%mod;
}
}
int qp(ll a,int p){
int ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
vector<int>G[M];
vector<int>conv(vector<int>a,vector<int>b,int n,int m){
static int x[M],y[M],z[M];
vector<int>tmp;tmp.clear();
int i;
mx=0;
while((1<<mx)<n+m)mx++;
lim=1<<mx;
for(i=0;i<n;i++)x[i]=a[i];for(;i<lim;i++)x[i]=0;
for(i=0;i<m;i++)y[i]=b[i];for(;i<lim;i++)y[i]=0;
fft_prepare();
conv(x,y,z);
for(i=0;i<n+m-1;i++)tmp.push_back(z[i]);
return tmp;
}
vector<int>dc(int l,int r){
if(l==r)return G[l];
vector<int>L=dc(l,mid);
vector<int>R=dc(mid+1,r);
vector<int>temp=conv(L,R,L.size(),R.size());
return temp;
}
int fac[M],inv[M];
int c(int n,int m){
if(n<m||m<0)return 0;
return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
int i,n,a,q,k;
fac[0]=inv[0]=1;
for(i=1;i<=M/2;i++)fac[i]=1LL*fac[i-1]*i%mod,inv[i]=qp(fac[i],mod-2);
scanf("%d%d%d",&n,&a,&q);
for(i=1;i<=n;i++){
int s;
scanf("%d",&s);
G[i].push_back(qp(a,s));
G[i].push_back(1);
}
vector<int>ans=dc(1,n);
while(q--){
scanf("%d",&k);
printf("%d\n",((1LL*ans[n-k]-c(n,k))*qp(a-1,mod-2)%mod+mod)%mod);
}
return 0;
}
E Magic Master
题目描述
根据题意移动卡牌，问最后得到的卡牌最初的位置。
解题思路
约瑟夫问题，倒推即可。
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
using namespace std;
int T,n,m,q,k;
const int maxn = 4e7+23;
int f[maxn];
int main()
{
cin >> T;
while(T--){
scanf("%d%d",&n,&m);m++;
scanf("%d",&q);
for(int i=0;i<q;i++){
scanf("%d",&k);
int now=n,v=k,step;
while(now>=1){
//printf("%d %d\n",now,v);
if((v-1)%m==0){
printf("%d\n",n-now+1+(v-1)/m);
goto A;
}
step=(v-1)/m+1;
now-=step,v=((v-step*m));
while(v<=0) v+=now;
}
A:;
}
}
}
F Megumi With String
题目描述
定义一个字符串$s$的价值$G(p)$为一个关于$p$的多项式，其中$p$为$s$的长度且$s$为$S$的子串。
给定$S$，$q$次操作，每次向$S$后插入一个新字符。随机生成一个字符串$T$，求$T$中所有子串的价值之和的期望。
解题思路
不同的子串在随机生成的字符串$T$中具有相等的概率出现，故问题很容易转化成：对于一个长度$l$的$S$中子串，有多少种方式生成$T$中包含这个子串。
建立一个$SAM$，对于每一个新添节点，通过$SAM$上节点与父节点之间的关系，求出每一个长度区间对答案的贡献，过程中求一个前缀和即可。
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
typedef long long ll;
using namespace std;
const int mod=998244353;
int fac[N],inv[N];
char s[N];
int a[52],f[52],n,m,k,l;
ll res,sum[N];
struct SAM{
int tr[N<<1][P],fa[N<<1],len[N<<1],siz[N<<1];
int cnt,last;
void init(){//dont forget!!!
cnt=last=1;
memset(tr[1],0,sizeof(tr[1]));
fa[1]=len[1]=0;
}
void add(int c){
int p=last,np=++cnt;
memset(tr[cnt],0,sizeof(tr[cnt]));
siz[np]=1;
last=np;
len[np]=len[p]+1;
while(p&&!tr[p][c])tr[p][c]=np,p=fa[p];
if(!p)fa[np]=1;
else{
int q=tr[p][c];
if(len[q]==len[p]+1)fa[np]=q;
else{
int nq=++cnt;len[nq]=len[p]+1;
memcpy(tr[nq],tr[q],sizeof(tr[q]));
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
while(tr[p][c]==q)tr[p][c]=nq,p=fa[p];
}
}
(res+=sum[min(n,len[last])]-sum[min(n,len[fa[last]])]+mod)%=mod;
}
void insert(char a[]){
int i;
for(i=0;a[i];i++)add(a[i]-'a');//can be changed
}
}sam;
ll 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 main(){
int i,j,T;
scanf("%d",&T);
while(T--){
res=0;
scanf("%d%d%d%d",&l,&k,&n,&m);
scanf("%s",s);
for(i=0;i<=k;i++)scanf("%d",&a[i]);
int mx=min(l+m,n);
ll pow26=26;
for(i=1;i<=mx;i++){
ll s=0,x=1;
for(j=0;j<=k;j++)(s+=a[j]*x)%=mod,x=x*i%mod;
s=s*qp(pow26,mod-2)%mod*(n-i+1)%mod;
pow26=pow26*26%mod;
sum[i]=(sum[i-1]+s)%mod;
}
sam.init();
sam.insert(s);
printf("%lld\n",res);
while(m--){
char t[10]={0};
scanf("%s",t);
sam.add(t[0]-'a');
printf("%lld\n",res);
}
}
return 0;
}
G Pangu Separates Heaven and Earth
题目描述
这道题目没有描述。
解题思路
强行签到…
AC代码 - by Mogg
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
using namespace std;
typedef long long ll;
const int ms = 50050;
int main()
{
int r, t, m;
scanf("%d", &t);
while (t--)
{
scanf("%d", &r);
if(r == 1)
{
printf("%d\n", 18000);
}
else
{
printf("%d\n", 0);
}
}
return 0;
}
H The Nth Item
题目描述
定义数列$f_n=3f_{n-1}+2f_{n-2},f_0=0,f_1=1$。有$n\leq 10^7$次询问，每次询问一个$n\leq 10^{18}$，求$f_n$。
解题思路
先求出来循环节（其实没必要），然后分两段打表，数较小的部分直接递推，数较大的部分矩阵快速幂求出一个后递推即可。
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
typedef long long ll;
using namespace std;
const int mod=998244353;
int f[N+2];
struct Mt{
int a[2][2];
}tmp[N];
Mt mul(Mt a,Mt b){
int i,j,k;
Mt t;
t.a[0][0]=(1LL*a.a[0][0]*b.a[0][0]+1LL*a.a[0][1]*b.a[1][0])%mod;
t.a[0][1]=(1LL*a.a[0][0]*b.a[0][1]+1LL*a.a[0][1]*b.a[1][1])%mod;
t.a[1][0]=(1LL*a.a[1][0]*b.a[0][0]+1LL*a.a[1][1]*b.a[1][0])%mod;
t.a[1][1]=(1LL*a.a[1][0]*b.a[0][1]+1LL*a.a[1][1]*b.a[1][1])%mod;
return t;
}
Mt qp(Mt a,int p){
Mt t;t.a[0][0]=t.a[1][1]=1;t.a[1][0]=t.a[0][1]=0;
for(;p;p>>=1,a=mul(a,a))if(p&1)t=mul(t,a);
return t;
}
int cir=499122176;
int main(){
int i;
Mt a;
a.a[0][0]=3;a.a[0][1]=2;a.a[1][0]=1;a.a[1][1]=0;
f[0]=0;f[1]=1;
for(i=2;i<=N;i++)f[i]=(f[i-2]*2LL+f[i-1]*3LL)%998244353;
int q;
ll n,ans=0;
ll res=0;
scanf("%d%lld",&q,&n);
tmp[0].a[0][0]=tmp[0].a[1][1]=1;tmp[0].a[1][0]=tmp[0].a[0][1]=0;
tmp[1]=qp(a,X);
for(i=1;i<X;i++)tmp[i]=mul(tmp[i-1],tmp[1]);
while(q--){
ll temp=n%cir;
int R=temp%X;
int DIV=temp/X;
Mt now=tmp[DIV];
ans=(1LL*now.a[1][0]*f[R+1]+1LL*now.a[1][1]*f[R])%mod;
n=n^(ans*ans);
res^=ans;
}
printf("%lld\n",res);
return 0;
}
I Yukino With Subinterval
题目描述
解题思路
AC代码
2