[ICPC 2018 Asia Qingdao Onsite L]Sub-cycle Graph

Link

n个点m条边组成的无环图的数目。生成函数学的很不好。

Solution

题目中的图本质上是有标号链的集合。
长度为n的有标号链个数为\max(1,\frac {n!}2)
有标号链的egf为

E=x+\frac 12(x^2+x^3+…)=x(\frac {1-\frac x2}{1-x})

那么k条有标号链的序列的egf为E^k,由于n个点m条边会出现n-m条链,因此答案就是\frac {n!}{(n-m)!}([x^n] (E^{n-m}))
至于求[x^n]E^k的方法,A=(1-\frac x2)^k,B=(\frac 1{1-x})^k可以求出来,求出x^{n-k}[A*B]就OK了。

\begin{aligned}
A&=\sum_{i=0}^k(-1)^i\frac {\binom{k}{i}}{2^i}x^i\\
B&=\sum_{i=0}^k\binom{k-1+i}{i}x^i
\end{aligned}

Code

#include <bits/stdc++.h>

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

int Add(int x,int const &y) {
    return (x+=y)>=P?x-P:x;
}

int Mul(long long x,int const &y) {
    return x*y%P;
}

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

int fact[XN],ifact[XN],inv2[XN];

int C(int n,int m) {
    return n>=m?Mul(fact[n],Mul(ifact[m],ifact[n-m])):0;
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    fact[0]=1;inv2[0]=1;inv2[1]=Pow(2,P-2);
    for(int i=1;i<=N;++i) {
        fact[i]=Mul(fact[i-1],i);
        inv2[i]=Mul(inv2[i-1],inv2[1]);
    }
    ifact[N]=Pow(fact[N],P-2);
    for(int i=N-1;i>=0;--i)
        ifact[i]=Mul(ifact[i+1],i+1);

    int T;std::cin>>T;
    while(T--) {
        int n,m;std::cin>>n>>m;
        if(m>n)
            std::cout<<0<<'\n';
        else if(n==m)
            std::cout<<Mul(fact[n-1],inv2[1])<<'\n';
        else {
            int k=n-m;int Ans=0;
            for(int i=0;i<=n-k;++i)
                Ans=Add(Ans,Mul(Mul(i&1?P-1:1,Mul(C(k,i),inv2[i])),C(n-i-1,k-1)));
            Ans=Mul(Ans,Mul(fact[n],ifact[n-m]));
            std::cout<<Ans<<'\n';
        }
    }
    return 0;
}

[Petrozavodsk Summer-2014. Yandex Contest C]Supermutations

Solution

维护下标模5余0,1,2,3,4的位置的数字的区间和,记录每个数组当前的开头位置。
每个数组的开头位置是不同的!

Code

const int XN=1e5+11;

struct Arr {
    int off;
    long long sum[XN*2];

    long long Sum(int p,int x) {
        return sum[x/5+off+(x%5>p)];
    }

    long long Sum(int p,int l,int r) {
        return Sum(p,r)-Sum(p,l-1);
    }
}*a[5];

int main() {
//  freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n;std::cin>>n;
    for(int i=0;i<5;++i)
        a[i]=new Arr;
    for(int j=1;j<=n;++j) {
        for(int i=0;i<5;++i) {
            int x;std::cin>>x;
            a[i]->sum[j]=a[i]->sum[j+n]=x;
        }
    }
    for(int i=0;i<5;++i)
        for(int j=1;j<=n*2;++j)
            a[i]->sum[j]+=a[i]->sum[j-1];

    int m;std::cin>>m;
    while(m--) {
        char op;std::cin>>op;
        if(op=='?') {
            int l,r;std::cin>>l>>r;
            long long res=0;
            for(int i=0;i<5;++i)
                res+=a[i]->Sum(i,l,r);
            std::cout<<res<<'\n';
        } else if(op=='<') {
            int x;std::cin>>x;
            Arr *t[5];
            for(int i=0;i<5;++i) {
                (a[i]->off+=x/5+(x%5>i))%=n;
                t[i]=a[(i+x)%5];
            }
            for(int i=0;i<5;++i)
                a[i]=t[i];
        } else {
            int q[5];
            Arr *t[5];
            for(int i=0;i<5;++i) {
                std::cin>>q[i];
                t[i]=a[--q[i]];
            }
            for(int i=0;i<5;++i)
                a[i]=t[i];
        }
    }


    return 0;
}

[ICPC 2018 Asia Yokohama Onsite F]Fair Chocolate Cutting

Link

Solution

最长的距离,貌似一定一端在顶点上。
最短的距离,固定一个端点在一条边上,那么这条平分线的长度貌似应该是单峰的。
然后就扫一遍,三分三分,就OK了。
然而正解……

Code

const int XN=5000+11;
const long double inf=1e100;

struct Point {
    long double x,y;

    friend Point operator +(Point const &a,Point const &b) {
        return {a.x+b.x,a.y+b.y};
    }

    friend Point operator -(Point const &a,Point const &b) {
        return {a.x-b.x,a.y-b.y};
    }

    friend Point operator *(Point const &p,long double const &k) {
        return {p.x*k,p.y*k};
    }

    friend long double Inner(Point const &a,Point const &b) {
        return a.x*b.x+a.y*b.y;
    }

    friend long double Outer(Point const &a,Point const &b) {
        return a.x*b.y-a.y*b.x;
    }

    friend long double Dist(Point const &a,Point const &b) {
        return sqrt(Inner(a-b,a-b));
    }
}p[XN];

long double Length(Point a,Point b,long double t,Point c,Point d,long double size) {
    //a+(b-a)*t 在cd上找 让bd部分为size的线
    Point v=a+(b-a)*t;
    long double req=(Outer(b-a,c-a)+Outer(c-a,d-a))/2-size-Outer(v-a,d-a)/2;
    //(v-d) x (t*(c-d))=2*size
    long double l=2*req/Outer(v-d,c-d);
    return Dist(v,d+(c-d)*l);
}

long double SolveMin(Point a,Point b,Point c,Point d,long double size) {
    long double l=0,r=1;
    while(r-l>1e-15) {
        long double m1=l+(r-l)/3,m2=r-(r-l)/3;
        if(Length(a,b,m1,c,d,size)>Length(a,b,m2,c,d,size))
            l=m1;
        else
            r=m2;
    }
    return Length(a,b,l,c,d,size);
}

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n;std::cin>>n;
    for(int i=0;i<n;++i)
        std::cin>>p[i].x>>p[i].y;
    long double size=0;
    for(int i=2;i<n;++i)
        size+=Outer(p[i-1]-p[0],p[i]-p[0]);

    size/=2;

    long double AnsMax=-inf,AnsMin=inf,sum=0;
    for(int l=0,r=1;l<n;sum-=Outer(p[(l+1)%n]-p[l],p[r]-p[l])/2,++l) {
        for(long double d=0;sum+(d=Outer(p[r]-p[l],p[(r+1)%n]-p[l])/2)<size/2;sum+=d,(r+=1)%=n);
        Enlarge(AnsMax,Length(p[l],p[l],0,p[r],p[(r+1)%n],size/2-sum));
        Reduce(AnsMin,SolveMin(p[l==0?n-1:l-1],p[l],p[r],p[(r+1)%n],size/2-sum));
    }
    std::cout<<std::fixed<<std::setprecision(10)<<AnsMin<<'\n'<<AnsMax<<'\n';
    return 0;
}

[ICPC 2018 Asia Yokohama Onsite D]Shortest Common Non-Subsequence

Link

Solution

正着DP,f[i][j]表示第一个字符串匹配到i第二个匹配到j的最短长度。DP完之后,考虑构造字典序最小的解。
(|s|+1,|t|+1)状态出发,沿着DP值递减的路径走,把路上经过的所有的点都标记上,表示从这个点有一条合法的最短路径。
求答案的时候,如果填0之后到达的状态是被标记的状态,且DP值增加了1,那么就填0。一个点在一条最短路上不代表这个点随便走都行。

Code

const int XN=4e3+5;

int main() {
//  freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    static char s[XN],t[XN];
    static int snext[XN][2],tnext[XN][2];
    std::cin>>(s+1)>>(t+1);
    int slen=strlen(s+1),tlen=strlen(t+1);
    snext[slen+1][0]=snext[slen+1][1]=slen+1;
    for(int i=slen;i>=0;--i)
        for(int c=0;c<2;++c)
            snext[i][c]=s[i+1]-'0'==c?i+1:snext[i+1][c];
    tnext[tlen+1][0]=tnext[tlen+1][1]=tlen+1;
    for(int i=tlen;i>=0;--i)
        for(int c=0;c<2;++c)
            tnext[i][c]=t[i+1]-'0'==c?i+1:tnext[i+1][c];
    static int f[XN][XN];
    memset(f,31,sizeof(f));
    f[0][0]=0;
    for(int i=0;i<=slen+1;++i)
        for(int j=0;j<=tlen+1;++j)
            if(i!=slen+1 || j!=tlen+1)
                for(int c=0;c<2;++c)
                    Reduce(f[snext[i][c]][tnext[j][c]],f[i][j]+1);  

//  std::cerr<<f[slen+1][tlen+1]<<'\n';

    static bool isValid[XN][XN];
    isValid[slen+1][tlen+1]=1;
    for(int i=slen+1;i>=0;--i)
        for(int j=tlen+1;j>=0;--j)
            if(i!=slen+1 || j!=tlen+1)
                for(int c=0;c<2;++c)
                    if(f[snext[i][c]][tnext[j][c]]==f[i][j]+1)
                        isValid[i][j]|=isValid[snext[i][c]][tnext[j][c]];

    for(int x=0,y=0;x!=slen+1 || y!=tlen+1;) {
        static int cc;
        assert(f[x][y]==cc++);

        for(int c=0;c<2;++c)
            if(isValid[snext[x][c]][tnext[y][c]] && f[snext[x][c]][tnext[y][c]]==f[x][y]+1) {
                std::cout<<c;
                x=snext[x][c];y=tnext[y][c];
                break;
            }
    }
    std::cout<<'\n';
    return 0;
}

[The 14th Beihang University Collegiate Programming Contest Onsite B]zzh与子序列

这场比赛,虽然签到失败,但是怼出来了这道稍微有点水平的题,也算还行吧。

Problem

给定数组,问字典序第k大的子序列是谁并输出,n\le 5000

Solution

这种题必定是从高到低一位位确定,具体的比较类似在值域线段树上找第k大的值。
对于这道题,主要的思路就是考虑每个位置被多少个前缀覆盖着。假如已经确定了一个前缀,位置ix个前缀覆盖着,那么位置i就会对下一位填a[i]的方案方案数产生2^{n-i}的贡献。
注意,我的写法将下一位为空视作为0,和其它的字符等同处理。下一位为空的总方案数就是已有的前缀个数。
统计前缀对后面位置的覆盖用差分做就好了。

Code

const int XN=5e3+11;
const long long INF=1e18;

long long Mul(long long const &a,long long const &b) {
    return (long double)a*(long double)b<INF?a*b:INF;
}

void Work() {
    static int a[XN];
    int n,m;long long k;
    std::cin>>n>>m>>k;
    ++k;
    static long long cnt[XN],pw2[XN]={1};
    for(int i=1;i<=n;++i) {
        std::cin>>a[i];
        cnt[i]=1;
        pw2[i]=Mul(pw2[i-1],2);
    }
    static long long sum[XN];
    std::vector<int> Ans;
    sum[0]=1;
    for(int b=1;b<=n;++b) {
        for(int i=1;i<=m;++i)
            sum[i]=0;
        for(int i=1;i<=n;++i)
            Reduce(sum[a[i]]+=Mul(cnt[i],pw2[n-i]),INF);
        int v=0;
        while(k>sum[v])
            k-=sum[v++];
        if(v)
            Ans.push_back(v);
        else
            break;
        sum[0]=0;
        if(a[n]==v)
            sum[0]+=cnt[n];
        for(int i=n;i>=1;--i)
            sum[0]+=(cnt[i]=a[i-1]==v?cnt[i-1]:0);
        for(int i=1;i<=n;++i)
            Reduce(cnt[i]+=cnt[i-1],INF);
    }
    for(size_t i=0;i<Ans.size();++i)
        std::cout<<Ans[i]<<(i==Ans.size()-1?'\n':' ');
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

[ICPC 2018 Beijing Onsite G]Solving Equations is Easy

Link

这题目的思路好清奇啊……xyx好强啊!!

Solution

k次复单位根为w_k

\begin{aligned}
x^k-a^k&=a^k[(\frac xa)^k-1]\\
&=a^k\prod_{i=0}^{k-1}(\frac xa-w_k^i)\\
&=\prod_{i=0}^{k-1}(x-aw_k^i)
\end{aligned}

已知\prod (x-a_i),考虑先求\prod (x^k-a_i^k)
按照上式展开得\prod_{t=0}^{k-1} [ \prod_{i=1}^n (x-a_iw_k^t) ]

\begin{aligned}
\prod_{i=1}^n (x-a_iw_k^t)&=w_k^{tn}\prod_{i=1}^n (\frac {x}{w_k^t}-a_i)\\
&=w_k^{tn}\prod_{i=1}^n (\frac {x}{w_k^t}-a_i)\\
&=w_k^{tn}f(\frac {x}{w_k^t})
\end{aligned}

代回

\begin{aligned}
\prod(x^k-a_i^k)&=\prod_{t=0}^{k-1}[w_k^{tn}f(\frac {x}{w_k^t})]\\
&=w_k^{\frac {nk(k-1)}2}\prod_{t=0}^{k-1}f(\frac x{w_k^t})
\end{aligned}

Code

const int XN=20;
const long double pi=acos(-1.); 

typedef std::vector<std::complex<long double>> Polynomial;

Polynomial operator *(Polynomial const &A,Polynomial const &B) {
    Polynomial C(A.size()+B.size()-1,0);
    for(size_t i=0;i<A.size();++i)
        for(size_t j=0;j<B.size();++j)
            C[i+j]+=A[i]*B[j];
    return C;
}

int main() {
//  freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,m;
    while(std::cin>>n>>m,n) {
        static int a[XN];
        std::complex<long double> root(cos(2*pi/m),sin(2*pi/m));
        static std::complex<long double> w[XN];
        for(int i=0;i<m;++i)
            w[i]={cos(2*i*pi/m),sin(2*i*pi/m)};//w[i-1]*root;
        for(int i=0;i<n;++i)
            std::cin>>a[i];
        a[n]=1;
        Polynomial Ans{w[n*m*(m-1)/2%m]};
        for(int t=0;t<m;++t) {
            Polynomial f(n+1);
            for(int i=0;i<=n;++i)
                f[i]=std::complex<long double>(a[i])*w[((m-t*i)%m+m)%m];
            Ans=Ans*f;
        }
        for(int i=0;i<n;++i)
            std::cout<<std::fixed<<std::setprecision(0)<<Ans[i*m].real()<<(i==n-1?'\n':' ');
    }
    return 0;
}

The 14th Beihang University Collegiate Programming Contest Online Solutions

给北航出题人点赞!期待后天的现场赛!

A

b-a\le 50,那么容易得出,当a较大时,给两个人的时间段数必须相同,否则不可能和相等。
粗略估计可以得到一个界2500a<2500时暴力DP,a\ge 2500时,将每个时间长度-a,然后状态里再计一下给两个人段数的差值,然后就可以DP了。

const int XN=50+11;

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--) {
        int n,a,b;std::cin>>n>>a>>b;
        static int t[XN];
        for(int i=1;i<=n;++i)
            std::cin>>t[i];
        if(a>2500) {
            for(int i=1;i<=n;++i)
                t[i]-=a;
            static const int N=50,H=2500;
            static int f[2][2*N+1][2*H+1];
            memset(f[0],127,sizeof(f[0]));
            f[0][N][H]=0;
            for(int i=1,sum=0,o=1;i<=n;sum+=t[i++],o^=1) {
                memset(f[o],127,sizeof(f[o]));
                for(int j=-(i-1);j<=(i-1);++j)
                    for(int k=-sum;k<=sum;++k) {
                        int x=f[o^1][N+j][H+k];
                        if(k+t[i]<=H)
                            Reduce(f[o][N+j+1][H+k+t[i]],x);
                        if(k-t[i]>=-H)
                            Reduce(f[o][N+j-1][H+k-t[i]],x);
                        Reduce(f[o][N+j][H+k],x+1);
                    }
            }
            std::cout<<f[n&1][N][H]<<'\n';
        } else {
            static const int H=50*2500;
            static int f[2][2*H+1];
            memset(f[0],127,sizeof(f[0]));
            f[0][H]=0;
            for(int i=1,o=1,sum=0;i<=n;sum+=t[i++],o^=1) {
                memset(f[o],127,sizeof(f[o]));
                for(int j=-sum;j<=sum;++j) {
                    int x=f[o^1][H+j];
                    if(j+t[i]<=H)
                        Reduce(f[o][H+j+t[i]],x);
                    if(j-t[i]>=-H)
                        Reduce(f[o][H+j-t[i]],x);
                    Reduce(f[o][H+j],x+1);
                }
            }
            std::cout<<f[n&1][H]<<'\n';
        }
    }
    return 0;
}

C

使用点分治。在一层中,统计以根为端点的所有链的边权和and边权异或和。考虑如何统计答案。
把式子(a_1+a_2)(b_1{\rm\ xor\ }b_2)展开一下,最后可以转化成求a_i(\sum b_j{\rm\ xor\ }b_i)的和。考虑到xor的位独立性,可以一位位地统计。

const int XN=1e5+11,P=1e9+7,INF=0x1f1f1f1f;

struct Edge {
    int to;
    unsigned int v;
};

std::vector<Edge> G[XN];

namespace StaticVertexBasedDC {
    bool ud[XN];
    int size[XN];

    int GetSize(int pos,int fa) {
        size[pos]=1;
        for(auto &e : G[pos]) {
            int u=e.to;
            if(!ud[u] && u!=fa)
                size[pos]+=GetSize(u,pos);
        }
        return size[pos];
    }

    int Centre(int pos) {
        GetSize(pos,0);
        int tot=size[pos];
        bool found;
        do {
            found=0;
            for(auto &e : G[pos])
                if(!ud[e.to] && size[e.to]<size[pos] && size[e.to]*2>=tot) {
                    pos=e.to;
                    found=1;
                    break;
                }
        } while(found);
        return pos;
    }

    long long Calc(std::pair<long long,unsigned int> a[],int n,std::array<int,32> const &xs) {
        long long res=0;
        for(int i=1;i<=n;++i) {
            long long sum=0;
            for(int b=31;b>=0;--b)
                (sum+=(long long)(a[i].second>>b&1?n-xs[b]:xs[b])*(1u<<b))%=P;
            (res+=a[i].first*sum)%=P;
        }
        return res;
    }

    std::pair<long long,unsigned int> all[XN],sub[XN];
    std::array<int,32> aset,sset;
    int allc,subc;
    void DFS(int pos,int fa,long long len,unsigned int xs) {
        sub[++subc]={len,xs};
        for(auto &e : G[pos])
            if(!ud[e.to] && e.to!=fa)
                DFS(e.to,pos,(len+e.v)%P,xs^e.v);
    }

    int rec;

    long long DC(int pos) {

        static int cc;
        ++cc;
        Enlarge(rec,cc);

        ud[pos]=1;
        allc=0;
        long long res=0;
        for(int i=0;i<32;aset[i++]=0);
        for(auto &e : G[pos]) {
            int u=e.to;
            if(!ud[u]) {
                for(int i=0;i<32;sset[i++]=0);
                subc=0;

                DFS(e.to,pos,e.v,e.v);
                for(int i=1;i<=subc;++i)
                    for(int b=31;b>=0;--b)
                        sset[b]+=sub[i].second>>b&1;

                (res-=Calc(sub,subc,sset))%=P;
                for(int b=31;b>=0;--b)
                    aset[b]+=sset[b];
                std::copy(sub+1,sub+1+subc,all+allc+1);
                allc+=subc;
            }
        }
        (res+=Calc(all,allc,aset))%=P;
        for(int i=1;i<=allc;++i)
            (res+=all[i].first*all[i].second%P)%=P;
        for(auto &e : G[pos]) {
            int u=e.to;
            if(!ud[u])
                (res+=DC(Centre(u)))%=P;
        }

        --cc;

        return res;
    }
}

void Work() {
    int n;std::cin>>n;
    using namespace StaticVertexBasedDC;
    for(int i=1;i<=n;++i) {
        ud[i]=0;
        std::vector<Edge>().swap(G[i]);
    }
    for(int i=1;i<=n-1;++i) {
        int x,y;unsigned int v;
        std::cin>>x>>y>>v;
        G[x].push_back({y,v});
        G[y].push_back({x,v});
    }

    rec=0;

    int Ans=DC(Centre(1));

//  std::cerr<<rec<<':'<<'\n';

    Ans<0  && (Ans+=P);
    std::cout<<Ans<<'\n';
}
int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

E

从大到小枚举d,然后用枚举d的倍数,并查集判断是否已经联通。
要先把相同的数字合并成一个,复杂度就是标准O(n\log n)了。

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

int dsu[XN];
int Root(int x) {
    return dsu[x]?dsu[x]=Root(dsu[x]):x;
}

void Work() {
    int n;std::cin>>n;
    static int cnt[XN];
    for(int i=1;i<=V;++i)
        cnt[i]=dsu[i]=0;
    long long Ans=0;
    for(int i=1;i<=n;++i) {
        int x;std::cin>>x;
        cnt[x]++;
    }
    for(int i=1;i<=V;++i)
        if(cnt[i])
            Ans+=(long long)(cnt[i]-1)*i;
    for(int d=V;d>=1;--d) {
        std::vector<int> v;
        for(int x=d;x<=V;x+=d)
            if(cnt[x])
                v.push_back(x);
        for(size_t i=0;i+1<v.size();++i)
            if(Root(v[i])!=Root(v[i+1])) {
                dsu[Root(v[i])]=Root(v[i+1]);
                Ans+=d;
            }
    }
    std::cout<<Ans<<'\n';
}

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

G

对于每个if[i][k]表示以i为结尾的所有上升子序列的\sum x^k是多少。转移的时候,对于a[j] < a[i],则a[i]可以接在以j为结尾的子序列后面,使得子序列长度+1。将(x+1)^k用二项式定理展开,就可以求出来\sum (x+1)^k了。
然后加上一个树状数组维护就好了

int C[21][21];
std::array<int,21> AddOne(std::array<int,21> const &a) {
    std::array<int,21> res;
    for(int i=0;i<=20;++i) {
        res[i]=0;
        for(int j=0;j<=i;++j)
            (res[i]+=(long long)C[i][j]*a[j]%P)%=P;
    }
    return res;
}

std::array<int,21> &operator +=(std::array<int,21> &a,std::array<int,21> const &b) {
    for(int i=0;i<=20;++i)
        (a[i]+=b[i])%=P;
    return a;
}

std::array<int,21> bit[XN];int n;
std::array<int,21> Sum(int pos) {
    std::array<int,21> res;
    for(int i=0;i<=20;res[i++]=0);
    for(;pos;pos-=pos & -pos)
        res+=bit[pos];
    return res;
}

void Add(int pos,std::array<int,21> const &v) {
    for(;pos<=n;pos+=pos & -pos)
        bit[pos]+=v;
}

std::pair<int,int> p[XN];
std::vector<int> num;

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    C[0][0]=1;
    for(int i=1;i<=20;++i) {
        C[i][0]=1;
        for(int j=1;j<=i;++j)
            C[i][j]=C[i-1][j-1]+C[i-1][j];
    }
    int T;std::cin>>T;
    while(T--) {
        std::vector<int>().swap(num);
        int n,k;std::cin>>n>>k;
        long long Ans=0;
        for(int i=1;i<=n;++i) {
            std::cin>>p[i].first>>p[i].second;
            num.push_back(p[i].first);
        }
        std::sort(num.begin(),num.end());
        num.erase(std::unique(num.begin(),num.end()),num.end());
        for(int i=1;i<=(int)num.size()+1;++i)
            for(int j=0;j<=20;bit[i][j++]=0);
        ::n=num.size()+1;
        Add(1,{1});
        for(int i=1;i<=n;++i) {
            p[i].first=std::lower_bound(num.begin(),num.end(),p[i].first)-num.begin()+2;
            auto res=Sum(p[i].first-1),
                 v=AddOne(res);
            for(int j=0;j<=20;++j)
                v[j]=(long long)v[j]*p[i].second%P;
            (Ans+=v[k])%=P;
            Add(p[i].first,v);
        }
        std::cout<<Ans<<'\n';
    }
    return 0;
}

J

感觉这次写的不错,留个模板

const int XN=20;

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

int Inverse(long long a,int P) {
    return Pow(a,P-2,P);
}

long long Mul(long long x,long long y,long long P) {
    long long res=0;
    for(x%=P;y;y>>=1,(x*=2)%=P)
        if(y&1)
            (res+=x)%=P;
    return res;
}

struct Lucas {
    int P;
    std::vector<int> fact,ifact;

    Lucas(int P):P(P),fact(P),ifact(P) {
        fact[0]=1;
        for(int i=1;i<P;++i)
            fact[i]=(long long)fact[i-1]*i%P;
        ifact[P-1]=Inverse(fact[P-1],P);
        for(int i=P-2;i>=0;--i)
            ifact[i]=(long long)ifact[i+1]*(i+1)%P;
    }

    int C(int n,int m) {
        return n<m?0:(long long)fact[n]*ifact[m]%P*ifact[n-m]%P;
    }

    int operator ()(long long n,long long m) {
        long long res=1;
        while(n && m) {
            (res*=C(n%P,m%P))%=P;
            n/=P,m/=P;
        }
        return res;
    }
};

struct MultiLucas {
    std::vector<Lucas> c;
    std::vector<int> p,t;
    std::vector<long long> r;
    long long P;

    MultiLucas(std::vector<int> const &p):p(p),t(p.size()),r(p.size()) {
        P=1;
        c.reserve(p.size());
        for(size_t i=0;i<p.size();++i) {
            P*=p[i];
            c.emplace_back(p[i]);
        }

        for(size_t i=0;i<p.size();++i) {
            r[i]=P/p[i];
            t[i]=Inverse(r[i],p[i]);
        }
    }

    long long operator ()(long long n,long long m) {
        long long res=0;
        for(size_t i=0;i<p.size();++i)
            (res+=Mul((long long)c[i](n,m)*t[i]%P,r[i],P))%=P;
        return res;
    }
};

void Work() {
    int n,k;
    long long m;
    std::cin>>n>>m>>k;
    std::vector<int> p(k);
    static long long v[XN];
    long long all=0;
    for(int i=0;i<n;++i) {
        std::cin>>v[i];
        all+=v[i];
    }
    long long P=1;
    for(int i=0;i<k;++i) {
        std::cin>>p[i];
        P*=p[i];
    }
    MultiLucas C(p);
    long long Ans=0;
    for(int S=0;S<(1<<n);++S) {
        int cnt=0;long long sum=0;
        for(int i=0;i<n;++i)
            if(S>>i&1) {
                cnt++;
                sum+=v[i]+1;
            }
        if(sum<=m) {
            (Ans+=Mul(cnt&1?P-1:1,C(m-sum+n-1,n-1),P))%=P;
        }
    //  std::cerr<<S<<'\n';
    }
    std::cout<<Ans<<'\n';
}

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

[ICPC 2018 Beijing Onsite F]The Kth Largest Value

Link

Solution

询问组数极少。。一开始居然没看到。。。。
首先,用bitset维护出每个点能到的点的集合。对于每组询问,二分答案。
二分答案的时候,需要快速地查询bitset里面某段区间1的个数。
对于一个bitset,直接做区间和是O(\frac n{32})的。但是,可以对1的个数做一个前缀和,类似分块一样。这样,单次询问的复杂度就是O(1)了。

Code

const int XN=5e4+11;

std::vector<int> G[XN],C[XN];int n;

const int SIZE=(XN>>6)+1;
struct BitSet {
    unsigned long long b[SIZE];
    int sum[SIZE];

    void Reset() {
        memset(b,0,sizeof(b));
    }

    void Set(unsigned int pos,bool val) {
        val==0?(b[pos>>6]&=~(1ull<<(pos&63))):(b[pos>>6]|=1ull<<(pos&63));
    }

    void GetSum() {
        for(int i=0;i<SIZE;++i)
            sum[i]=(i==0?0:sum[i-1])+__builtin_popcountll(b[i]); 
    }

    int Sum(int l,int r) {
        return Sum(r)-Sum(l-1);
    }

    int Sum(int pos) {
        Reduce(pos,n);
        return pos<1?0:((pos>>6?sum[(pos>>6)-1]:0)+__builtin_popcountll(b[pos>>6]&(((__int128)1<<((pos&63)+1))-1)));
    }

    BitSet &operator |=(BitSet const &other) {
        for(int i=0;i<SIZE;++i)
            b[i]|=other.b[i];
        return *this;
    }

    bool Test(unsigned int pos) const {
        return b[pos>>6]>>(pos&63)&1;
    }
}set[XN];

int low[XN],dfn[XN],stack[XN],dfc,cc,belong[XN],size[XN],top;
bool instack[XN];
void DFS(int pos) {
    dfn[pos]=low[pos]=++dfc;
    instack[stack[++top]=pos]=1;
    for(auto u : G[pos])
        if(!dfn[u]) {
            DFS(u);
            Reduce(low[pos],low[u]);
        } else if(instack[u])
            Reduce(low[pos],dfn[u]);
    if(dfn[pos]==low[pos])
        for(size[++cc]=0,set[cc].Reset();stack[top+1]!=pos;top--) {
            int u=stack[top];
            instack[u]=0;
            belong[u]=cc;
            size[cc]++;
            set[cc].Set(u,1);
        }
}

int Sum(int x,int allb) {
    int res=0;
    for(int i=1;i<=n;++i)
        res+=set[belong[i]].Sum((x^i)&(~allb),(x^i)|allb);
    return res;
}

int Query(int k) {
    int res=0;
    for(int b=15;b>=0;--b) {
        int cnt=Sum(res|(1<<b),(1<<b)-1);
        if(k<=cnt)
            res|=1<<b;
        else
            k-=cnt;
    }
    return res;
}

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--) {
        int m,q;std::cin>>n>>m>>q;
        dfc=cc=0;
        for(int i=1;i<=n;++i) {
            G[i].clear();
            dfn[i]=0;
        }
        for(int i=1;i<=m;++i) {
            int x,y;std::cin>>x>>y;
            G[x].push_back(y);
        }

        for(int i=1;i<=n;++i)
            if(!dfn[i]) {
                DFS(i);
                assert(top==0);
            }

        static int deg[XN];

        for(int i=1;i<=cc;++i) {
            C[i].clear();
            deg[i]=0;
        }

        for(int i=1;i<=n;++i)
            for(auto u : G[i])
                if(belong[u]!=belong[i])
                    C[belong[i]].push_back(belong[u]);

        for(int i=1;i<=cc;++i) {
            std::sort(C[i].begin(),C[i].end());
            C[i].erase(std::unique(C[i].begin(),C[i].end()),C[i].end());
            for(int u : C[i])
                deg[u]++;
        }

        std::queue<int> Q;

        for(int i=1;i<=cc;++i)
            if(!deg[i])
                Q.push(i);

        while(!Q.empty()) {
            int pos=Q.front();Q.pop();
            for(auto u : C[pos]) {
                set[u]|=set[pos];
                if(--deg[u]==0)
                    Q.push(u);
            }
        }

        for(int i=1;i<=cc;++i)
            set[i].GetSum();

        while(q--) {
            int k;std::cin>>k;
            std::cout<<Query(k)<<'\n';
        }
    }
    return 0;
}

[ICPC 2018 Beijing Onsite J]Rikka with Triangles

Link

Solution

以每个点为原点,将剩下的点排极角序,然后按顺序枚举剩下的点,记录它上方的,以这两点连线为一边的锐角和钝角直角分别的x,y坐标和。就可以用叉积公式算面积了。
这样做,锐角三角形会被3个锐角计入三次,其他三角形会锐角计入2次,那么当作为非锐角被计入时,就减去两倍的面积。
最后剩下的是所有锐角三角形面积和的三倍,/3输出即可。

Code

const int P=998244353;

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

const int XN=2e3+11,inv3=Pow(3,P-2);

struct Point {
    long long x,y;

    friend Point operator -(Point const &a,Point const &b) {
        return {a.x-b.x,a.y-b.y};
    }

    friend __int128 Inner(Point const &a,Point const &b) {
        return (__int128)a.x*b.x+(__int128)a.y*b.y;
    }

    friend __int128 Outer(Point const &a,Point const &b) {
        return (__int128)a.x*b.y-(__int128)a.y*b.x;
    }
}p[XN],g[XN*2];

void Work() {
    int n;std::cin>>n;
    for(int i=0;i<n;++i)
        std::cin>>p[i].x>>p[i].y;
    long long Ans=0;
    for(int c=0;c<n;++c) {
        for(int i=0;i<n;++i)
            g[i]=p[i]-p[c];
        std::swap(g[c],g[0]);
        std::sort(g+1,g+n,[](Point const &a,Point const &b)->bool {
                    auto Quad=[](Point const &a)->int {
                        return a.x>0 && a.y>=0?1:(a.x<=0 && a.y>0?2:(a.x<0 && a.y<=0?3:4));
                    };
                    int qa=Quad(a),qb=Quad(b);
                    return qa==qb?Outer(b,a)<0:qa<qb;
                });
        static long long xs[XN*2],ys[XN*2];
        for(int i=1;i<n;++i)
            g[n+i-1]=g[i];
        for(int i=1;i<2*n-1;++i) {
            xs[i]=(xs[i-1]+g[i].x)%P;
            ys[i]=(ys[i-1]+g[i].y)%P;
        }
        for(int i=1,le=1;i<n;++i) {
            auto FindLast=[&](int L,int R,std::function<bool(Point)> Judge)->int {//Last Satisfies Judge(g[i])
                    while(L!=R) {
                        int M=(L+R+1)/2;
                        if(Judge(g[M]))
                            L=M;
                        else
                            R=M-1;
                    }
                    return L;
                };
            Enlarge(le,i);
            while(Outer(g[i],g[le])==0)
                ++le;
            Point neg={-g[i].x,-g[i].y};
            if(Outer(g[le],neg)>0) {
                int oppo=FindLast(le,i+n-1,[&](Point const &p)-> bool { return Outer(p,neg)>0; });
                Point axis={-g[i].y,g[i].x};
                int mid=Outer(g[le],axis)>0?FindLast(le,oppo,[&](Point const &p)->bool { return Outer(p,axis)>0; }):le-1;
                (Ans+=g[i].x%P*(3*ys[mid]-2*ys[oppo]-ys[le-1])%P-g[i].y%P*(3*xs[mid]-2*xs[oppo]-xs[le-1])%P)%=P;
            }
        }
    }
    Ans<0 && (Ans+=P);
    (Ans*=inv3)%=P;
    std::cout<<Ans<<'\n';
}

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

[ICPC 2018 Jiaozuo Onsite B]Ultraman vs. Aodzilla and Bodzilla

Link

Solution

很不错的想法啊……
首先,一个结论是,1…n这些数字,取出一些,能凑出1…\frac {n(n+1)}{2}之间的所有的和。
S(x)是最小的满足\frac {n(n+1)}{2}\ge xn
那么,同时打掉两个怪物所需的最少时间是S(HP_A+HP_B),因为S(HP_A+HP_B)个轮次中可以凑出HP_A或者HP_B,这样其他的轮次用于打另一个怪,在这个时间内肯定可以打完。
枚举先打哪个怪物,所需的时间同样可以计算。设先打x后打y,那么最终的伤害就是S(HP_x)ATK_x+S(HP_A+HP_B)ATK_{y}。枚举一下先打A还是先打B,显然最小的伤害值一定在这两个中间产生,因为伤害值的表达式中的每一个系数都达到了最小值。
现在就考虑如何构造字典序最小的打法。
如果先打A,只有B不够打才需要修改。那么就从后往前找到第一个合法的位置把这一轮次的打A变成打B。这肯定是所有改法中字典序最小的,因为如果不改这个,就需要在前面改两个。同时,由一开始的那个结论,这样位置肯定是存在的。
如果先打B,那么为了让字典序最小,需要把一些尽量靠前的位置从B改成A。那就从前往后枚举,只要改了之后B还够打就改。最后唯一的可能是A还是不够打。那就把最后一个A的位置改回B,然后直接把A还缺的打击值的那一轮改成A。注意,A还缺的那一轮的打击值一定\le n_1,也就是一定是属于B的轮次。因为,即使是初始状态未做任何调整的前提下,A的打击值+n_1就一定> HP_A了。

Code

int Search(int x) {
    int L=1,R=x;
    while(L!=R) {
        long long M=(L+R)/2;
        if(M*(M+1)/2>=x)
            R=M;
        else
            L=M+1;
    }
    return L;
}

std::pair<long long,std::string> Case1(int ha,int hb,int aa,int ab) {
    long long n1=Search(ha),n=Search(ha+hb);
    long long hita=n1*(n1+1)/2,hitb=n*(n+1)/2-hita;
    long long harm=aa*n1+ab*n;
    std::string s;
    for(int i=1;i<=n1;++i)
        s+='A';
    for(int i=n1+1;i<=n;++i)
        s+='B';
    if(hitb<hb) {
        for(int i=n1;i>=1;--i) {
            if(hita-i>=ha && hitb+i>=hb) {
                s[i-1]='B';
                hita-=i;
                hitb+=i;
                break;
            }
        }
    }
    if(!(hita>=ha && hitb>=hb)) throw;
    return {harm,s};
}

std::pair<long long,std::string> Case2(int ha,int hb,int aa,int ab) {
    long long n1=Search(hb),n=Search(ha+hb);
    long long hitb=n1*(n1+1)/2,hita=n*(n+1)/2-hitb;
    long long harm=ab*n1+aa*n;
    std::string s;
    for(int i=1;i<=n1;++i)
        s+='B';
    for(int i=n1+1;i<=n;++i)
        s+='A';
    int last=0;
    for(int i=1;i<=n1;++i)
        if(hitb-i>=hb) {
            hitb-=i;
            hita+=i;
            s[i-1]='A';
            last=i;
        }
    if(hita<ha) {
        s[last-1]='B';
        s[last+ha-hita-1]='A';
        hitb-=ha-hita;
        hita=ha;
    }
    if(!(hita>=ha && hitb>=hb)) for(;;);
    return {harm,s};
}

void Work() {
    int ha,hb,aa,ab;std::cin>>ha>>hb>>aa>>ab;
    auto Ans=std::min(Case1(ha,hb,aa,ab),Case2(ha,hb,aa,ab));
    std::cout<<Ans.first<<' '<<Ans.second<<'\n';
}

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