[Nowcoder Multi Univerisity Training 2J]Subarray

Solution

可能作为区间端点的点个数最多为3e7
f[i]表示以第i个区间右端点为答案右端点的最大区间和
g[i]表示以第i个区间左端点为答案左端点的最大区间和
f[i]=\max(0,f[i−1]−(l[i]−r[i−1]−1))+r[i]−l[i]+1
g[i]=\max(0,g[i+1]−(l[i+1]−r[i]−1))+r[i]−l[i]+1
如果f[i]+g[i+1]≥l[i+1]−r[i]−1,说明答案的左右端点可以跨越[r[i]+1,l[i+1]−1],那么把这些合并考虑
搞完上面,问题就变成了给你若干个长度和不超过3e7的(1,−1)序列,问有多少区间和大于1
然后就好做了

[HDU6371]Chopping hands

Link

Solution

在有序表里删除点可以方便地维护中位数,所以初始全部插入然后DFS枚举删除哪些。

先按照pack大小排序可以强力加速。

然而HDOJ太慢还是T了。

然后spice的参数顺序!
a.splice(iter_a,b,iter_b)是把ba里搞!

Code

const int XN=30,XM=211;

std::vector<int> pack[XN];

int w[XM][XM],c[XN],n;
long long Ans,succs[XN],cost;

std::list<int> a,temp;
std::vector<std::list<int>::iterator> it[XM];
std::pair<std::list<int>::iterator,int> med;
std::vector<std::pair<int,std::pair<int,int>>> nums;

int cnt[XM];

int ord[XN];

void DFS(int p=1) {
    //std::cerr<<p<<','<<cost<<'\n';
    if(nums[a.back()].first*2-(cost+succs[p])<Ans)
        return;
    if(p==n+1)
        Enlarge(Ans,(a.size()&1?2*nums[(*med.first)].first
                    :nums[(*med.first)].first+nums[(*std::next(med.first))].first)-cost);
    else {
        cost+=c[ord[p]];
        DFS(p+1);
        cost-=c[ord[p]];
        if(!(p==n && cost==0)) {
            static std::pair<int,std::list<int>::iterator> stack[XM];
            static int top;
            auto backup=med;
            int pre=top;
            for(auto x : pack[ord[p]]) {
                stack[++top]={x,std::next(it[x][cnt[x]])};
                if(*it[x][cnt[x]]<*med.first)
                    med.second--;
                else if(*it[x][cnt[x]]==*med.first)
                    med.first++;
                temp.splice(temp.end(),a,it[x][cnt[x]--]);
                while(med.second<(int)(a.size()+1)/2) {
                    ++med.first;
                    ++med.second;
                }
                while(med.second>(int)(a.size()+1)/2) {
                    --med.first;
                    --med.second;
                }
            }
            DFS(p+1);
            med=backup;
            for(;top!=pre;top--)
                a.splice(stack[top].second,temp,it[stack[top].first][++cnt[stack[top].first]]);
        }
    }
}

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--) {
        //std::cerr<<T<<'\n';
        int m;std::cin>>n>>m;
        for(int i=1;i<=n;++i)
            std::cin>>c[i];
        for(int i=1;i<=m;++i)
            cnt[i]=0;
        for(int i=1;i<=n;++i) {
            int k;std::cin>>k;
            pack[i].resize(k);
            for(int j=0;j<k;++j) {
                std::cin>>pack[i][j];
                cnt[pack[i][j]]++;
            }
            ord[i]=i;
        }
        std::sort(ord+1,ord+1+n,[&](int x,int y)->bool {
            return pack[x].size()>pack[y].size();
        });
        succs[n+1]=0;
        for(int i=n;i>=1;--i)
            succs[i]=succs[i+1]+std::min(0,c[ord[i]]);
        a.clear();
        nums.clear();
        for(int i=1;i<=m;++i) {
            int k;std::cin>>k;
            it[i].resize(k+1);
            for(int j=1;j<=k;++j) {
                std::cin>>w[i][j];
                nums.push_back({w[i][j],{i,j}});
            }
        }
        std::sort(nums.begin(),nums.end());
        for(auto &p : nums)
            it[p.second.first][p.second.second]=a.insert(a.end(),a.size());

        med.first=a.begin();
        std::advance(med.first,(med.second=(a.size()+1)/2)-1);

        Ans=-1e18;
        cost=0;
        DFS();
        assert(temp.empty());
        std::cout<<Ans<<'\n';
    }
    return 0;
}

[Nowcoder Multi Univerisity Training 1C]Euclidean Distance

Link

Solution

(令x_i=\frac {a_i}m
{\displaystyle {\mathcal {L}}}=\sum (p_i-x_i)^2+\lambda(\sum p_i-1),即为求\max_\lambda\ \min_{p}\ {\displaystyle {\mathcal {L}}}(p_i\ge 0)

{\displaystyle {\mathcal {L}}}=\sum (p_i-(x_i-\lambda))^2+\sum(2x_i\lambda-\lambda^2)+2\lambda,对于每个(p_i-(x_i-\lambda))^2\ge \min(x_i-\lambda,0)^2,可以缩掉p_i了。
然后就是求\sum\min(x_i-\lambda,0)^2+\sum(2x_i\lambda-\lambda^2)-2\lambda的最大值。

Code

const int XN=1e4+11,INF=1e9;

struct Fact {
    long long p,q;

    Fact(long long x,long long y=1) {
        long long d=std::__gcd(x,y);
        p=x/d;q=y/d;
        if(q<0) {
            p=-p;
            q=-q;
        }
    }
};

bool operator <(Fact x,Fact y) {
    return __int128(x.p)*y.q-__int128(x.q)*y.p<0;
}

Fact operator -(Fact x) {
    return {-x.p,x.q};
}

Fact operator +(Fact x,Fact y) {
    return Fact({x.p*y.q+x.q*y.p,x.q*y.q});
}


Fact operator *(Fact x,Fact y) {
    return Fact({x.p*y.p,x.q*y.q});
}

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,m;
    while(std::cin>>n>>m) {
        static int a[XN];
        for(int i=1;i<=n;++i)
            std::cin>>a[i];
        std::sort(a+1,a+1+n); 
        a[0]=-INF;
        a[n+1]=INF;
        long long A=-n;
        Fact B={-2,1},C={0,1};
        for(int i=1;i<=n;++i)
            B=B+Fact(2*a[i],m);
        Fact Ans{0,1};

        auto Solve=[&](Fact L,Fact R)->Fact {
            if(A==0)
                return B*(B.p*B.q>=0?R:L)+C;
            Fact axis=-1*B*Fact(1,2*A);
            if(!(axis<L) && !(R<axis)) {
                return (4*A*C+(-B*B))*Fact(1,4*A);  
            } else {
                Fact X=axis<L?L:R;
                return A*X*X+B*X+C; 
            }
        };

        for(int i=1;i<=n+1;++i) {
            Enlarge(Ans,Solve({a[i-1],m},{a[i],m}));
            if(i!=n+1) {
                A++;
                B=B+(-2*Fact(a[i],m));
                C=C+1ll*a[i]*a[i]*Fact(1,1ll*m*m);
            }
        }
        if(Ans.q==1)
            std::cout<<Ans.p<<'\n';
        else
            std::cout<<Ans.p<<'/'<<Ans.q<<'\n';
    }
    return 0;
}

拉格朗日乘数法

标准形式

\begin{aligned}
\text{minimize\ } &f\\
\text{s.t.\ }&g=0
\end{aligned}

等价于

\text{minimize\ } f+\lambda g

不等式形式

\begin{aligned}
\text{minimize\ } &f\\
\text{s.t.\ }g\le 0
\end{aligned}

等价于

\begin{aligned}
\text{minimize}_x\ \text{maximize}_\lambda
\ &f+\lambda g\\
\text{s.t.\ }&\lambda\ge 0
\end{aligned}

对偶为

\begin{aligned}
\text{maximize}_\lambda
\ \text{minimize}_x\ &f+\lambda g\\
\text{s.t.\ }&\lambda\ge 0
\end{aligned}

[HDU6364]Ringland

Link

读入卡的相当死。。

Code

const int XN=5e5+11;

void Work() {
    int n,l;fin>>n>>l;
    static int a[XN*3],b[XN];
    static long long sum[XN*3];
    for(int i=1;i<=n;++i) {
        fin>>a[i+n];
        a[i]=a[i+n]-l;
        a[i+2*n]=a[i+n]+l;
    }
    for(int i=1;i<=n;++i)
        fin>>b[i];
    for(int i=1;i<=3*n;++i)
        sum[i]=0;

    for(int i=1,j=1;i<=3*n;++i) {
        while(j<=std::min(n,i) && b[j]<=a[i])
            ++j;
        sum[std::max(1,i-n+1)]-=a[i];
        sum[i-j+2]+=2ll*a[i];
        sum[i+1]-=a[i];
    }

    for(int i=1,j=1;i<=n;++i) {
        sum[1]+=b[i];
        while(j<=3*n && a[j]<b[i])
            ++j;
        sum[j-i+1]-=2*b[i];
    }
    long long Ans=1e18;
    for(int i=1;i<=2*n+1;++i)
        Reduce(Ans,sum[i]+=sum[i-1]);
    printf("%lld\n",Ans);
}

int main() {
    //freopen("input","r",stdin);
    int T;fin>>T;
    while(T--)
        Work();
    return 0;
}

[HDU6368]Variance-MST

Link

Solution

题解说的很清楚了。。
核心就是如果直接删掉环上最小边再加上最大边,不能保证修改的这两条边的均值是递增的,即a < b < c < d可能有\frac {a+d}2 < \frac {b+c}2,因此必须把所有成环的边记录一下,按照两条边的均值排序后再按顺序进行删边加边操作。

Code

#include <bits/stdc++.h>

const int XN=1e5+11,XM=2e5+11,P=998244353,INF=1e9;

int Pow(long long base,int v) {
    long long res;
    for(res=1;v;v>>=1,(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

struct Edge {
    int x,y,v,id;
}edges[XM];

struct LinkCutTrees {
    struct Node {
        Node *son[2],*fa;
        bool rev;

        std::pair<int,Edge*> v,min;

        Node(void*):rev(0),min(INF,0) {
            son[0]=son[1]=fa=0;
        }

        Node(std::pair<int,Edge*> const &v):rev(0),v(v),min(v) {
            son[0]=son[1]=fa=null;
        }

        void *operator new(size_t flag) {
            static Node *pool=(Node*)malloc((XN+XM)*sizeof(Node)),*mem=pool++;
            return flag?mem++:mem=pool;
        }

        int Type() {
            return fa->son[1]==this;
        }

        bool isRoot() {
            return fa->son[0]!=this && fa->son[1]!=this;
        }

        void Adopt(Node *s,int d) {
            son[d]=s;
            if(s!=null)
                s->fa=this;
        }

        void Reverse() {
            rev^=1;
            std::swap(son[0],son[1]);
        }

        void Up() {
            min=std::min(std::min(son[0]->min,son[1]->min),v);
        }

        void Down() {
            if(rev) {
                if(son[0]!=null)
                    son[0]->Reverse();
                if(son[1]!=null)
                    son[1]->Reverse();
                rev=0;
            }
        }

    };

    std::vector<Node*> node;

    static Node *null;

    LinkCutTrees():node{0} {}

    void Link(int id1,int id2) {
        Link(node[id1],node[id2]);
    }

    void Cut(int id1,int id2) {
        Cut(node[id1],node[id2]);
    }

    void Add(std::pair<int,Edge*> const &x) {
        node.push_back(new Node(x));
        if(x.second)
            x.second->id=node.size()-1;
    }

    std::pair<int,Edge*> Query(int x,int y) {
        MakeRoot(node[x]);
        Expose(node[y]);
        return node[y]->min;
    }

    Node *FindRoot(int x) {
        return FindRoot(node[x]);
    }


    static void Trans(Node *pos) {
        Node *f=pos->fa,*g=f->fa;
        f->Down();pos->Down();
        int d=pos->Type();
        if(!f->isRoot())
            g->son[f->Type()]=pos;
        pos->fa=g;
        f->Adopt(pos->son[!d],d);f->Up();
        pos->Adopt(f,!d);
    }

    static void Splay(Node *pos) {
        pos->Down();
        for(Node *fa;!pos->isRoot();Trans(pos))
            if(!(fa=pos->fa)->isRoot())
                Trans(pos->Type()==fa->Type()?fa:pos);
        pos->Up();
    }

    static void Access(Node *pos) {
        for(Node *pred=null;pos!=null;pred=pos,pos=pos->fa) {
            Splay(pos);
            pos->son[1]=pred;
            pos->Up();
        }
    }

    static void Expose(Node *pos) {
        Access(pos);
        Splay(pos);
    }

    static Node *FindRoot(Node *pos) {
        Expose(pos);
        while(pos->son[0]!=null) {
            pos->Down();
            pos=pos->son[0];
        }
        //std::cerr<<std::find(node.begin(),node.end(),pos)-node.begin()<<'\n';
        return pos;
    }

    static void MakeRoot(Node *pos) {
        Expose(pos);
        pos->Reverse();
    }

    static void Cut(Node *p1,Node *p2) {
        MakeRoot(p1);
        Expose(p2);
        assert(p2->son[0]==p1);
        p2->son[0]=p1->fa=null;
        p2->Up();
    }

    static void Link(Node *p1,Node *p2) {
        MakeRoot(p1);
        p1->fa=p2;
    }
};

LinkCutTrees::Node *LinkCutTrees::null=new LinkCutTrees::Node((void*)0);

void Work() {
    LinkCutTrees::Node::operator new(0);
    LinkCutTrees lct;
    int n,m;std::cin>>n>>m;
    for(int i=1;i<=n;++i)
        lct.Add({INF,0});
    for(int i=1;i<=m;++i)
        std::cin>>edges[i].x>>edges[i].y>>edges[i].v;

    std::sort(edges+1,edges+1+m,[](Edge const &a,Edge const &b)->bool {
        return a.v<b.v;
    });

    for(int i=1;i<=m;++i)
        lct.Add({edges[i].v,edges+i});//指针会变!
    std::vector<std::tuple<int,int,int>> tg;//维护所有切换 0 时间 1 系数 2 delta
    for(int i=1;i<=m;++i) {
        int x=edges[i].x,y=edges[i].y,v=edges[i].v,id=edges[i].id;
        if(lct.FindRoot(x)==lct.FindRoot(y)) {
            auto me=lct.Query(x,y);
            lct.Cut(me.second->x,me.second->id);
            lct.Cut(me.second->y,me.second->id);
            tg.emplace_back(me.first+v,-1,me.first);
            tg.emplace_back(me.first+v,1,v);
        } else
            tg.emplace_back(-INF,1,v);
        lct.Link(x,id);
        lct.Link(y,id);
    }

    std::sort(tg.begin(),tg.end());
    //E(X^2)-E^2(x)
    std::pair<long long,long long> optm={(long long)1e18,0ll},cur{0ll,0ll};
    int cnt=0;
    for(auto &tgs : tg) {
        int t,op,d;
        std::tie(t,op,d)=tgs;

        cur.first+=1ll*op*d*d;
        cur.second+=op*d;

        auto X=[&](std::pair<long long,long long> const &x)->__int128 {//long long,int??
            return __int128(x.first)*(n-1)-__int128(x.second)*x.second;
        };
        if((cnt+=op)==n-1 && X(optm)>X(cur)) {
            optm=cur;
        }
    }
    int inv=Pow(n-1,P-2),a=optm.first%P*inv%P,b=optm.second%P*inv%P,
        Ans=(a-1ll*b*b%P)%P;
    if(Ans<0)
        Ans+=P;
    std::cout<<Ans<<'\n';
}

int main() {
    //freopen("in","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

[HDU6372]Lucas

Link

Solution

根据Lucas Theorem,\binom{n}{m}\mod p=0\Leftrightarrow np进制表示的每一位都\ge mp进制表示的对应位。
对于题目中的np进制数字iHMBB[i][j]=1j的个数就是满足如上条件的j的个数,HMBB的一次方中的1的个数就是p^n-1\ge i\ge j(i,j)数(此处的\ge指每位对应\ge
同理,HMBB^k1的个数就是p^n-1\ge a_1\ge a_2\ge…\ge a_{k+1}的个数。
而每一位是独立的,可以单独计算一位的然后求个幂。
而一位的答案就是以p-1为开头,长度为k+2的不升序列的长度。用组合数计算,可以假设开头再放上一个0,那么就是开头为0,结尾p-1,中间k+1个数的非降序列数。除去开头,后面k+2个数每个数字相对于前面的数字的增量\ge 0,且总的增量为p-1,因此对于增量列出方程

\left\{\begin{aligned}
\sum \Delta_i=&p-1\\
\Delta_i \ge&0
\end{aligned}\right.

方案数为\binom{(p-1)+(k+1)}{k+1}
最终要计算的就是

\begin{aligned}
&\sum_{i=1}^{k}\sum_{j=1}^n \binom{p+i}{i+1}^j
\end{aligned}

Code

#include <bits/stdc++.h>

const int N=2e6,XN=N+11,P=1e9+7;

void M(int &x) {
    ((x>=P) && (x-=P)) || ((x<0) && (x+=P));
}

int Pow(long long base,int v,int P) {
    long long res=1;
    for(;v;v>>=1,(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

int prime[XN],pcnt;
void Prep() {
    static bool notPrime[XN];
    for(int i=2;i<=N;++i) {
        if(!notPrime[i]) {
            prime[++pcnt]=i;
        }
        for(int j=1;j<=pcnt && i*prime[j]<=N;++j) {
            notPrime[i*prime[j]]=1;
            if(i%prime[j]==0) {
                break;
            } 
        }
    }
}

int fact[XN],ifact[XN];
int C(int n,int m) {
    return n>=m?1ll*fact[n]*ifact[m]%P*ifact[n-m]%P:0;
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);std::cout.tie(0);

//  freopen("input","r",stdin);

    fact[0]=1;
    for(int i=1;i<=N;++i)
        fact[i]=1ll*fact[i-1]*i%P;
    ifact[N]=Pow(fact[N],P-2,P);
    for(int i=N-1;i>=0;--i)
        ifact[i]=1ll*ifact[i+1]*(i+1)%P;

    Prep();
    int T;std::cin>>T;
    while(T--) {
        int c,n,k;std::cin>>c>>n>>k;
        int p=prime[c];
        int Ans=0;
        for(int i=1;i<=k;++i) {
            int v=C(p+i,i+1);
            M(Ans+=v==1?v*n%P:1ll*v*(1ll-Pow(v,n,P))%P*Pow(1-v,P-2,P)%P);
        }
        std::cout<<Ans<<'\n';
    }
    return 0;
}

[Gym 102114C]Call It What You Want

Link

给的\Phi_d的复数形式的公式是骗人玩的…很好我又被骗了…

Solution

x^n-1=\prod_{d|n}\Phi_d(x)\Leftrightarrow \Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(\frac nd)}
\Phi_d(x)的最高次项为\varphi(d),所以在模x^{\varphi(d)+1}下求出\Phi_n(x)然后再求答案,单次询问的复杂度为\mathcal{O}(\sum_{d | n}{2^{\omega(d)}\varphi(d)}) = \mathcal{O}(2^6 n)

Code

#include <bits/stdc++.h>

const int N=1e5,XN=N+11;

int prime[XN],pcnt,phi[XN];
std::vector<int> pdv[XN];

void Prep() {
    static bool notPrime[XN];
    phi[1]=1;
    for(int i=2;i<=N;++i) {
        if(!notPrime[i]) {
            prime[++pcnt]=i;
            phi[i]=i-1;
            pdv[i]={i};
        }
        for(int j=1;j<=pcnt && i*prime[j]<=N;++j) {
            notPrime[i*prime[j]]=1;
            pdv[i*prime[j]]=pdv[i];
            if(i%prime[j]==0) {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            } else {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
                pdv[i*prime[j]].push_back(prime[j]);
            }
        }
    }
}

//P只有复根 无法因式分解

std::vector<int> FindDivisors(int x) {
    std::vector<int> res={};
    for(int d=1;d*d<=x;++d)
        if(x%d==0) {
            res.push_back(d);
            if(x!=d*d)
                res.push_back(x/d);
        }
    return res;
}

std::vector<int> Calc(int n) {
    std::vector<int> posi,nega;
    for(int S=0;S<(1<<pdv[n].size());++S) {
        int d=1;
        for(size_t i=0;i<pdv[n].size();++i)
            if(S>>i&1)
                d*=pdv[n][i];
        (__builtin_popcount(S)&1?nega:posi).push_back(n/d);
    }
    std::vector<int> P{1};
    for(auto d : posi) {
        //P*=(x^d-1)
        std::vector<int> T(P.size()+d,0);
        for(size_t i=0;i<P.size();++i) {
            T[i]-=P[i];
            T[i+d]+=P[i];
        }
        P=T;
    }
    for(auto d : nega) {
        //P/=(x^d-1)
        std::vector<int> T(P.size()-d,0);
        for(int i=T.size()-1;i>=0;--i) {
            T[i]=P[i+d];
            P[i]+=P[i+d];
            P[i+d]=0;
        }
        P=T;
    }
    return P;
}

void Work() {
    int n;std::cin>>n;
    auto divisor=FindDivisors(n);
    std::vector<std::vector<int>> Ans;
    for(int d : divisor)
        Ans.push_back(Calc(d));
    std::sort(Ans.begin(),Ans.end(),[](auto const &a,auto const &b)->bool {
        if(a.size()!=b.size())
            return a.size()<b.size();
        else
            for(int i=a.size()-1;i>=0;--i)
                if(a[i]!=b[i])
                    return a[i]<b[i];
            assert(0);
    });
    for(auto &v : Ans) {
        std::cout<<'(';
        for(int i=v.size()-1;i>=0;--i)
            if(v[i]) {
                if(v[i]>0 && i!=(int)v.size()-1)
                    std::cout<<'+';
                else if(v[i]<0)
                    std::cout<<'-';
                if(abs(v[i])!=1 || i==0)
                    std::cout<<abs(v[i]);
                if(i) {
                    std::cout<<'x';
                    if(i>=2)
                        std::cout<<'^'<<i;
                }
            }
        std::cout<<')';
    }
    std::cout<<'\n';
}

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    Prep();
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}