| A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
| $\color{red}{\texttt{+}}$ |
$\color{green}{-}$ |
$\color{gray}{\texttt{+}}$ |
$\color{red}{\texttt{+}}$ |
$\color{green}{-}$ |
|
$\color{green}{-}$ |
$\color{red}{\texttt{+}}$ |
$\color{green}{\texttt{+}}$ |
$\color{green}{\texttt{+}}$ |
$\color{green}{\texttt{-}}$ |
$\color{red}{\texttt{+}}$ |
$\color{green}{\texttt{+}}$ |
G. Rikka with Game Theory
K. Rikka with Composite Number
签到题。
I. Rikka with RCPC
显然 $1$ 操作不如取 $3$ 操作，且 $1$ 操作一定可以被替换成 $3$ 操作。这样题意变成：要求选若干段不相邻，长度 $\geq k$ 且区间和不超过 $T$ 的区间，将权值变成 $0$，问最小代价。直接线段树/树状数组维护后缀最小值即可。
复杂度 $O(n\log n)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=200010;
typedef long long ll;
const ll inf=1e18;
int a[N];ll s[N],t[N<<2];
void insert(int u,int l,int r,int p,ll v)
{
if(l==r){t[u]=v;return;}
int mid=(l+r)>>1;
if(p<=mid) insert(u<<1,l,mid,p,v);
else insert(u<<1|1,mid+1,r,p,v);
t[u]=min(t[u<<1],t[u<<1|1]);
}
ll qry(int u,int l,int r,int L,int R)
{
if(L<=l && r<=R) return t[u];
int mid=(l+r)>>1;ll v=inf;
if(L<=mid) v=min(v,qry(u<<1,l,mid,L,R));
if(R>mid) v=min(v,qry(u<<1|1,mid+1,r,L,R));
return v;
}
ll f[N];
int main()
{
memset(t,0x3f,sizeof(t));
int n,m,S;scanf("%d%d%d",&n,&m,&S);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
insert(1,0,n,0,0);
for(int i=1;i<=n;i++)
{
f[i]=f[i-1]+a[i];
int p=lower_bound(s,s+n+1,s[i]-S)-s;
if(p<i-m) f[i]=min(f[i],qry(1,0,n,p,i-m-1));
insert(1,0,n,i,f[i]);
}
ll ans=inf;
for(int i=n;i && s[n]-s[i]<=S;i--) ans=min(ans,f[i]);
printf("%lld\n",ans);
return 0;
}
|
J. Rikka with Book
子集 dp。用 $f_s$ 表示 $s$ 集合内的书要保持平衡情况下，最远端距离重心位置的最大值。
考虑加入一本书 $i$ 时，这本书会被垫在最下面。容易证明此时将上面 $s$ 集合的书的重心放在这本书的边缘上一定最优。此时新的重心可以算出来。
直接做过不了第二个样例。注意到最优策略有可能是：放一堆书压住一本书的左端，使得这本书的重心超出桌子，容易发现此时最优策略就是上面的情况下把所有数绕桌子边界对称一下，直接在两者中取较大值即可。
复杂度 $O(2^nn)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<iostream>
#include<cstdio>
#include<cstring>
#define db double
using namespace std;
const int N=20;
int a[N],w[N];db f[1<<N];
int main()
{
int n;scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<n;i++) scanf("%d",&w[i]);
for(int i=0;i<n;i++) f[1<<i]=a[i]/2.0;
for(int s=1;s<1<<n;s++)
{
int sm=0;
for(int i=0;i<n;i++) if(s>>i&1) sm+=w[i];
for(int i=0;i<n;i++) if(!(s>>i&1))
f[s^(1<<i)]=max(f[s^(1<<i)],max(f[s]+1.*w[i]/(sm+w[i])*(a[i]/2.0),a[i]-1.*w[i]/(sm+w[i])*(a[i]/2.0)));
}
printf("%.10lf\n",f[(1<<n)-1]);
return 0;
}
|
A. Rikka with Game
容易发现击杀的顺序是无所谓的。一条链的版本就是 matrix67 博客里大鱼吃小鱼的问题。
结论：如果存在一个最大匹配不包含 $i$，那么 $i$ 变成龙就不会死。如果 $i$ 一定在最大匹配中，那么会有一个人击杀 $i$ 然后结束。
考虑先证明如果最大匹配一定包含 $i$ 那么 $i$ 会死：如果 $(i,j)$ 是一组可行的最大匹配，那么 $j$ 一定会击杀 $i$（如果 $j$ 前面没人击杀），之后假设 $x$ 会击杀 $j$，那么 $x$ 一定也会被击杀（因为所有最大匹配都经过 $i$，故 $x$ 一定也在最大匹配中），所以 $x$ 为了存活不会击杀 $j$，$j$ 就会存活。
同理也可以证明，如果存在最大匹配不包含 $i$，如果 $j$ 击杀 $i$，一定会有他的匹配击杀它。所以 $i$ 一定可以存活。
用带花树计算出匹配。然后判断 $i$ 是否一定是最大匹配时，将 $i$ ban 掉，然后重新增广 $i$ 的匹配即可。复杂度仍然是 $O(n^3)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define N 1010
using namespace std;
vector<int>g[N];
bool ban[N];
namespace flower_tree{
queue<int>q;
int col[N],f[N];
int find(int x){return f[x]==x?f[x]:(f[x]=find(f[x]));}
int pre[N],lik[N],T,vis[N];
int lca(int x,int y)
{
for(x=find(x),y=find(y),++T;vis[x]!=T;)
{
vis[x]=T;
x=find(pre[lik[x]]);
if(y) swap(x,y);
}
return x;
}
void flower(int x,int y,int v)
{
for(;find(x)!=v;x=pre[y])
{
pre[x]=y;y=lik[x];
if(col[y]==2) col[y]=1,q.push(y);
if(f[x]==x) f[x]=v;if(f[y]==y) f[y]=v;
}
}
void clear(int n)
{
while(!q.empty()) q.pop();
for(int i=1;i<=n;i++) f[i]=i,pre[i]=col[i]=0;
}
bool dfs(int s,int n)
{
clear(n);
col[s]=1;q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
for(int v:g[u])
if(!ban[v] && find(u)!=find(v) && col[v]!=2)
{
if(col[v])
{
int w=lca(u,v);
flower(u,v,w);flower(v,u,w);
continue;
}
col[v]=2,pre[v]=u;
if(lik[v]) col[lik[v]]=1,q.push(lik[v]);
else
{
for(int x=v,y=lik[pre[x]];x;x=y,y=lik[pre[x]])
lik[x]=pre[x],lik[pre[x]]=x;
return true;
}
}
}
return false;
}
}
using flower_tree::lik;
char str[N];bool vis[N],ans[N];
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",str+1);
for(int j=i+1;j<=n;j++) if(str[j]=='0') g[i].push_back(j),g[j].push_back(i);
}
for(int i=1;i<=n;i++) if(!lik[i]) flower_tree::dfs(i,n);
for(int i=1;i<=n;i++) ans[i]=true;
for(int i=1;i<=n;i++) if(lik[i])
{
ban[i]=true,lik[lik[i]]=0;
if(!flower_tree::dfs(lik[i],n))
{
ans[i]=false;
lik[lik[i]]=i;
}
else lik[i]=0;
ban[i]=false;
}
for(int i=1;i<=n;i++) putchar('0'+ans[i]);
return 0;
}
|
B. Rikka with Maximum Segment Sum
全局子段和有一个经典做法：从左往右依次加入一个元素，如果 $<0$ 就变成 $0$。
考虑从左往右处理，维护从 $i$ 开始的最大子段和 $f_i$，相当于前缀加，对 $0$ 取 $\max$，前缀历史最大值之和。
直接做不好处理。但是可以发现 $f_i$ 是单调递减的。并且只要 $f_i$ 变成了 $0$，它之后一定等于 $f_{i+1}$。用单调栈维护所有断点，这样就不需要对 $0$ 取 $\max$ 的过程。直接用线段树维护即可。复杂度 $O(n\log n)$。
还有一个分治做法：考虑所有经过 mid 的区间，对于每个 $i\in[l,mid]$，我们求出 $[i,mid]$ 的最大子段和 $s_i$ 与后缀子段和 $f_i$，对于 $i\in(mid,r]$ 求出最大子段和与前缀子段和。那么区间 $[l,r]$ 的答案就是 $\max{s_l,s_r,f_l+f_r}$。
不妨假设 $s_l<s_r$，那么随着 $l$ 移动 $s_r$ 为最大值的 $r$ 是一个区间，$s_l>s_r$ 同理。用双指针维护区间端点，复杂度 $O(n\log n)$。
D. Rikka with New Year’s Party
用到的结论和 太阳神的宴会 一样，即对于每个字符找到它前一次出现位置，设它们的距离为 $f_i$。结论是如果将子串每个字符第一次出现的 $f_i$ 置为 $0$，那么两个子串经过变换后相同当且仅当这两个数组同构。
考虑将每个后缀对应字符串排序，容易发现每次求两个后缀的 lcp 可以转化成 $O(\Sigma)$ 次原 $f_i$ 两个后缀的 lcp。用后缀数组和 ST 表预处理 $f_i$ 两两后缀 lcp，时间复杂度 $O(n\log n\Sigma)$。
代码
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200010
using namespace std;
int f[N],nxt[N][27],tp[N],pre[27];char s[N];
namespace suffix_array{
int sa[N],ht[N],id[N],rk[N],b[N*2],a[N],n,f[N][20],l2[N];
void sort(int m)
{
for(int i=1;i<=m;i++) b[i]=0;for(int i=1;i<=n;i++) b[rk[i]]++;
for(int i=1;i<=m;i++) b[i]+=b[i-1];for(int i=n;i;i--) sa[b[rk[id[i]]]--]=id[i];
}
void make_sa(int m=26)
{
for(int i=1;i<=n;i++) rk[i]=a[i],id[i]=i;
sort(m);
for(int p=1,t=0;p<n;p<<=1,m=t,t=0)
{
for(int i=1;i<=p;i++) id[++t]=n-p+i;
for(int i=1;i<=n;i++) if(sa[i]>p) id[++t]=sa[i]-p;
sort(m),swap(rk,id),rk[sa[1]]=t=1;
for(int i=2;i<=n;i++) rk[sa[i]]=(t+=(id[sa[i]]!=id[sa[i-1]] || id[sa[i]+p]!=id[sa[i-1]+p]));
}
}
void get_ht(){for(int i=1,p=0;i<=n;ht[rk[i]]=p,i++) for(p-=!!p;i+p<=n && sa[rk[i]-1]+p<=n && a[sa[rk[i]-1]+p]==a[i+p];p++);}
void init_lcp()
{
l2[0]=-1;for(int i=1;i<=n;i++) f[i][0]=ht[i],l2[i]=l2[i>>1]+1;
for(int j=1;1<<j<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++) f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int lcp(int x,int y)
{
if(x==y) return n-x+1;x=rk[x],y=rk[y];if(x>y) swap(x,y);
x++;int p=l2[y-x+1];return min(f[x][p],f[y-(1<<p)+1][p]);
}
void build(){make_sa(n),get_ht(),init_lcp();}
void init(int a0[],int n0){n=n0;for(int i=1;i<=n;i++) a[i]=a0[i];build();}
void init(char s[],int n0){n=n0;for(int i=1;i<=n;i++) a[i]=s[i]-'a'+1;build();}
}
int n,id[N],g[N];
int lcp(int x,int y)
{
int p=0;
for(int i=0;i<min(tp[x],tp[y]);i++)
{
p+=suffix_array::lcp(x+p,y+p);
int px=nxt[x][i],py=nxt[y][i];
if(p<min(px,py)) return p;
if(px==py) p=px+1;else return min(px,py);
}
throw;
}
int main()
{
scanf("%d%s",&n,s+1);
f[n+1]=-1;for(int i=1;i<=n;i++) f[i]=i-pre[s[i]-'a'],pre[s[i]-'a']=i;
suffix_array::init(f,n);
for(int i=n;i;i--) memcpy(nxt[i],nxt[i+1],sizeof(nxt[i])),nxt[i][s[i]-'a']=i;
for(int i=1;i<=n;i++)
{
id[i]=i;static int tmp[27];
for(int j=0;j<26;j++) if(nxt[i][j]) tmp[tp[i]++]=nxt[i][j]-i;
tmp[tp[i]++]=n-i+2;sort(tmp,tmp+tp[i]);
for(int j=0;j<tp[i];j++) nxt[i][j]=tmp[j];
}
sort(id+1,id+n+1,[&](int x,int y){int p=lcp(x,y);return f[x+p]<f[y+p];});
long long ans=n-id[1]+1;
for(int i=2;i<=n;i++) ans+=(n-id[i]+1)-lcp(id[i-1],id[i]);
printf("%lld\n",ans);
return 0;
}
|
E. Rikka with Subsequence
分类讨论。容易发现如果 $x$ 是偶数直接除以 $2$，否则按 $s$ 末尾是不是若干 9 分类讨论，可以做到只有一个位置不同。
H. Rikka with Storehouse
经典套路，考虑令 $f_i(x)$ 表示当 $i$ 子树对应函数和为 $f’(x)$，父亲为 $x$ 时的最小代价，可以发现当前点权一定是二次函数最值，容易归纳证明其关于 $x$ 是一个二次函数。
由于树高只有 $O(n\log n)$，直接暴力更新函数值即可。复杂度 $O(n\log n\log \text{mod})$。
代码
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<iostream>
#include<cstdio>
#include<cstring>
#define N 1000000
using namespace std;
typedef long long ll;
const int mod=998244353,iv4=(mod*3ll+1)/4;
int ksm(int a,int b=mod-2)
{
int r=1;
for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) r=1ll*r*a%mod;
return r;
}
int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
struct node{
int a,b,c;
node(){a=b=c=0;}node(int x):a(1),b((mod*2-2*x)%mod),c(1ll*x*x%mod){}
node(int a,int b,int c):a(a),b(b),c(c){}
int calc(int x){return (1ll*a*x%mod*x+1ll*b*x+c)%mod;}
int min(){return calc(mod-1ll*b*ksm(2*a)%mod);}
}f[N];
node operator +(const node x,const node y){return node(add(x.a,y.a),add(x.b,y.b),add(x.c,y.c));}
void upd(int x)
{
auto v=f[x<<1]+f[x<<1|1];int a=v.a,b=v.b,c=v.c,iv=ksm(1+a);
f[x]=node(1ll*a*iv%mod,1ll*b*iv%mod,(1ll*a*c+c-1ll*b*b%mod*iv4%mod+mod)%mod*iv%mod);
}
int main()
{
int n,m;scanf("%d%d",&n,&m),n=(1<<n)-1;
for(int i=n/2+1,x;i<=n;i++) scanf("%d",&x),f[i]=x;
for(int i=n/2;i;i--) upd(i);
printf("%d\n",f[1].min());
for(int i=1;i<=m;i++)
{
int w,x;scanf("%d%d",&x,&w);
f[x]=w;
for(x/=2;x;x/=2) upd(x);
printf("%d\n",f[1].min());
}
return 0;
}
|
M. Rikka with Employees
考虑如果给定的是一个毛毛虫时怎么做。考虑找到主链，先让主链上的人放假，这样所有叶子都是互不干扰的。把所有叶子排成一个序列，先让右半边的人放假，递归左半边，然后召回右半边的人，让右半边的人放假，递归右半边。由于每个人只会在 $O(\log n)$ 次递归中被处理，所以总次数是 $O(n\log n)$ 的。最后对于主链从下往上推一边即可。
对于原图，将其树链剖分。对于每条重链，按照上面的做法把所有轻儿子找出列成一个序列。由于这里每个轻儿子大小不同，考虑按权分治，即先按大小排序，然后每次划成尽可能均匀的两部分。
似乎复杂度是 $O(n\log^2 n)$ 的，因为每个点向上会经过 $O(\log n)$ 条重链，每条重链会被处理 $O(\log n)$ 次。其实仔细分析会发现每次合并两个序列时，因为我们是排序后按权分治，所以两个序列极差不会超过两个序列中较小部分的和，所以每合并一次大小 $\times 1.5$，总复杂度是 $O(n\log n)$ 的。
将冗余操作（比如放完假立刻召回的情况）去掉，可以在限定步数内解决。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define N 100010
using namespace std;
int fa[N],siz[N],son[N];vector<int>g[N];
void dfs0(int u){siz[u]=1;for(int v:g[u]){dfs0(v),siz[u]+=siz[v];if(siz[son[u]]<siz[v]) son[u]=v;}}
pair<int,int>ton[N*80];int tp;
void add(int u){ton[++tp]={0,u};}
void dec(){if(ton[tp].first==0) tp--;else ton[++tp]={1,0};}
void qry(int u){ton[++tp]={2,u};}
void put(int u){add(u);for(int v:g[u]) put(v);}
void recall(int u){int v=siz[u];for(int i=0;i<v;i++) dec();}
void solve(int);
void calc(vector<int>&tmp,int l,int r)
{
if(l==r){solve(tmp[l]);return;}
int w=0,v=0;
for(int i=l;i<=r;i++) w+=siz[tmp[i]];
for(int i=l;i<=r;i++)
{
if(v<w/2 && i!=r) v+=siz[tmp[i]];
else
{
--i;
for(int j=i+1;j<=r;j++) put(tmp[j]);
calc(tmp,l,i);
for(int j=i+1;j<=r;j++) recall(tmp[j]);
for(int j=l;j<=i;j++) put(tmp[j]);
calc(tmp,i+1,r);
for(int j=l;j<=i;j++) recall(tmp[j]);
break;
}
}
}
void solve(int u)
{
vector<int>line,tmp;
for(int v=u;v;v=son[v]) line.push_back(v);
for(int v:line) add(v);
for(int u:line)
for(int v:g[u]) if(v!=son[u]) tmp.push_back(v);
sort(tmp.begin(),tmp.end(),[&](int x,int y){return siz[x]<siz[y];});
if(!tmp.empty()) calc(tmp,0,tmp.size()-1);
for(int v:line) dec();
for(int u:line)
{
add(u);for(int v:g[u]) if(v!=son[u]) put(v);
}
for(int i=line.size()-1;i>=0;i--)
{
dec();for(int v:g[line[i]]) if(v!=son[line[i]]) recall(v);
qry(line[i]);
}
}
int main()
{
int n;scanf("%d",&n);
for(int i=2;i<=n;i++) scanf("%d",&fa[i]),g[fa[i]].push_back(i);
dfs0(1);
solve(1);
cerr<<tp<<endl;
for(int i=1;i<=tp;i++) if(ton[i].first==0) printf("+%d",ton[i].second);
else if(ton[i].first==1) putchar('-');
else if(ton[i].first==2) printf("=%d",ton[i].second);
else printf("*%d",ton[i].second);
puts("!");
return 0;
}
|
L. Rikka with Generals
设 $a_i$ 表示第 $i$ 个将军的领地。容易发现，对于任意 $i$ 和 $i+1$，它们至多只会交换一次。所以我们可以用 dp 记录 $f_{i,j}$ 表示前 $i-1$ 个数已经确定，第 $i$ 个数为 $j$，并且 $i+1$ 到 $n$ 都没有被交换过。分类讨论一下可以发现从一个位置出发最多只有 $2$ 种决策，直接转移是 $O(n^2)$ 的。
但是注意到每个位置最多只会被交换度数次，所以一个位置的值域大小只有两倍度数，总复杂度 $O(n)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
const int N=200010,mod=998244353;
int a[N],b[N],x[N],y[N],n;
map<int,int>f[N];vector<int>g[N];
vector<int>::iterator find(int x,int y){return lower_bound(g[x].begin(),g[x].end(),y);}
void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
int dfs(int i,int j)
{
if(i==n) return 1;if(f[i].count(j)) return f[i][j];
int &v=f[i][j];v=dfs(i+1,b[i+1]);
auto q=find(j,i+1);
if(q!=g[j].end())
{
int p=*q;
if(p==i+1) add(v,dfs(i+1,j));
else
{
auto l=find(b[p],i+1),r=find(b[p],p-1);
if(r!=g[b[p]].end() && *r==p-1 && r-l+1==p-i-1) add(v,dfs(p,b[p-1]));
}
}
return v;
}
int main()
{
int t;scanf("%d",&t);
while(t --> 0)
{
scanf("%d",&n);
for(int i=1;i<n;i++) scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[a[i]]=i;
for(int i=1;i<n;i++) g[x[i]].push_back(a[y[i]]),g[y[i]].push_back(a[x[i]]);
for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
printf("%d\n",dfs(1,b[1]));
for(int i=1;i<=n;i++) f[i].clear(),g[i].clear();
}
return 0;
}
|
C. Rikka with Random Tree
XJ 又搬原题了。。。
拆开式子，可以拆成每个点深度期望和与每个点作为 lca 的概率。
可以用莫比乌斯反演或者直接容斥（其实是一样的）。
代码
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<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 300010
using namespace std;
int n,mod;
void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
void dec(int &x,int y){x=(x-y<0?x-y+mod:x-y);}
int f[N],g[N],w[N],c[N],iv[N];vector<int>r[N];
int main()
{
scanf("%d%d",&n,&mod);
iv[1]=1;for(int i=2;i<=n;i++) iv[i]=1ll*(mod-mod/i)*iv[mod%i]%mod;
int r1=0,r2=0;
f[1]=0;
for(int i=1;i<=n;i++)
{
f[i]=1ll*f[i]*iv[c[i]]%mod,add(r1,1ll*n*f[i]%mod);
for(int j=i*2;j<=n;j+=i) c[j]++,add(f[j],f[i]+1),r[j].push_back(i);
}
g[1]=1;
for(int i=n;i;i--)
{
int s=1;
for(int j=2;i*j<=n;j++)
{
int res=0;for(int v:r[j]) add(res,g[v]);
g[j]=1ll*res*iv[c[i*j]]%mod,s=(s+g[j])%mod;
}
w[i]=1ll*s*s%mod;
for(int j=2;i*j<=n;j++) w[i]=(w[i]-1ll*g[j]*g[j]%mod*w[i*j]%mod+mod)%mod;
add(r2,1ll*f[i]*w[i]%mod);
}
printf("%lld\n",2ll*(r1-r2+mod)%mod);
return 0;
}
|