JZTXT

The 1st Universal Cup. Stage 12: Ōokayama

发布时间 2023-04-21 19:50:26作者: sz[sz]

G

容斥完之后发现要求一个m次多项式的n次方，并且得到\(n\times m\)项。
原本很sb地直接套了个多项式LnExp上去（即使知道大概率过不了），然后狂TLE。。。
其实但凡从常数的角度分析，Exp的常数有14倍，已经比\(log(m)\)大了，所以不如写快速幂，然后写着就会发现卷积的长度总和其实是\((n\times m),(n\times m)/2,...=O(n\times m)\)的，就随便过了。
当时不管常数还是效率都没认真分析，就直接按着常规方法套板子，而忽视了具体题目的数据范围特性，就卡了很久，很不应该！

点击查看代码 
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N=(1<<23)+5,P=998244353,G[2]={3,(P+1)/3};
void inc(int& x,int y){
    x+=y;
    if(x>=P) x-=P;
    if(x<0) x+=P;
}
int sum(int x,int y){
    x+=y;
    if(x>=P) x-=P;
    if(x<0) x+=P;
    return x;
}
void mul(int& x,int y){
    x=1ll*x*y%P;
}
int prd(int x,int y){
    return 1ll*x*y%P;
}
inline int fpw(int a,int x){
    int s=1;
    for(;x;x>>=1,a=1ll*a*a%P) if(x&1) s=1ll*s*a%P;
    return s;
}
int rv[N],gp[2][N],iv[N],fc[N],fv[N];
void init(int n){
    fc[0]=1;
    for(int i=1;i<n;i++) iv[i]=fpw(i,P-2),fc[i]=1ll*fc[i-1]*i%P;
    fv[n-1]=fpw(fc[n-1],P-2);
    for(int i=n-2;~i;i--) fv[i]=1ll*fv[i+1]*(i+1)%P;
    for(int p=0;p<2;p++){
        for(int i=1;i<n;i<<=1){
            gp[p][i]=1;
            int t=fpw(G[p],(P-1)/(i<<1));
            for(int j=i+1;j<(i<<1);j++) gp[p][j]=1ll*gp[p][j-1]*t%P;
        }
    }
}
int Cmb(int n,int m){
    return 1ll*fc[n]*fv[m]%P*fv[n-m]%P;
}
inline void dft(int* a,int n,int p){
    for(int i=0;i<n;i++) if(i<rv[i]) swap(a[i],a[rv[i]]);
    for(int i=1;i<n;i<<=1){
        for(int j=0;j<n;j+=(i<<1)){
            for(int k=0;k<i;k++){
                int &A=a[i+j+k],&B=a[j+k],t=1ll*gp[p][i+k]*A%P;
                A=B-t; if(A<0) A+=P;
                B=B+t; if(B>=P) B-=P;
            }
        }
    }
    if(p) for(int i=0;i<n;i++) a[i]=1ll*a[i]*iv[n]%P;
}
inline int Rev(int m){
    int p=0,n=1;
    while(n<m) n<<=1,p++;
    for(int i=0;i<n;i++) rv[i]=(rv[i>>1]>>1)|((i&1)<<(p-1));
    return n;
}
inline void poly_mul(int m,int* A,int* B,int* C){
    int n=Rev(m);
    dft(A,n,0); dft(B,n,0);
    for(int i=0;i<n;i++) C[i]=1ll*A[i]*B[i]%P;
    dft(C,n,1);
    fill(C+m,C+n,0);
}
void print(char name[],int n,int* a){
    printf("%s n=%d\n",name,n);
    for(int i=0;i<n;i++) cout<<a[i]<<" "; puts("");
}
int n,m,A[N],g[N],f[N];
int main() {
    cin>>n>>m;
    init(1<<22);
    for(int i=0;i<=m;i++){
        A[i]=prd(Cmb(m,i),prd(fc[m],fv[m-i]));
    }

    f[0]=1;
    //print("A",n*m+1,A);
    int x=n;
    int len=m+1,sum=1;
    for(;x;x>>=1){
        if(x&1){
            for(int i=0;i<len;i++) g[i]=A[i];
            sum+=len;
            poly_mul(sum,f,g,f);
            for(int i=0;i<(sum<<1);i++) g[i]=0;
            //print("f",len,f);
        }
        len<<=1;
        int nn=Rev(len );
        dft(A,nn,0);
        for(int i=0;i<nn;i++) A[i]=1ll*A[i]*A[i]%P;
        dft(A,nn,1);
        fill(A+len,A+nn,0);
        //print("A",len<<1,A);
    }
    //puts("");
    //print("f",n*m+1,f);
    int ans=0;
    for(int i=0;i<=n*m;i++){
        int s=prd(f[i],fc[n*m-i]);
        // cout<<i<<" "<<f[i]<<" "<<s<<endl;
        if(i&1) inc(ans,P-s);
        else inc(ans,s);
    }
    cout<<ans<<endl;
    return 0;
}

J

当时只发现它是个单峰的，枚举最小值及其位置之后可以判断，然后就一直陷在优化这个枚举判断的过程，发现不可做。
但这式子就是凸性的定义呀！甚至题目都把凸写上去了。。。发现这个之后就对右端点求个下凸壳，然后判断即可。
感觉是经典的，做法已经写在体面上了，然后还想偏，对自己很无语

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=6e5+5;
const ll inf=1e12,P=998244353,V=(P+1)/2;
int n;
ll l[N],r[N];
struct vec{
    ll x,y;
    vec operator - (const vec& u){
        return (vec){x-u.x,y-u.y};
    }
    friend ll cross (vec a,vec b){
        return a.x*b.y-a.y*b.x;
    }
    void print(){
        printf("x=%lld y=%lld\n",x,y);
    }
};
vec q[N];
int t2;
void workR(){
    for(int i=1;i<=n;i++){
        scanf("%lld",&r[i]);
        vec u=(vec){i,r[i]};
        while(t2>1 && cross(q[t2]-q[t2-1],u-q[t2-1])<=0) t2--;
        q[++t2]=u;
    }
}
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lld",&l[i]);
    workR();
    for(int i=1,j=0;i<=n;i++){
        if(j<t2 && i==q[j+1].x){
            j++;
            if(l[i]>q[j].y){
                puts("No");
                return 0;
            }
            continue;
        }
        vec u=(vec){i,l[i]};
        if(cross(u-q[j],q[j+1]-q[j])<0){
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    return 0;
}

K

这个题做法其实挺显然的，考虑枚举d，把区间平移一下，首项的方案数就是各个区间交的长度，所以要求的就是R最小与L最大，然后发现这两者肯定是分别根据d分成至多n段，每段由一个位置的值决定（和斜率优化类似），然后就把d分为分成\(O(n)\)个区间，每段里数一数就好。

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=6e5+5;
const ll inf=1e12,P=998244353,V=(P+1)/2;
int n;
ll l[N],r[N];
struct vec{
    ll x,y;
    vec operator - (const vec& u){
        return (vec){x-u.x,y-u.y};
    }
    friend ll cross (vec a,vec b){
        return a.x*b.y-a.y*b.x;
    }
    void print(){
        printf("x=%lld y=%lld\n",x,y);
    }
};
struct node{
    ll l,r;
    int d;
    void print(){
        printf("l=%lld r=%lld d=%d\n",l,r,d);
    }
}a[N],b[N];
int t1,t2;
vec q[N];
ll floor(vec u){
    if(u.y==0) return 0;
    if(u.x<0) u.x=-u.x,u.y=-u.y;
    if(u.y>0) return u.y/u.x;
    return -((-u.y-1)/u.x+1);
}
ll up(vec u){
    if(u.y==0) return 0;
    if(u.x<0) u.x=-u.x,u.y=-u.y;
    if(u.y>0) return (u.y-1)/u.x+1;
    return -((-u.y)/u.x);
}
void workL(){
    for(int i=1;i<=n;i++){
        scanf("%lld",&l[i]);
        vec u=(vec){i,l[i]};
        while(t1>1 && cross(q[t1]-q[t1-1],u-q[t1-1])>=0) t1--;
        q[++t1]=u;
    }
    a[t1+1].r=-inf-1;
    for(int i=t1;i;i--){
        //cout<<"i="<<i<<endl;
        //q[i].print();
        a[i].l=a[i+1].r+1;
        if(i==1) a[i].r=inf;
        else{
            vec u=(vec){q[i-1].x-q[i].x,q[i-1].y-q[i].y};
            a[i].r=floor(u);
        }
        a[i].d=q[i].x;
    }
    reverse(a+1,a+t1+1);
    //for(int i=1;i<=t1;i++) a[i].print();
}
void workR(){
    for(int i=1;i<=n;i++){
        scanf("%lld",&r[i]);
        vec u=(vec){i,r[i]};
        while(t2>1 && cross(q[t2]-q[t2-1],u-q[t2-1])<=0) t2--;
        q[++t2]=u;
    }
    b[0].r=-inf-1;
    for(int i=1;i<=t2;i++){
        b[i].l=b[i-1].r+1;
        if(i==t2) b[i].r=inf;
        else{
            vec u=(vec){q[i+1].x-q[i].x,q[i+1].y-q[i].y};
            b[i].r=floor(u);
        }
        b[i].d=q[i].x;
    }
    //for(int i=1;i<=t2;i++) b[i].print();
}
ll cnt(ll L,ll R){
    return (L+R)%P*((R-L+1)%P)%P*V%P;
}
ll mod(ll x){
    return (x%P+P)%P;
}
ll cal(vec u,ll L,ll R){
    u.x=mod(u.x); u.y=mod(u.y);
    if(L>R) return 0;
    return ((R-L+1)%P*((u.y+1)%P)%P+P-u.x*cnt(L,R)%P)%P;
}
int main() {
    cin>>n;
    workL(); workR();
    ll ans=0;
    for(int i=1,j=1;i<=t1;i++){
        if(b[j].r<a[i].l && j<=t2) j++;
        while(b[j].l<=a[i].r && j<=t2){
            //cout<<"i="<<i<<" j="<<j<<endl;
            ll L=max(a[i].l,b[j].l),R=min(a[i].r,b[j].r);
            //cout<<"L="<<L<<" R="<<R<<endl;
            vec u=(vec){b[j].d-a[i].d,-l[a[i].d]+r[b[j].d]};
            //u.print();
            if(!u.x){
                if(u.y>=0) (ans+=cal(u,L,R))%=P;
            }
            else{
                if(u.x>0) R=min(R,floor(u));
                else L=max(L,up(u));
                (ans+=cal(u,L,R))%=P;
            }
            j++;
        }
        j--;
    }
    cout<<ans<<endl;
    //cout<<inf%P*(inf%P)%P<<endl;
    return 0;
}

M

缩完点之后是一个DAG最小链覆盖，但链是可以相交的，之前网上的做法都是暴力\(O(n^2)\)建图，但这题可能就是为了卡这个的。然后优化的做法其实也比较常规：拆点后每个点向对应的点连容量inf的边，再把原来\(u->v\)的容量改成inf，这样就相当于：原图中可达，就可以跑出一个流；并且有源点汇点边的流量限制，所以是正确的。
然后有点麻烦的事输出方案，就按着反向边dfs一个个流去找即可。

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,inf=1e9;
vector<int> a[N];
stack<int> stk;
bool vis[N],instk[N];
int dfn[N],low[N],col[N],w[N]; // co:染色结果，w:点权
vector<int> sz; // sz:第i个颜色的点数
int n,m,dcnt;//
void dfs(int x){ // Tarjan求强联通分量
    vis[x]=instk[x]=1; stk.push(x);
    dfn[x]=low[x]=++dcnt;
    for(auto p:a[x]){
        if(!vis[p])dfs(p);
        if(instk[p])low[x]=min(low[x],low[p]);
    }
    if(low[x]==dfn[x]){
        int t; sz.push_back(0); // 记录
        do{
            t=stk.top();
            stk.pop();
            instk[t]=0;
            sz.back()+=w[t]; // 记录
            col[t]=sz.size(); // 染色
        }while(t!=x);
    }
}
void getscc(){
    fill(vis,vis+n,0);
    sz.clear();
    for(int i=1;i<=n;i++) if(!vis[i])dfs(i);
}
struct pii{
    int u,v;
};
void shrink(){ // 缩点，在a里重构
    vector<pii> tmp;
    getscc();
    for(int i=1;i<=n;i++) {
        for (auto j: a[i]) if (col[i] != col[j]) {
                pii u = {col[i], col[j]};
                tmp.push_back(u);
            }
    }
    n=sz.size();
    for(int i=1;i<=n;i++){
        a[i].clear();
        w[i]=sz[i];
    }
    for(auto i:tmp){
        a[i.u].push_back(i.v);
    }
}
int fa[N];
int find(int u){
    if(u==fa[u]) return u;
    return fa[u]=find(fa[u]);
}
struct FLOW{
    struct edge{int to,w,nxt;};
    vector<edge> a; int head[N],cur[N];
    int n,s,t;
    queue<int> q; bool inque[N];
    int dep[N];
    void ae(int x,int y,int w){ // add edge
        //cout<<"ae:"<<x<<" "<<y<<" "<<w<<endl;
        a.push_back({y,w,head[x]});
        head[x]=a.size()-1;
    }
    bool bfs(){ // get dep[]
        fill(dep,dep+n,inf); dep[s]=0;
        copy(head,head+n,cur);
        q=queue<int>(); q.push(s);
        while(!q.empty()){
            int x=q.front(); q.pop(); inque[x]=0;
            for(int i=head[x];i!=-1;i=a[i].nxt){
                int p=a[i].to;
                if(dep[p]>dep[x]+1 && a[i].w){
                    dep[p]=dep[x]+1;
                    if(inque[p]==0){
                        inque[p]=1;
                        q.push(p);
                    }
                }
            }
        }
        return dep[t]!=inf;
    }
    int dfs(int x,int flow){ // extend
        int now,ans=0;
        if(x==t)return flow;
        for(int &i=cur[x];i!=-1;i=a[i].nxt){
            int p=a[i].to;
            if(a[i].w && dep[p]==dep[x]+1)
                if((now=dfs(p,min(flow,a[i].w)))){
                    a[i].w-=now;
                    a[i^1].w+=now;
                    ans+=now,flow-=now;
                    if(flow==0)break;
                }
        }
        return ans;
    }
    bool is[N];
    void init(int _n){
        n=_n+1; a.clear();
        fill(head,head+n,-1);
        fill(inque,inque+n,0);
        fill(is,is+n,0);
    }
    int solve(int _s,int _t,int _n){ // return max flow
        s=_s,t=_t;
        int ans=0;
        while(bfs()) ans+=dfs(s,inf);
        for(int e=head[s];e>=0;e=a[e].nxt) if(a[e^1].w) is[a[e].to]=1;
        for(int e=head[t];e>=0;e=a[e].nxt) if(a[e].w){
            int v=a[e].to,u=v;
            while(1){
                if(u>=1 && u<=_n && is[u]){
                    is[u]=0;
                    break;
                }
                int w=0,tmp=0;
                for(int i=head[u];i>=0;i=a[i].nxt) if(i&1 && a[i].w){
                    w=a[i].to;
                    tmp=i;
                    break;
                }
                if(!w) break;
                a[tmp].w--;
                u=w;
            }
            //cout<<u<<" "<<v-_n<<endl;
           // fa[find(u)]=find(v-_n);
        }
        return ans;
    }
}flow;
void add(int x,int y,int w){flow.ae(x,y,w),flow.ae(y,x,0);}
// 先flow.init(n)，再add添边，最后flow.solve(s,t)
int ans[N];
int main(){
    cin>>n>>m;
    for(int u,v,i=1;i<=m;i++) scanf("%d%d",&u,&v),a[u].push_back(v);
    int tot=n;
    shrink();
    //for(int i=1;i<=tot;i++) cout<<col[i]<<" "; puts("");
    int S=0,T=n+n+1;
    flow.init(T+1);
    for(int i=1;i<=n;i++){
        //cout<<"i="<<i<<endl;
        add(S,i,1);
        add(i+n,T,1);
        add(i+n,i,inf);
        for(auto j:a[i]) add(i,j+n,inf);
    }
    for(int i=1;i<=n;i++) fa[i]=i;
    flow.solve(S,T,n);
    int cnt=0;
    for(int i=1;i<=tot;i++){
        int u=find(col[i]);
        if(!ans[u]) ans[u]=++cnt;
       // cout<<col[i]<<" u="<<u<<endl;
        printf("%d ",ans[u]);
    }
    puts("");
    return 0;
}