kesoft题解

发布于 2022-02-02  7 次阅读

小楼昨夜又西北风

#include<complex>
#include<cstdio>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
const int N=1e5+7,M=1e6+7;
struct Question{
    int l,r,id;
}q[N];
int n,m,cnt=1,tot;
int a[N],c[N],num[N],pos[N],ans[N],f[M],prime[N],inv[N];
bool check[M];
int qread()
{
    int x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9')ch=getchar();
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
bool cmp(const Question &a,const Question &b)
{
    if(pos[a.l]==pos[b.l])return a.r<b.r;
    return pos[a.l]<pos[b.l];
}
void Change(int x,int v)
{
    cnt=1ll*cnt*inv[f[num[a[x]]]]%mod;
    num[a[x]]+=v*c[x];
    cnt=1ll*cnt*f[num[a[x]]]%mod;
}
void Init()
{
    check[1]=1;
    for(int i=2;i<M;i++)
    {
        if(!check[i])prime[++tot]=i,f[i]=1;
        for(int j=1;j<=tot && i*prime[j]<M;j++)
        {
            check[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
    f[0]=1;
    for(int i=1;i<M;i++)f[i]+=f[i-1];
    inv[1]=1;
    for(int i=2;i<N;i++)
        inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    int sqr=sqrt(n);
    for(int i=1;i<=n;i++)pos[i]=(i-1)/sqr+1;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        a[i]=qread();
    for(int i=1;i<=n;i++)
        c[i]=qread();
    for(int i=1;i<=m;i++)
    {
        q[i].l=qread();q[i].r=qread();
        q[i].id=i;
    }
    Init();
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++)
    {
        while(r<q[i].r)Change(++r,1);
        while(r>q[i].r)Change(r--,-1);
        while(l<q[i].l)Change(l++,-1);
        while(l>q[i].l)Change(--l,1);
        ans[q[i].id]=cnt;
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}

下雨了，可以来拯救吗？

#include<complex>
#include<cstdio>
using namespace std;
const int mod=998244353;
long long n;
int Fpow(long long b,int p)
{
    long long res=1;
    for(;p;p>>=1,b=b*b%mod)
        if(p&1)res=res*b%mod;
    return res;
}
int main()
{
    scanf("%lld",&n);
    long long ans=0;
    for(long long l=1,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        ans+=(r-l+1)*(n/l)%mod;
    }
    printf("%d\n",ans%mod*Fpow(n%mod,mod-2)%mod);
    return 0;
}

玫瑰依在

#include<complex>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+7;
int n,m,cnt;
long long K;
int a[N],b[N],c[N],d[N],e[N];
int qread()
{
    int x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9')ch=getchar();
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int Lowbit(int x){return x&-x;}
void Add(int x)
{
    for(;x<=m;x+=Lowbit(x))
        c[x]++;
}
int Query(int x)
{
    int res=0;
    for(;x;x-=Lowbit(x))
        res+=c[x];
    return res;
}
int Find(int x)
{
    int l=1,r=m,mid;
    while(l<r)
        if(d[mid=l+r>>1]<x)l=mid+1;
        else r=mid;
    return l;
}
void Discrete()
{
    sort(d+1,d+n+2);
    d[0]=-1;m=0;
    for(int i=1;i<=n+1;i++)
        if(d[i]!=d[i-1])d[++m]=d[i];
    for(int i=0;i<=n;i++)
        e[i]=Find(e[i]);
}
long long check(int x)
{
    for(int i=1;i<=n;i++)
        e[i]=e[i-1]+(a[i]>=x);
    for(int i=0;i<=n;i++)
        e[i]=e[i]*2-i,d[i+1]=e[i];
    Discrete();
    memset(c,0,sizeof(c));
    long long res=0;
    for(int i=0;i<=n;i++)
        if(i&1)Add(e[i]);
        else res+=Query(e[i]-1);
    memset(c,0,sizeof(c));
    for(int i=0;i<=n;i++)
        if(i&1)res+=Query(e[i]-1);
        else Add(e[i]);
    return res;
}
int main()
{
    scanf("%d%lld",&n,&K);
    for(int i=1;i<=n;i++)
        b[i]=a[i]=qread();
    b[0]=-1;
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
        if(b[i]!=b[i-1])b[++cnt]=b[i];
    int l=1,r=cnt,res=0;
    while(l<=r)
    {
        int mid=l+r>>1;
        long long t=check(b[mid]);
        if(t>=K)l=mid+1,res=mid;
        else r=mid-1;
    }
    printf("%d\n",b[res]);
    return 0;
}

拼不出的数

#include<complex>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+7;
int n;
int a[N];
int qread()
{
    int x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9')ch=getchar();
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        a[i]=qread();
    sort(a+1,a+n+1);
    long long sum=0;
    for(int i=1;i<=n;i++)
        if(a[i]>sum+1)
        {
            printf("%lld\n",sum+1);
            return 0;
        }
        else sum+=a[i];
    printf("%lld\n",sum+1);
    return 0;
}

樱花般的爱情

#include<complex>
#include<cstdio>
using namespace std;
const int mod=1e9+7;
const int N=5e5+7;
int n;
long long ans;
int s[N>>1],a[N<<1];
int Fpow(long long b,int p)
{
    long long res=1;
    for(;p;p>>=1,b=b*b%mod)
        if(p&1)res=res*b%mod;
    return res;
}
int main()
{
    scanf("%d",&n);
    s[0]=1;
    for(int i=1;i*2<=n;i++)
        s[i]=1ll*s[i-1]*(2*i-1)%mod;
    for(int i=n+1;i<=n+n-1;i++)
    {
        a[i]=1ll*Fpow(i-n,n-i/2)*s[i-n>>1]%mod;
        ans+=1ll*i*(a[i]-a[i-1])%mod;
    }
    printf("%d\n",(ans%mod+mod)*Fpow(s[n>>1],mod-2)%mod);
    return 0;
}

她的字符串

#include<complex>
#include<cstdio>
using namespace std;
const int N=27,M=1e6+7;
int n,ans;
int last[N],num[N],p[N][N],minv[N][N];
char s[M];
int main()
{
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;i++)
    {
        int c=s[i]-'a';
        num[c]++;last[c]=i;
        for(int j=0;j<26;j++)
            if(j!=c && num[j])
                ans=max(ans,max(num[c]-num[j]-minv[c][j]-(last[j]==p[c][j]),num[j]-num[c]-minv[j][c]-(last[j]==p[j][c])));
        for(int j=0;j<26;j++)
        {
            if(num[c]-num[j]<minv[c][j])
            {
                minv[c][j]=num[c]-num[j];
                p[c][j]=i;
            }
            if(num[j]-num[c]<minv[j][c])
            {
                minv[j][c]=num[j]-num[c];
                p[j][c]=i;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

虚幻的十字架

#include<complex>
#include<cstdio>
using namespace std;
const int N=101;
int n,tot;
char s[N][N];
bool vis[N][N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(s[i][j]=='#' && !vis[i][j])
                if(s[i+1][j-1]=='#' && s[i+1][j]=='#' && s[i+1][j+1]=='#' && s[i+2][j]=='#')
                    vis[i+1][j-1]=vis[i+1][j]=vis[i+1][j+1]=vis[i+2][j]=1;
                else
                {
                    printf("NO\n");
                    return 0;
                }
    printf("YES\n");
    return 0;
}

顽皮的她与消失的数字

#include<complex>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+7;
int n,m;
int a[N],b[N];
int qread()
{
    int x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9')ch=getchar();
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        a[i]=qread();
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
        b[i]=qread();
    sort(a+1,a+n+1);sort(b+1,b+m+1);
    int i=1,j=1;
    while(i<=n)
        if(a[i]!=b[j])printf("%d ",a[i++]);
        else i++,j++;
    return 0;
}