“卓见杯”郑州轻工业大学第十五届程序设计大赛暨河南省高校邀请赛

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef double db;
typedef long long ll;
struct cp
{
    db x,y;
    cp(db real=0,db imag=0):x(real),y(imag){};
    cp operator +(cp b)const{return {x+b.x,y+b.y};}
    cp operator -(cp b)const{return {x-b.x,y-b.y};}
    cp operator*(cp b)const{return {x*b.x-y*b.y,x*b.y+y*b.x};}
};
using vcp=vector<cp>;
using Poly=vector<int>;
class Cipolla
{
    int P,I2{};
    using pll=pair<ll,ll>;
};
#define MUL(a,b) (ll(a)*(b)%P)
#define ADD(a,b) (((a)+=(b))>=P?(a)-=P:0)
#define SUB(a,b) (((a)-=(b))<0?9a)+=P:0)
const int P=1e9+7,N=2e5+10;
Poly getINV(int L){

    Poly inv(L);inv[1]=1;
    rep(i,2,L-1)
        inv[i]=MUL((P-P/i),inv[P%i]);return inv;
    }
int POW(ll a,int b=P-2,ll x=1)
{
    for(;b;b>>=1,a=a*a%P)
        if(b&1)x=x*a%P;
    return x;
}
//auto inv=getInv(N);
namespace FFT{
    const db pi=acos(-1);
    
    vcp Omega(int L){
        vcp w(L);w[1]=1;
        for(int i=2;i<L;i<<=1){
            auto w0=w.begin()+i/2,w1=w.begin()+i;
            cp wn(cos(pi/i),sin(pi/i));
            for(int j=0;j<i;j+=2)
            w1[j]=w0[j>>1],w1[j+1]=w1[j]*wn;
        }
        return w ;
    }
    auto W=Omega(1<<19);
    void DIF(cp *a,int n){
        cp x,y;
        for(int k=n>>1;k;k>>=1)
        for(int i=0;i<n;i+=k<<1)
        for(int j=0;j<k;j++)
            x=a[i+j],y=a[i+j+k],a[i+j+k]=(a[i+j]-y)*W[k+j],a[i+j]=x+y;
    }
    void IDIT(cp *a,int n){
        cp x,y;
        for(int k=1;k<n;k<<=1)
        for(int i=0;i<n;i+=k<<1)
            for(int j=0;j<k;j++)
                x=a[i+j],y=a[i+j+k]*W[k+j],a[i+j+k]=x-y,a[i+j]=x+y;
        const db Inv=1. /n;
        rep(i,0,n-1)a[i].x*=Inv,a[i].y*=Inv;
        reverse(a+1,a+n);
    }
}
namespace Polynomial{
    void DFT(vcp &a){FFT::DIF(a.data(),a.size());}
    void IDFT(vcp &a){FFT::IDIT(a.data(),a.size());}
    int norm(int n){return 1<<(__lg(n-1)+1);}
    void norm(Poly &a){if(!a.empty())a.resize(norm(a.size()),0);
    else
    a={0};}
    vcp &dot(vcp &a,vcp &b){rep(i,0,a.size()-1)a[i]=a[i]*b[i];
    return a;}
    
    Poly operator *(ll k,Poly a){
        Poly ans;
        for(auto i:a)
            ans.push_back(k*i);
            return ans;
    }
    Poly operator *(Poly a,Poly b){
        int n=a.size()+b.size()-1;
        vcp c(norm(n));
        rep(i,0,a.size()-1)c[i].x=a[i];
        rep(i,0,b.size()-1)c[i].y=b[i];
        DFT(c),dot(c,c),IDFT(c),a.resize(n);
        rep(i,0,n-1)a[i]=(int)(c[i].y*.5+.5);
        return a;
    }
}
using namespace Polynomial;
char s[N];
int n;

int main()
{
//     freopen("1.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>s+1;
    n=strlen(s+1)+10;
    int m=strlen(s+1);
    Poly vec1(n),vec2(n);
    for(int i=1;i<=m;i++)
    {
        if(s[i]=='(') vec1[m-i]=1;
        else vec2[i]=1;
    }
    Poly ans=vec1*vec2;
//     for(auto x:vec1) cout<<x<<" ";
//     cout<<endl;
//     for(auto x:vec2) cout<<x<<" ";
//     cout<<endl;
//     for(int i=0;i<vec1.size();i++) cout<<vec1[i]<<" ";
//     cout<<endl;
//     for(int i=0;i<vec2.size();i++) cout<<vec2[i]<<" ";
//     cout<<endl;
//     for(auto x: ans) cout<<x<<" ";
//     cout<<endl;
    bool flag=true;
    for(int i=1;i<m;i++)
    {
        if(flag) flag=false;
        else cout<<" ";
        cout<<ans[i+m];
    }
    cout<<endl;
//     cout<<(1<<18)<<endl;
    
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
    int x;scanf("%d",&x);return x;
}
int n,b[200010],ans[20];
vector<int>e[200010],pos[200010],can[20];

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        e[i].push_back(read());
    for(int i=1;i<=n;i++)
    {
        b[i]=read();
        pos[b[i]].push_back(i);
    }
    for(int i=9;i>=0;i--)
    {
        if(pos[i].size())
        {
            ans[1]=i;
            can[1]=pos[i];
            break;
        }
    }
    for(int i=1;i<=8;i++)
    {
        for(auto po:can[i])
        {
            for(auto y:e[po])
                ans[i+1]=max(ans[i+1],b[y]);
        }
        for(auto po:can[i])
        {
            for(auto y:e[po])
                if(b[y]==ans[i+1])
                    can[i+1].push_back(y);
        }
        
        cout<<ans[i];
    }
    cout<<ans[9];        
}

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N=1010;
int f[N][N];
int a[N];
int n,m;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>a[i],a[i]%=n;
    f[1][a[1]]=1;
    for(int i=2;i<=m;i++)
    {
        f[i][a[i]]=1;
        for(int j=0;j<n;j++)
        {
            f[i][(j+a[i])%n]|=f[i-1][j];
            f[i][j]|=f[i-1][j];
        }
    }
//    for(int i=1;i<=m;i++)
//    {
//        for(int j=0;j<n;j++)
//        {
//            cout<<f[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    if(f[m][0]) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    
    return 0;    
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
    int x;scanf("%d",&x);return x;
}
int n;
char s[200010];
int check()
{
    for(int i=0;i<n;i++)
        if(s[i]!='z')
            return 0;
    return 1;
}
int main()
{
    n=read();
    scanf("%s",s);
    if(check())
        printf("No solution");
    else
    {
        s[n-1]++;
        n--;
        while(s[n]=='z'+1)
        {
            s[n]='a';
            n--;
            s[n]++;
        }
        printf("%s",s);
    }
    
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
    int x;scanf("%d",&x);return x;
}
int n,a[100010],b[100010];
ll ans;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        a[read()]=1;
    for(int j=1;j<=n;j++)
        b[read()]=1;
    for(int i=1;i<=100000;i++)
    {
        ll maxa=0,maxb=0;
        for(int j=i;j<=100000;j+=i)
        {
            if(a[j])
                maxa=j;
            if(b[j])
                maxb=j;
        }
        ans=max(ans,maxa*maxb*i);
    }
    cout<<ans;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
    int x;scanf("%d",&x);return x;
}
ll n;
int main()
{
    n=read();        
    cout<<(1+n)*n/2-n+1;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
    int x;scanf("%d",&x);return x;
}
int n,flag[1010],len[1010],ans;
ll f[1010][1010];
string s[1010];
ll B=233,M=1e9+7;
map<ll,int>o;
void work(int i)
{
    f[i][0]=s[i][0];
    for(int j=1;j<len[i];j++)
        f[i][j]=(f[i][j-1]*B+s[i][j])%M;
    
}
int main()
{
//     freopen("1.in","r",stdin);
    cin>>n;
    getline(cin,s[0]);
    for(int i=1;i<=n;i++)
        getline(cin,s[i]);
    for(int i=1;i<=n;i++)
    {
        if(s[i].substr(0,7)=="what's ")
        {
            s[i]=s[i].substr(7,s[i].length()-7);
            flag[i]=1;
            len[i]=s[i].length();
            work(i);
        }
        else
        {
            len[i]=s[i].length();
            work(i);
            int pos=0;
            for(int j=1;j<i;j++)
            {
//                cout<<"??";
                if(flag[j]&&len[i]>=len[j]&&f[j][len[j]-1]==f[i][len[j]-1]&&len[j]>len[pos]&&o[f[j][len[j]-1]]==0)
                    pos=j;
            }
            if(pos!=0)
            {
                ans++;
                flag[pos]=0;
                o[f[pos][len[pos]-1]]=1;
            }
        }
    }
    cout<<ans;
}

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N=6e5+10;
struct node {
    int l,r;
    bool operator<(const node &a) {
        return l<a.l;
    }
}p[N];
ll c[N];
int n,m,k;

void add(int x,int y)
{
    for(;x<=n;x+=x&-x)
    {
        c[x]+=y;
    }
}

ll ask(int x)
{
    ll ans=0;
    for(;x;x-=x&-x)
    {
        ans+=c[x];
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        cin>>p[i].l>>p[i].r;
    }
    sort(p+1,p+m+1);
    int t=1;
    priority_queue<pair<int,int>> q;
    for(int i=1;i<=n;i++)
    {
        while(t<=m&&p[t].l<=i)
        {
            int l=p[t].l;
            int r=p[t].r;
            add(l,1);
            add(r+1,-1);
            q.push({r,l});
            t++;
        }
        int z=ask(i);
        if(z>k)
        {
            while(z>k)
            {
                auto it=q.top();
                q.pop();
                int l=it.second;
                int r=it.first;
                add(l,-1);
                add(r+1,1);
                z--;
            }
        }
    }
//    while(q.size())
//    {
//        cout<<q.top().first<<" "<<q.top().second<<endl;
//        q.pop();
//    }
    cout<<q.size()<<endl;
    
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
    int x;scanf("%d",&x);return x;
}
char x[3][100010],y[3][100010];
int d[10];
int check(int t)
{
    if(strlen(x[t])>6||strlen(y[t])>6)
        return 1;//chu  ba
    ll xx=0,yy=0;
    
    for(int i=x[t][0]=='-'?1:0;i<strlen(x[t]);i++)
        xx=xx*10+x[t][i]-'0';
    for(int i=y[t][0]=='-'?1:0;i<strlen(y[t]);i++)
        yy=yy*10+y[t][i]-'0';
    d[t]=xx*xx+yy*yy;
    return d[t]>1000000;
}
int main()
{
    scanf("%s%s",x[1],y[1]);
    scanf("%s%s",x[2],y[2]);
    if(check(1)&&check(2))
        printf("Draw");
    else if(check(1))
        printf("Bob");
    else if(check(2))
        printf("Alice");
    else
    {
        if(d[1]==d[2])
            printf("Draw");
        else if(d[1]<d[2])
            printf("Alice");
        else
            printf("Bob");
    }
        
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
    int x;scanf("%d",&x);return x;
}
ll n,a[300010],b[300010],sum[300010],m,ni[300010];
ll inv[300010],fac[300010],mod=998244353;

ll t=1,tsum,tt;
ll quick(ll x,ll y)
{
    ll t=1;
    while(y)
    {
        if(y&1)
            t=t*x%mod;
        x=x*x%mod;
        y=y/2;
    }
    return t;
}
ll C(ll b,ll a)
{
    return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
ll work()
{
    ll ans=0;
    for(int i=1;i<=m;i++)
    {
        if(sum[i]>=2)
        {
            tt=(tt-C(2,sum[i])*ni[(sum[i]+1)]%mod*C(2,sum[i])%mod*ni[(sum[i]+1)]%mod)%mod;
            tsum=(tsum-C(2,sum[i])*ni[(sum[i]+1)]%mod)%mod;
            tt=(tt+mod)%mod;
            tsum=(tsum+mod)%mod;
            ans=(ans+C(2,sum[i])*ni[sum[i]+1]%mod*((tsum*tsum%mod-tt)%mod+mod)%mod)%mod;    
            tt=(tt+C(2,sum[i])*ni[(sum[i]+1)]%mod*C(2,sum[i])%mod*ni[(sum[i]+1)]%mod)%mod;
            tsum=(tsum+C(2,sum[i])*ni[(sum[i]+1)]%mod)%mod;
        }
    }
    ans=ans*t%mod*ni[6]%mod;
    return (ans+mod)%mod;
}
int main()
{
    ll ans=0;
//     freopen("1.in","r",stdin);
    n=read();
    for(int i=1;i<=n;i++)
        b[i]=a[i]=read();
    sort(b+1,b+1+n);
    m=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++)
        sum[lower_bound(b+1,b+1+m,a[i])-b]++;
    fac[0]=inv[0]=1;
    for(int i=1;i<=200010;i++)
        fac[i]=fac[i-1]*i%mod;
    inv[200010]=quick(fac[200010],mod-2);
    for(int i=200010;i>=1;i--)
        inv[i-1]=inv[i]*i%mod;
    for(int i=1;i<=200010;i++)
        ni[i]=quick(i,mod-2);
    for(int i=1;i<=m;i++)
        t=t*(sum[i]+1)%mod;
    for(int i=1;i<=m;i++)
        if(sum[i]>=2)
            tsum=(tsum+C(2,sum[i])*ni[(sum[i]+1)]%mod)%mod;
    for(int i=1;i<=m;i++)
        if(sum[i]>=2)
            tt=(tt+C(2,sum[i])*ni[(sum[i]+1)]%mod*C(2,sum[i])%mod*ni[(sum[i]+1)]%mod)%mod;    
    ans=(ans+t*(tsum*tsum%mod-tt)%mod)%mod;
    ans=(ans+mod)%mod;
    ans=ans*ni[2]%mod;
    
    for(int i=1;i<=m;i++)
        if(sum[i]>=2)
            ans=(ans+C(2,sum[i])*ni[(sum[i]+1)]%mod*t%mod)%mod;
    ans=(ans+t-1)%mod;
    for(int i=1;i<=m;i++)
        if(sum[i]>=3)
            ans=(ans+C(3,sum[i])*t%mod*ni[sum[i]+1]%mod)%mod;
    ans=ans+work();
    cout<<ans%mod<<endl;
}