You can view Chinese editorial here: https://www.luogu.com.cn/blog/Caro23333/codeforces-round-641-zhong-wen-ti-xie
Div2.A Problem and editorial by BlueSmoke
Editorial
Tutorial is loading...
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--)
{
int n,k;
cin >> n >> k;
if(n%2==0)
{
cout << n+2*k << endl;
continue;
}
int p = 0;
for(int i = n; i>=2; i--)
if(n%i==0)
p = i;
cout << n+p+2*(k-1) << endl;
}
return 0;
}
Div2.B Problem and editorial by BlueSmoke
Editorial
Tutorial is loading...
Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 500005;
inline int readint()
{
int res = 0;
char c = 0;
while(!isdigit(c))
c = getchar();
while(isdigit(c))
res = res*10+c-'0', c = getchar();
return res;
}
int n,a[MAXN],f[MAXN];
int main()
{
int T = readint();
while(T--)
{
n = readint();
for(int i = 1; i<=n; i++)
a[i] = readint();
for(int i = 1; i<=n; i++)
f[i] = 1;
for(int i = 1; i<=n; i++)
for(int j = i*2; j<=n; j += i)
if(a[i]<a[j])
f[j] = max(f[j],f[i]+1);
int ans = 0;
for(int i = 1; i<=n; i++)
ans = max(ans,f[i]);
cout << ans << endl;
}
return 0;
}
Div1.A Problem and editorial by mydiplomacy
Editorial
Tutorial is loading...
Code
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=100005;
int n;
ll a[maxn];
ll pre[maxn],suf[maxn];
ll gcd(ll x, ll y)
{
if(y==0) return x;
else return gcd(y,x%y);
}
ll ga,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
pre[1]=a[1]; suf[n]=a[n];
for(int i=2;i<=n;i++)
pre[i]=gcd(pre[i-1],a[i]);
for(int i=n-1;i>=1;i--)
suf[i]=gcd(suf[i+1],a[i]);
for(int i=0;i<=n-1;i++)
{
if(i==0)
ans=suf[2];
else if(i==n-1)
ans=ans*pre[n-1]/gcd(pre[n-1],ans);
else
ans=ans*gcd(pre[i],suf[i+2])/gcd(gcd(pre[i],suf[i+2]),ans);
}
printf("%lld\n",ans);
return 0;
}
Div1.B Problem and editorial by A.K.E.E.
Editorial
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define x first
#define y second
#define mp make_pair
#define pb push_back
template <typename TYPE> inline void chkmax(TYPE &x,TYPE y){x<y?x=y:TYPE();}
template <typename TYPE> inline void chkmin(TYPE &x,TYPE y){y<x?x=y:TYPE();}
template <typename TYPE> void readint(TYPE &x)
{
x=0;int f=1;char c;
for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=x*10+c-'0';
x*=f;
}
const int MAXN=500005;
int n,k,a[MAXN];
bool solve()
{
readint(n),readint(k);
bool flag=0;
for(int i=1;i<=n;++i)
{
readint(a[i]);
if(a[i]<k)a[i]=0;
else if(a[i]>k)a[i]=2;
else a[i]=1;
if(a[i]==1)flag=1;
}
if(!flag)return 0;
if(n==1)return 1;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n && j-i<=2;++j)
if(a[i] && a[j])return 1;
return 0;
}
int main()
{
int T;
readint(T);
while(T--)printf(solve()?"yes\n":"no\n");
return 0;
}
Div1.C Problem and editorial by A.K.E.E.
Editorial
Tutorial is loading...
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MAXN = 1005;
inline ll readint()
{
ll res = 0, f = 1;
char c = 0;
while(!isdigit(c))
{
c = getchar();
if(c=='-')
f = -1;
}
while(isdigit(c))
res = res*10+c-'0', c = getchar();
return res*f;
}
int n,m,T,a[MAXN][MAXN];
char str[MAXN];
int f[MAXN][MAXN],pos[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
bool vis[MAXN][MAXN];
inline bool check(int x, int y)
{
for(int i = 0; i<4; i++)
{
int nx = x+pos[i][0], ny = y+pos[i][1];
if(a[nx][ny]==a[x][y])
return true;
}
return false;
}
pii q[MAXN*MAXN];
inline void bfs()
{
int front = 0, rear = 0;
for(int i = 1; i<=n; i++)
for(int j = 1; j<=m; j++)
if(check(i,j))
f[i][j] = 0, vis[i][j] = true, q[rear++] = mp(i,j);
while(front<rear)
{
pii now = q[front++];
for(int i = 0; i<4; i++)
{
int nx = now.fi+pos[i][0], ny = now.se+pos[i][1];
if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny])
continue;
f[nx][ny] = f[now.fi][now.se]+1;
vis[nx][ny] = true;
q[rear++] = mp(nx,ny);
}
}
}
int main()
{
n = readint(), m = readint(), T = readint();
memset(a,-1,sizeof(a));
for(int i = 1; i<=n; i++)
{
scanf("%s",str+1);
for(int j = 1; j<=m; j++)
a[i][j] = str[j]-'0';
}
bfs();
int x,y;
ll t;
while(T--)
{
x = readint(), y = readint(), t = readint();
if(vis[x][y])
printf("%d\n",a[x][y]^(max(0ll,t-f[x][y])&1));
else
printf("%d\n",a[x][y]);
}
return 0;
}
Div1.D Problem and editorial by Rebelz
Part of solution by Elegia
Editorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}
int readint(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int cys=998244353;
int n,m;
ll a[100005],ans[300005];
ll qpow(ll x,ll p){
ll ret=1;
for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
return ret;
}
int main(){
n=readint();
for(int i=1;i<=n;i++) a[i]=readint(),m+=a[i];
ll invm=qpow(m,cys-2),invn1=qpow(n-1,cys-2);
for(int i=m;i>=1;i--){
ll k1=i*invm%cys*invn1%cys,k2=(m-i)*invm%cys;
ans[i]=(k2*ans[i+1]+1)%cys*qpow(k1,cys-2)%cys;
}
for(int i=1;i<=m;i++) ans[i]=(ans[i]+ans[i-1])%cys;
ll res=0;
for(int i=1;i<=n;i++) res=(res+ans[m-a[i]])%cys;
res=(res+cys-ans[m]*(n-1)%cys)%cys;
printf("%lld\n",res*qpow(n,cys-2)%cys);
return 0;
}
Div1.E Problem and editorial by A.K.E.E.
Editorial
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
#define x first
#define y second
#define pb push_back
const int MAXN=200005;
int n,m,cnt;
pii a[MAXN];
bool avis[MAXN];
struct Range
{
int l,r,type;
ll val;
Range(){}
Range(int l,int r,int type,ll val):l(l),r(r),type(type),val(val){}
}b[MAXN];
int f[2][MAXN],wh[2][MAXN],res[MAXN];
vector<int> str[2][MAXN];
bool check(ll s,int l,int r)
{
if(s<=0)return !s && r-l+1>=0;
ll L=1,R=r-l+1,mid,ans=0;
while(L<=R)
{
mid=(L+R)>>1;
if((l+l+mid-1)*mid<=s*2)ans=mid,L=mid+1;
else R=mid-1;
}
return s*2<=(r+r-ans+1)*ans;
}
void modify(ll s,int l,int r,vector<int> &tar,int start)
{
ll L=1,R=r-l+1,mid,ans=0;
while(L<=R)
{
mid=(L+R)>>1;
if((l+l+mid-1)*mid<=s*2)ans=mid,L=mid+1;
else R=mid-1;
}
for(int i=l;i<=r;i++)
if(ans && (i+i+ans-2)*(ans-1)<=(s-i)*2 && (s-i)*2<=(r+r-ans+2)*(ans-1))
{--ans,s-=i;tar.pb(1);}
else tar.pb(0);
}
void update(int i,int ti,int ti_1,int pos,ll d)
{
if(pos<=f[ti][i])return;
str[ti][i].clear();
f[ti][i]=pos;wh[ti][i]=ti_1;
str[ti][i].pb(1);
for(int j=f[ti][i]+1;j<=b[i].r;j++)str[ti][i].pb(0);
modify(d-f[ti][i],b[i].r+1,f[ti_1][i-1]-1,str[ti][i],f[ti][i]);
}
int main()
{
#ifndef ONLINE_JUDGE
//freopen("code.in","r",stdin);
//freopen("code.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
ll y;
scanf("%lld",&y);
if(!y)continue;
a[++m]=make_pair(n-i+1,y);
avis[n-i+1]=1;
}
if(!m)
{
for(int i=1;i<=n;i++)putchar('0');
return 0;
}
sort(a+1,a+m+1);
b[cnt=1]=Range(a[m].x,a[m].x,2,a[m].y);
for(int i=m-1;i;i--)
{
if(a[i].y==a[i+1].y)b[cnt].l=a[i].x,b[cnt].type=0;
else if(a[i].y==a[i+1].y-1)b[cnt].l=a[i].x,b[cnt].type=1,b[cnt].val--;
else b[++cnt]=Range(a[i].x,a[i].x,2,a[i].y);
}
b[cnt+1]=Range(-1,-1,0,0);
bool error=0;
f[0][0]=-1;f[1][0]=n+1;
for(int i=1;i<=cnt;i++)
{
f[0][i]=f[1][i]=-1;
for(int t=0;t<=1;t++)
if(f[t][i-1]>b[i].r)
{
if(b[i].type==0 || b[i].type==2)
{
ll d=(b[i].val-1)-(b[i-1].val-1+t);
int pos=-1;
for(int j=min(b[i].l-1ll,d);j>b[i+1].r;--j)
if(check(d-j,b[i].r+1,f[t][i-1]-1)){pos=j;break;}
update(i,0,t,pos,d);
}
if(b[i].type==1 || b[i].type==2)
{
ll d=b[i].val-(b[i-1].val-1+t);
if(check(d-b[i].l,b[i].r+1,f[t][i-1]-1))
update(i,1,t,b[i].l,d);
}
}
if(f[0][i]<0 && f[1][i]<0 && i==cnt && !b[i].type)error=1;
}
if(error)
{
for(int t=0;t<=1;t++)
if(f[t][cnt-1]>b[cnt].r)
{
ll d=(b[cnt].val-1)-(b[cnt-1].val-1+t);
int pos=-1;
for(int j=min((ll)b[cnt].r,d);j>=b[cnt].l;--j)
{
if(avis[j])continue;
if(check(d-j,b[cnt].r+1,f[t][cnt-1]-1)){pos=j;break;}
}
update(cnt,0,t,pos,d);
}
}
int cur=(f[1][cnt]>0);
for(int i=1;i<f[cur][cnt];i++)res[i]=0;
for(int i=cnt;i>0;i--)
{
for(int j=0;j<(int)str[cur][i].size();j++)res[j+f[cur][i]]=str[cur][i][j];
cur=wh[cur][i];
}
for(int i=n;i>0;i--)putchar(res[i]+'0');
return 0;
}
Div1.F Problem and editorial by Rebelz
Hard version solution by Elegia
Editorial for easy version
Tutorial is loading...
Code
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}
int readint(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int cys=998244353;
int n;
ll fac[5005],inv[5005],d[5005][5005],ans[5005];
ll qpow(ll x,ll p){
ll ret=1;
for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
return ret;
}
int main(){
n=readint();
d[0][0]=fac[0]=inv[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%cys;
inv[n]=qpow(fac[n],cys-2);
for(int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%cys;
for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) d[i][j]=(d[i-1][j-1]*(i-j+1)+d[i-1][j]*j)%cys;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans[i]=(ans[i]+d[j][i]*inv[j])%cys;
for(int i=1;i<=n;i++) printf("%lld ",ans[i]*fac[n]%cys);
printf("\n");
return 0;
}
Editorial for hard version
Tutorial is loading...
Code
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}
int readint(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int cys=998244353,g=3,invg=(cys+1)/3;
int n;
ll ni[200015],fac[200015],inv[200015],tw[200005];
int mod(int x){return x>=cys?x-cys:x;}
ll qpow(ll x,ll p){
ll ret=1;
for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
return ret;
}
vi operator+(vi a,vi b){
vi ret(max(a.size(),b.size()));
for(int i=0;i<ret.size();i++) ret[i]=mod((i<a.size()?a[i]:0)+(i<b.size()?b[i]:0));
return ret;
}
vi operator-(vi a,vi b){
vi ret(max(a.size(),b.size()));
for(int i=0;i<ret.size();i++) ret[i]=mod((i<a.size()?a[i]:0)+cys-(i<b.size()?b[i]:0));
return ret;
}
vi operator*(vi a,ll b){
for(int i=0;i<a.size();i++) a[i]=1ll*a[i]*b%cys;
return a;
}
vi operator>>(vi a,int b){
for(int i=0;i<a.size()-b;i++) a[i]=a[i+b];
a.resize(a.size()-b);
return a;
}
namespace poly{
int N,l;
int A[1100000],B[1100000],r[1100000],pre1[20][600000],pre2[20][600000];
void pre(){
for(int i=1,r=0;i<(1<<19);i<<=1,r++){
int w=1,wn=qpow(g,(cys-1)/(i<<1));
for(int j=0;j<i;j++,w=1ll*w*wn%cys) pre1[r][j]=w;
}
for(int i=1,r=0;i<(1<<19);i<<=1,r++){
int w=1,wn=qpow(invg,(cys-1)/(i<<1));
for(int j=0;j<i;j++,w=1ll*w*wn%cys) pre2[r][j]=w;
}
}
void ntt(int *A,int N,int f){
for(int i=0;i<N;i++) if(i<r[i]) swap(A[i],A[r[i]]);
for(int i=1,r=0;i<N;i<<=1,r++){
for(int j=0;j<N;j+=(i<<1)){
for(int k=j;k<j+i;k++){
int x=A[k],y=1ll*A[k+i]*(f>0?pre1[r][k-j]:pre2[r][k-j])%cys;
A[k]=mod(x+y); A[k+i]=mod(x+cys-y);
}
}
}
if(f<0){
int invn=qpow(N,cys-2);
for(int i=0;i<N;i++) A[i]=1ll*A[i]*invn%cys;
}
}
void init(int t){
N=1,l=0;
for(;N<t;N<<=1) l++;
for(int i=0;i<N;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
}
void getmul(){
ntt(A,N,1); ntt(B,N,1);
for(int i=0;i<N;i++) A[i]=1ll*A[i]*B[i]%cys;
ntt(A,N,-1);
}
vi mul(vi a,vi b){
init(a.size()+b.size());
for(int i=0;i<N;i++) A[i]=i<a.size()?a[i]:0;
for(int i=0;i<N;i++) B[i]=i<b.size()?b[i]:0;
getmul();
vi ret(a.size()+b.size()-1);
for(int i=0;i<ret.size();i++) ret[i]=A[i];
return ret;
}
vi polyinv(vi a,int l){
if(l==1) return vi(1,qpow(a[0],cys-2));
a.resize(l);
vi b=polyinv(a,(l+1)/2);
init(l<<1);
for(int i=0;i<N;i++) A[i]=i<l?a[i]:0;
for(int i=0;i<N;i++) B[i]=i<(l+1)/2?b[i]:0;
ntt(A,N,1); ntt(B,N,1);
for(int i=0;i<N;i++) A[i]=1ll*A[i]*B[i]%cys*B[i]%cys;
ntt(A,N,-1);
vi t=b*2;
t.resize(l);
for(int i=0;i<l;i++) t[i]=mod(t[i]+cys-A[i]);
return t;
}
vi polydiff(vi a){
for(int i=0;i<a.size()-1;i++) a[i]=1ll*(i+1)*a[i+1]%cys;
a.resize(a.size()-1);
return a;
}
vi polyint(vi a){
a.resize(a.size()+1);
for(int i=a.size()-1;i>=1;i--) a[i]=1ll*a[i-1]*ni[i]%cys;
a[0]=0;
return a;
}
vi polyln(vi a,int l){
return polyint(mul(polydiff(a),polyinv(a,l)));
}
vi polyexp(vi a,int l){
if(l==1) return vi(1,1);
a.resize(l);
vi b=polyexp(a,(l+1)/2);
init(l<<1);
vi t=mul(b,vi(1,1)-polyln(b,l)+a);
t.resize(l);
return t;
}
vi polypow(vi a,int l,int k){
return polyexp(polyln(a,l)*k,l);
}
}
vi getans(){
vi f(0);
for(int i=0;i<=n+1;i++) f.push_back(inv[i+1]);
vi tmp=poly::mul(f,poly::polyinv((vi(1,1)-f)>>1,n+1));
vi tw(0); tw.resize(n);
for(int i=0;i<n;i++) tw[i]=tmp[i+1];
vi h(0);
h.push_back(1),h.push_back(1);
h=poly::polyinv(poly::polyln(h,n+3)>>1,n+2);
vi g=poly::polyinv((vi(1,1)-h)>>1,n+1);
vi ph=poly::polypow(h,n+1,n+1);
vi t1=poly::mul(g,ph);
vi tmp1=poly::mul(poly::polydiff(h),ph);
tmp1.resize(n+1);
vi tmp2=poly::mul(g,g);
tmp2.resize(n+1);
vi t2=poly::mul(tmp1,tmp2);
for(int i=0;i<n;i++) tw[i]=mod(tw[i]+cys-ni[n+1]*mod(t1[i+1]*(n-i+1)%cys+t2[i+1])%cys);
for(int i=0;i<n;i++) tw[i]=tw[i]*fac[i]%cys;
reverse(tw.begin(),tw.end());
tmp.clear();
for(int i=0;i<n;i++) tmp.push_back(i&1?cys-inv[i]:inv[i]);
tw=poly::mul(tw,tmp);
tw.resize(n);
reverse(tw.begin(),tw.end());
return tw;
}
int main(){
poly::pre();
n=readint();
fac[0]=inv[0]=1;
for(int i=1;i<=n+5;i++) fac[i]=fac[i-1]*i%cys;
inv[n+5]=qpow(fac[n+5],cys-2);
for(int i=n+4;i>=1;i--) inv[i]=inv[i+1]*(i+1)%cys;
for(int i=1;i<=n+5;i++) ni[i]=inv[i]*fac[i-1]%cys;
vi res=getans();
for(int i=0;i<n;i++) printf("%lld ",res[i]*fac[n]%cys*inv[i]%cys);
printf("\n");
return 0;
}
You can also view Div1.F editorial by Elegia here: https://mirror.codeforces.com/blog/entry/77280
Anyway, hope you like these problems and thank you for participating!
