[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;
}

非标准库的一些好用的东西

Bit Opearation Built-in Functions

int __builtin_ffs (int x)
//Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero. 
int __builtin_clz (unsigned int x)
//Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined. 
int __builtin_ctz (unsigned int x)
//Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined. 
int __builtin_clrsb (int x)
//Returns the number of leading redundant sign bits in x, i.e. the number of bits following the most significant bit that are identical to it. There are no special cases for 0 or other values.
int __builtin_popcount (unsigned int x)
//Returns the number of 1-bits in x.
int __builtin_parity (unsigned int x)
//Returns the parity of x, i.e. the number of 1-bits in x modulo 2.

O(n)求字符串的最小表示

Problem

求一个字符串的循环移位中字典序最小的那个。

Solution

两个指针指向两个同构串的开头,比较它们的大小,较大的那个串的与另一个串相等的那一部分及其第一个不同的字符不可能是最小同构串开头,可以直接跳过。

Code

int MinimumRepresentation(int *a,int n) {
    ++a;
    int p1=0,p2=1,len=0;
    while(p1<n && p2<n && len<n) {
        if(a[(p1+len)%n]==a[(p2+len)%n])
            len++;
        else {
            (a[(p1+len)%n]>a[(p2+len)%n]?p1:p2)+=len+1;
            if(p1==p2)
                p2++;
            len=0;
        }
    }
    return std::min(p1,p2)+1;
}