A. Petr
Meaning:
Given a string S, ask how many kinds of substrings start with stat string and end with end string. If they are exactly the same, they are regarded as one.
Solution:
Considering double hash, judging the equality of strings by hash value can achieve
n
2
n^2
n2 complexity.
wa point: for the end string, its beginning is shown in the following table
j
j
j should be greater than or equal to the beginning subscript of stat
i
i
i and
j
+
l
e
n
2
−
1
>
=
i
+
l
e
n
1
−
1
j+len2-1>=i+len1-1
j+len2−1>=i+len1−1.
Then, T68 is always used during the game, because a map is opened. In the no loop, judge whether there is this legal string in the map. In this way, there is an additional complexity of log, which will affect t.
The correct way is to open a vector, and finally sort and unique to redo it. Complexity is
n
2
+
l
o
g
n
n^2+logn
n2+logn
The code is too ugly to debug. You should write a function next time.
#include<bits/stdc++.h>
typedef long long ll;
const int maxn = 200050;
using namespace std;
ll k1[maxn],k2[maxn];
ll p1=131,p2=13331;
ll mod1=1000000007,mod2=1000000009;
ll hash1[maxn],hash2[maxn];
int main(){
string s;
cin>>s;
string s1,s2;
cin>>s1>>s2;
int len1=s1.length(),len2=s2.length();
k1[0]=k2[0]=1;
for(int i=1;i<2022;i++)k1[i]=k1[i-1]*p1%mod1,k2[i]=k2[i-1]*p2%mod2;
for(int i=0;i<s.length();i++){
hash1[i+1]=(hash1[i]*p1%mod1+s[i]-'a'+1)%mod1;
hash2[i+1]=(hash2[i]*p2%mod2+s[i]-'a'+1)%mod2;
}
ll hh11=0,hh12=0,hh21=0,hh22=0;
for(int i=0;i<len1;i++){
hh11=(hh11*p1%mod1+s1[i]-'a'+1)%mod1;
hh12=(hh12*p2%mod2+s1[i]-'a'+1)%mod2;
}
for(int i=0;i<len2;i++){
hh21=(hh21*p1%mod1+s2[i]-'a'+1)%mod1;
hh22=(hh22*p2%mod2+s2[i]-'a'+1)%mod2;
}
int ans=0;
vector<pair<ll,ll> >v;
for(int i=0;i+len1-1<s.length();i++){
for(int j=max(i,i+len1-len2);j+len2-1<s.length();j++){
ll hashl1=(hash1[i+len1]-hash1[i]*k1[len1]%mod1+mod1)%mod1;
ll hashl2=(hash2[i+len1]-hash2[i]*k2[len1]%mod2+mod2)%mod2;
ll hashr1=(hash1[j+len2]-hash1[j]*k1[len2]%mod1+mod1)%mod1;
ll hashr2=(hash2[j+len2]-hash2[j]*k2[len2]%mod2+mod2)%mod2;
ll q1=(hash1[j+len2]-hash1[i]*k1[j+len2-i]%mod1+mod1)%mod1;
ll q2=(hash2[j+len2]-hash2[i]*k2[j+len2-i]%mod2+mod2)%mod2;
if(hashl1==hh11&&hashl2==hh12&&hashr1==hh21&&hashr2==hh22)v.push_back(make_pair(q1,q2));
}
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
cout<<v.size()<<"\n";
return 0;
}
B. DNA Evolution
Meaning:
You have a string S composed of a, t, G and C. There are two operations. One is op=1, and the character at x is modified to C. the second operation gives you a string e with a length of no more than 10, which appears in a loop (e.g. eeeee ee). Ask
[
l
,
r
]
[l,r]
The S string in the [l,r] interval is the same as (eeee) with several characters.
Solution:
Consider maintaining 4 characters and all States with length of 1-10, and maintain with multi-dimensional segment tree.
tree[id][k][len][m],id represents the subscript of the line segment tree, K represents the character, len represents the length of the string, and m represents the value of the current position after taking the remainder of len. Maintain sum values for each state.
In this problem, the space of the line segment tree will be MLE four times, and the space of the tree array will be four times less.
Tree array:
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <cassert>
#include <iomanip>
#include <deque>
#include <time.h>
#include <bitset>
using namespace std;
#define ll long long
#define maxn 100005
#define mod 1000000007
#define MOD 998244353
#define Mod 1000000009
#define eps 1e-10
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll INF=0x3f3f3f3f;
const ll mod1=1e9+7;
const ll mod2=1e9+9;
template <typename T>
inline void read(T& X) {X = 0; int w = 0; char ch = 0;while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();if (w) X = -X;}
char F[200];inline void write(int x){if(x == 0){putchar('0');return;}int tmp = x > 0 ? x : -x;int cnt = 0;if(x < 0)putchar( '-' );while(tmp > 0){F[cnt++] = tmp % 10 + '0';tmp /= 10;}while(cnt > 0)putchar(F[--cnt]) ;}
template<typename T> void print(T x){if(x>9) print(x/10);putchar(x%10+'0');}
ll q_pow(ll x,ll y,ll M){ll ans=1;while(y){if(y%2){y--;ans=ans*x%M;}else {y/=2;x=x*x%M;}}return ans;}
int tree[maxn][4][11][10];
int lowbit(int x){return x&(-x);}
void add(int x,int pos,int k,int val){
for(;x<maxn;x+=lowbit(x)){
for(int j=1;j<=10;j++){
tree[x][k][j][pos%j]+=val;
}
}
}
int sum(int i,int xh,int k,int len){
int ans=0;
for(;i;ans+=tree[i][k][len][xh],i-=lowbit(i));
return ans;
}
int query(int l,int r,int xh,int len,int k){
return sum(r,xh,k,len)-sum(l-1,xh,k,len);
}
map<char,int>mp;
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
mp['A']=0;mp['T']=1;mp['G']=2;mp['C']=3;
string s;
cin>>s;
for(int i=0;i<s.length();i++){
add(i+1,i+1,mp[s[i]],1);
}
int q;
cin>>q;
int op,l,r;
string ss;
while(q--){
cin>>op;
if(op==1){
cin>>l>>ss;
add(l,l,mp[s[l-1]],-1);
add(l,l,mp[ss[0]],1);
s[l-1]=ss[0];
}
else{
cin>>l>>r>>ss;
int len=ss.length();
int ans=0;
for(int i=0;i<ss.length();i++){
ans+=query(l,r,(i+l)%len,len,mp[ss[i]]);
}
cout<<ans<<"\n";
}
}
return 0;
}
Segment tree:
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <cassert>
#include <iomanip>
#include <deque>
#include <time.h>
#include <bitset>
using namespace std;
#define ll long long
#define maxn 100005
#define mod 1000000007
#define MOD 998244353
#define Mod 1000000009
#define eps 1e-10
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll INF=0x3f3f3f3f;
const ll mod1=1e9+7;
const ll mod2=1e9+9;
template <typename T>
inline void read(T& X) {X = 0; int w = 0; char ch = 0;while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();if (w) X = -X;}
char F[200];inline void write(int x){if(x == 0){putchar('0');return;}int tmp = x > 0 ? x : -x;int cnt = 0;if(x < 0)putchar( '-' );while(tmp > 0){F[cnt++] = tmp % 10 + '0';tmp /= 10;}while(cnt > 0)putchar(F[--cnt]) ;}
template<typename T> void print(T x){if(x>9) print(x/10);putchar(x%10+'0');}
ll q_pow(ll x,ll y,ll M){ll ans=1;while(y){if(y%2){y--;ans=ans*x%M;}else {y/=2;x=x*x%M;}}return ans;}
int tree[maxn<<2][4][11][10];
void pushup(int k,int id){
for(int i=1;i<=10;i++){
for(int j=0;j<i;j++){
tree[id][k][i][j]=tree[id<<1][k][i][j]+tree[id<<1|1][k][i][j];
}
}
return ;
}
void update(int id,int l,int r,int k,int pos,int val){
if(l==r){
for(int i=1;i<=10;i++){
tree[id][k][i][pos%i]+=val;
}
return ;
}
int mid=(l+r)>>1;
if(mid>=pos)update(id<<1,l,mid,k,pos,val);
else update(id<<1|1,mid+1,r,k,pos,val);
pushup(k,id);
}
int query(int id,int l,int r,int k,int xh,int lx,int ly,int len){
if(l>=lx&&r<=ly)return tree[id][k][len][xh];
int mid=(l+r)>>1;
int ans=0;
if(mid>=lx)ans+=query(id<<1,l,mid,k,xh,lx,ly,len);
if(mid<ly) ans+=query(id<<1|1,mid+1,r,k,xh,lx,ly,len);
return ans;
}
map<char,int>mp;
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
mp['A']=0;mp['T']=1;mp['G']=2;mp['C']=3;
string s;
cin>>s;
for(int i=0;i<s.length();i++){
update(1,1,s.length(),mp[s[i]],i+1,1);
}
int q;
cin>>q;
int op,l,r;
string ss;
while(q--){
cin>>op;
if(op==1){
cin>>l>>ss;
update(1,1,s.length(),mp[s[l-1]],l,-1);
update(1,1,s.length(),mp[ss[0]],l,1);
s[l-1]=ss[0];
}
else{
cin>>l>>r>>ss;
int len=ss.length();
int ans=0;
for(int i=0;i<ss.length();i++){
// cout<<query(1,1,s.length(),mp[ss[i]],(i+l)%len,l,r,len)<<"\n";
ans+=query(1,1,s.length(),mp[ss[i]],(i+l)%len,l,r,len);
}
cout<<ans<<"\n";
}
}
return 0;
}
D. Find Maximum
Meaning:
f
(
x
)
=
∑
i
=
0
n
−
1
a
i
b
i
t
(
i
)
,
b
i
t
(
i
)
=
(
x
>
>
i
)
&
1
f(x)=\sum_{i=0}^{n-1}a_ibit(i),bit(i)=(x>>i)\&1
f(x)=∑i=0n−1aibit(i),bit(i)=(x>>i)&1
x belongs to
[
1
,
n
−
1
]
[1,n-1]
[1,n−1]
Solution:
For N binary processing, if the current bit is 1, the current bit can not be taken, and all subsequent positions can be taken, or it can be taken according to n.
#include<bits/stdc++.h>
typedef long long ll;
const int maxn = 200050;
using namespace std;
ll a[maxn];
ll sum[maxn];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
string s;
ll ans=0;
cin>>s;
reverse(s.begin(),s.end());
ll now=0;
// cout<<s<<"\n";
for(int i=0;i<n;i++){
// cout<<sum[n-i]<<" "<<now<<"\n";
if(s[i]=='1'){
ans=max(ans,now+sum[n-i-1]);
now+=a[n-i];
}
}
ans=max(ans,now);
cout<<ans;
return 0;
}
E. Bots
Meaning:
There are two robots. Each robot can take n steps. Ask how many positions may exist after walking.
Solution:
You can go altogether
2
n
2n
Step 2n, the answer is
∑
i
=
0
n
∑
j
=
0
n
C
i
+
j
i
\sum_{i=0}^n\sum_{j=0}^nC_{i+j}^i
∑i=0n∑j=0nCi+ji
First, yes
∑
j
=
0
n
C
i
+
j
i
\sum_{j=0}^nC_{i+j}^i
Σ j=0n Ci+ji solution
=
C
i
i
+
C
i
+
1
i
+
.
.
.
+
C
i
+
n
i
=C_i^i+C_{i+1}^i+...+C_{i+n}^i
=Cii+Ci+1i+...+Ci+ni
=
C
i
+
1
i
+
1
+
C
i
+
1
i
+
.
.
.
C
i
+
n
i
=C_{i+1}^{i+1}+C_{i+1}^i+...C_{i+n}^i
=Ci+1i+1+Ci+1i+...Ci+ni
because
C
n
m
=
C
n
−
1
m
+
C
n
−
1
m
−
1
C_n^m=C_{n-1}^m+C_{n-1}^{m-1}
Cnm=Cn−1m+Cn−1m−1
Recursion:
∑
j
=
0
n
C
i
+
j
i
=
C
i
+
n
+
1
i
+
1
=
C
i
+
n
+
1
n
\sum_{j=0}^nC_{i+j}^i=C_{i+n+1}^{i+1}=C_{i+n+1}^n
∑j=0nCi+ji=Ci+n+1i+1=Ci+n+1n
The answer is transformed into
∑
i
=
0
n
C
i
+
n
+
1
n
\sum_{i=0}^nC_{i+n+1}^n
∑i=0nCi+n+1n
=
C
n
+
1
n
+
C
n
+
2
n
+
.
.
.
+
C
2
n
+
1
n
=C_{n+1}^n+C_{n+2}^n+...+C_{2n+1}^n
=Cn+1n+Cn+2n+...+C2n+1n
=
C
n
+
1
n
+
1
−
1
+
C
n
+
1
n
+
C
n
+
2
n
+
.
.
.
+
C
2
n
+
1
n
=C_{n+1}^{n+1}-1+C_{n+1}^n+C_{n+2}^n+...+C_{2n+1}^n
=Cn+1n+1−1+Cn+1n+Cn+2n+...+C2n+1n
=
C
2
n
+
2
n
+
1
−
1
=C_{2n+2}^{n+1}-1
=C2n+2n+1−1
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <cassert>
#include <iomanip>
#include <deque>
#include <time.h>
#include <bitset>
using namespace std;
#define ll long long
#define maxn 3002000
#define mod 1000000007
#define MOD 998244353
#define Mod 1000000009
#define eps 1e-10
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll INF=0x3f3f3f3f;
const ll mod1=1e9+7;
const ll mod2=1e9+9;
template <typename T>
inline void read(T& X) {X = 0; int w = 0; char ch = 0;while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();if (w) X = -X;}
char F[200];inline void write(int x){if(x == 0){putchar('0');return;}int tmp = x > 0 ? x : -x;int cnt = 0;if(x < 0)putchar( '-' );while(tmp > 0){F[cnt++] = tmp % 10 + '0';tmp /= 10;}while(cnt > 0)putchar(F[--cnt]) ;}
template<typename T> void print(T x){if(x>9) print(x/10);putchar(x%10+'0');}
ll q_pow(ll x,ll y,ll M){ll ans=1;while(y){if(y%2){y--;ans=ans*x%M;}else {y/=2;x=x*x%M;}}return ans;}
ll a[maxn];
ll b[maxn];
ll C(ll n,ll m){
return a[n]*b[m]%mod*b[n-m]%mod;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin>>n;
a[0]=1;
for(int i=1;i<=2*n+2;i++)a[i]=a[i-1]*i%mod;
b[2*n+2]=q_pow(a[2*n+2],mod-2,mod);
for(int i=2*n+1;i>=0;i--)b[i]=b[i+1]*(i+1ll)%mod;
cout<<(C(2*n+2,n+1)-1ll+mod)%mod;
return 0;
}
F. Purification
Meaning:
You want to clear all the squares, square "." You can use a spell to clear this row and this column. Box "E" cannot be used. The scheme with the least number of outputs or none.
Solution:
The scheme is at least N times. Just select n rows or N columns. For question 2b, the output should be output according to the row and column. In the case of N columns, the output is reversed.
#include<bits/stdc++.h>
typedef long long ll;
const int maxn = 200050;
using namespace std;
vector<int>g[maxn],h[maxn];
int xh[maxn]={0},xl[maxn]={0};
int main(){
int n;
char s;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>s;
if(s=='.'){
g[i].push_back(j),h[j].push_back(i);
xh[i]=1;xl[j]=1;
}
}
}
int sumh=0,suml=0;
for(int i=1;i<=n;i++){
if(xh[i])sumh++;
if(xl[i])suml++;
}
if(sumh<n&&suml<n){
cout<<"-1\n";
return 0;
}
if(sumh==n){
for(int i=1;i<=n;i++){
cout<<i<<" "<<g[i][0]<<"\n";
}
}
else{
for(int i=1;i<=n;i++){
cout<<h[i][0]<<" "<<i<<"\n";
}
}
return 0;
}
H. Dima and a Bad XOR
Meaning:
N rows, m numbers per row. Select a number for each row in n rows so that XOR is not 0 Output any scheme.
Solution:
It's easy to think of binary splitting. For each bit, as long as you can add up enough odd ones, it can not be 0 Take 1 from 1. If it is an odd number, it is directly consistent. If it is an even number, you can choose 0 if you look for 1, that is, there is no 0 in the row of 1. If there is, you can choose a 0.
#include<bits/stdc++.h>
typedef long long ll;
const int maxn = 200050;
using namespace std;
int a[555][555];
int b[555][555];
int ans[555];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=0;i<=10;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=m;k++){
b[j][k]=(a[j][k]>>i)&1;
}
}
int sum=0;
int indexi=0,indexj=0;
for(int j=1;j<=n;j++)ans[j]=0;
for(int j=1;j<=n;j++){
int num=0,pos1,pos2;
for(int k=1;k<=m;k++){
num+=b[j][k];
if(b[j][k])ans[j]=k;
if(b[j][k]==0)pos1=j,pos2=k;
}
if(num)sum++;
if(num>=1&&num<m)indexi=pos1,indexj=pos2;
}
if(sum%2){
cout<<"TAK\n";
for(int j=1;j<=n;j++){
if(ans[j]==0)cout<<"1 ";
else cout<<ans[j]<<" ";
}return 0;
}
else if(indexi!=0&&indexj!=0){
cout<<"TAK\n";
for(int j=1;j<=n;j++){
if(ans[j]==0)cout<<"1 ";
else if(j==indexi)cout<<indexj<<" ";
else cout<<ans[j]<<" ";
}return 0;
}
}
cout<<"NIE\n";
return 0;
}
I. RGB Substring (hard version)
Meaning:
One character can be modified at a time. Ask the minimum modification times of k characters in the string that comply with the "RGB" cycle.
Solution:
There are only three Cycle States. Just judge all three. At that time 2b, I went directly to the line segment tree.
#include<bits/stdc++.h>
typedef long long ll;
const int maxn = 200050;
using namespace std;
string s;
char mp[3]={'R','G','B'};
struct node{
int ans[3];
int len;
}tree[maxn<<2];
void pushup(int id){
tree[id].len=tree[id<<1].len+tree[id<<1|1].len;
for(int i=0;i<3;i++){
tree[id].ans[i]=tree[id<<1].ans[i]+tree[id<<1|1].ans[(i+tree[id<<1].len)%3];
}
return;
}
void build(int id,int l,int r){
if(l==r){
tree[id].len=1;
for(int i=0;i<3;i++){
tree[id].ans[i]=(s[l]!=mp[i]);
}
return ;
}
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
pushup(id);
}
node query(int id,int l,int r,int lx,int ly){
if(l>=lx&&r<=ly){
return tree[id];
}
int mid=(l+r)>>1;
int minn=0x3f3f3f3f;
node a,b;
int f1=0,f2=0;
if(mid>=lx)a=query(id<<1,l,mid,lx,ly),f1=1;
if(mid<ly)b=query(id<<1|1,mid+1,r,lx,ly),f2=1;
if(f1&&f2){
node c;
c.len=a.len+b.len;
for(int i=0;i<3;i++){
c.ans[i]=a.ans[i]+b.ans[(i+a.len)%3];
}
return c;
}
if(f1)return a;
if(f2)return b;
}
int main(){
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
cin>>s;
s=" "+s;
build(1,1,n);
int ans=0x3f3f3f3f;
for(int i=1;i+k-1<=n;i++){
node now=query(1,1,n,i,i+k-1);
for(int j=0;j<3;j++){
ans=min(ans,now.ans[j]);
}
}
cout<<ans<<"\n";
}
return 0;
}
J. Up the Strip
Meaning:
Now you are in the position of n, you have two operations. One is that you can jump to
n
−
x
,
(
x
−
>
[
1
,
n
−
1
]
)
n-x,(x->[1,n-1])
N − x,(x − > [1, n − 1]). One you can jump to
n
x
,
(
x
−
>
[
2
,
n
]
)
\frac{n}{x},(x->[2,n])
xn, (x − > [2, n]), ask the number of schemes that jump to 1.
Solution:
Reverse thinking, jump from 1 to n, there are two operations, one can jump to
[
i
+
1
,
n
]
of
position
Set
Position of [i+1,n]
Position of [i+1,n]
One for all
j
,
[
i
∗
j
,
i
∗
j
+
j
)
area
between
all
can
with
from
i
jump
reach
j. [i * J, i * j + J) interval can jump from i to
j. [i * j,i * j+j) interval can jump from i to.
The number of intervals is
n
2
+
n
3
+
.
.
.
.
\frac{n}{2}+\frac{n}{3}+....
2n+3n+.... Is a harmonic series with a time complexity of
n
l
o
g
n
nlogn
nlogn
For interval addition, we use differential array, which can be maintained by O(1).
The initial value dp[1]=1. Since ans[1]=0, all dp[2]=-1.
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <cassert>
#include <iomanip>
#include <deque>
#include <time.h>
#include <bitset>
using namespace std;
#define ll long long
#define maxn 5002000
#define mod 1000000007
#define MOD 998244353
#define Mod 1000000009
#define eps 1e-10
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll INF=0x3f3f3f3f;
const ll mod1=1e9+7;
const ll mod2=1e9+9;
template <typename T>
inline void read(T& X) {X = 0; int w = 0; char ch = 0;while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();if (w) X = -X;}
char F[200];inline void write(int x){if(x == 0){putchar('0');return;}int tmp = x > 0 ? x : -x;int cnt = 0;if(x < 0)putchar( '-' );while(tmp > 0){F[cnt++] = tmp % 10 + '0';tmp /= 10;}while(cnt > 0)putchar(F[--cnt]) ;}
template<typename T> void print(T x){if(x>9) print(x/10);putchar(x%10+'0');}
ll q_pow(ll x,ll y,ll M){ll ans=1;while(y){if(y%2){y--;ans=ans*x%M;}else {y/=2;x=x*x%M;}}return ans;}
ll dp[maxn];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n,m;
cin>>n>>m;
dp[1]=1;dp[2]=m-1;
for(int i=1;i<=n;i++){
dp[i]=(dp[i]+dp[i-1])%m;
dp[i+1]=(dp[i+1]+dp[i])%m;//j=[i+1,n],dp[j]+=dp[i]
for(int j=2;j*i<=n;j++){
dp[j*i]=(dp[j*i]+dp[i])%m;
if(j*i+j<=n)dp[j*i+j]=((dp[j*i+j]-dp[i])%m+m)%m;
}
}
cout<<dp[n];
return 0;
}