2017.10.28 NOIP模拟赛

题解 套题

目录

• 2017.10.28 NOIP模拟赛
  • 神炎皇
    • 思路
    • 代码
  • 降雷皇
    • 思路
    • 代码
  • 幻魔皇
    • 思路
    • 代码

神炎皇

思路

• 推公式快推到吐。。。
• 设$\gcd(a,b)=d,x=a/d,y=b/d$，则$x,y$互质；
• 则$(a+b)\mid ab \iff d(x+y)\mid d^2xy$；
• 所以$(x+y)\mid dxy$；
• 又由$x,y$互质可知$x+y$与$x,y$都互质，所以$(x+y)\mid d$；
• 那么现在就是要求有多少这样的$d,x,y$满足$d(x+y)\leq n$；
• 不妨设$d=k(x+y)$，那么有$k \leq\lfloor\frac{n}{(x+y)^2}\rfloor$；
• 所以$x+y \leq \lfloor\sqrt{n}\rfloor$；
• 我们枚举$z=x+y$即可。这样只需知道对于每个$z$，有多少互质对$x,y$；
• 设$v$与$z$互质，$w=z-v$，那么显然$v,w$互质，这样的$v,w$就是一对互质的$x,y$，共有$\varphi(z)$个；
• 因此$ans=\sum_{i=2}^{\lfloor\sqrt{n}\rfloor}\varphi(i)\times\lfloor\frac{n}{i^2}\rfloor$，复杂度$O(\sqrt{n})$。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <cmath>
using std::sqrt;
const int MAXN=1e7+5;
int phi[MAXN];
inline void Euler_phi(int n){
    static int prm[MAXN];
    static bool notP[MAXN];
    notP[1]=true,phi[1]=1;
    for(int i=2;i<=n;++i){
        if(!notP[i]){
            prm[++prm[0]]=i;
            phi[i]=i-1;
        }
        for(int j=1,tmp;j<=prm[0] && i*prm[j]<=n;++j){
            tmp=i*prm[j];
            notP[tmp]=true;
            if(i%prm[j]==0){
                phi[tmp]=phi[i]*prm[j];
                break;
            }
            else phi[tmp]=phi[i]*phi[prm[j]];
        }
    }
}
inline unsigned long long cal(long long n){
    int sqrt_n=sqrt(n);
    Euler_phi(sqrt_n);
    unsigned long long ret=0;
    for(int i=2;i<=sqrt_n;++i)
        ret+=(unsigned long long)phi[i]*(n/i/i);
    return ret;
}
int main(){
#ifdef DEBUG
    setIO("a");
#endif
    long long n;
    read(n);
    write(cal(n));
    return 0;
}

降雷皇

思路

• 就是一个裸的最长上升子序列，只是要统计方案数；
• 那么，普通的upper_bound做法似乎就行不通了；
• 我们考虑对于每个$a_i$，以它结尾的最长上升子序列是由一个以$a_j$结尾的最长上升子序列转移而来，其中$j<i,a_j<a_i$；
• 那么，我们只需要快速知道以$a_j$结尾的最长上升子序列最长有多长，方案数是多少就可以了；
• 怎么办呢？考虑用权值线段树维护；
• 对于每个节点，维护其值域区间内的$a_i$所构成的以$a_i$结尾的最长上升子序列的最大长度及其总方案数；
• 那么每次我们查询一下进行转移，之后将新的值插入即可，复杂度$O(n \log a_{max})$。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <algorithm>
using std::max;
const int MAXN=100005,P=123456789;
int n,maxr;
int r[MAXN];
struct query{
    int sz;
    long long sum;
    query(int sz=0,long long sum=0):sz(sz),sum(sum){}
};
class val_segT{
#define ls (u<<1)
#define rs (ls|1)
    private:
        typedef query node;
        node d[MAXN<<2];
        void upd(int u){
            if(d[ls].sz>d[rs].sz) d[u]=d[ls];
            else if(d[rs].sz>d[ls].sz) d[u]=d[rs];
            else d[u]=node(d[ls].sz,(d[ls].sum+d[rs].sum)%P);
        }
        void ist(int u,int l,int r,int pos,query &val){
            if(l==r){
                if(d[u].sz<val.sz) d[u]=val;
                else if(d[u].sz==val.sz)
                    d[u].sum=(d[u].sum+val.sum)%P;
                return;
            }
            int mid=l+r>>1;
            if(pos<=mid) ist(ls,l,mid,pos,val);
            else ist(rs,mid+1,r,pos,val);
            upd(u);
        }
        query qry(int u,int l,int r,int lp,int rp){
            if(lp<=l && r<=rp) return d[u];
            int mid=l+r>>1;
            query ret,tmp;
            if(lp<=mid) ret=qry(ls,l,mid,lp,rp);
            if(rp>mid){
                tmp=qry(rs,mid+1,r,lp,rp);
                if(tmp.sz>ret.sz) ret=tmp;
                else if(tmp.sz==ret.sz) ret.sum=(ret.sum+tmp.sum)%P;
            }
            return ret;
        }
    public:
        void ist(int pos,query &val){ist(1,1,maxr,pos,val);}
        query qry(int rp){
            if(rp<=0) return query(0,0);
            return qry(1,1,maxr,1,rp);
        }
#undef ls
#undef rs
}T;
inline query DP(){
    query ret,tmp;
    for(int i=1;i<=n;++i){
        tmp=T.qry(r[i]-1);
        if(tmp.sz==0) tmp.sum=1;
        ++tmp.sz;
        if(ret.sz<tmp.sz) ret=tmp;
        else if(ret.sz==tmp.sz) ret.sum=(ret.sum+tmp.sum)%P;
        T.ist(r[i],tmp);
    }
    return ret;
}
int main(){
#ifdef DEBUG
    setIO("b");
#endif
    int type;
    read(n),read(type);
    for(int i=1;i<=n;++i){
        read(r[i]);
        maxr=max(maxr,r[i]);
    }
    query ans=DP();
    write(ans.sz,'\n');
    if(type) write(ans.sum);
    return 0;
}

幻魔皇

思路

• 显然每一层的点数是斐波那契数列的一项，那$n=5000$节点数就上天了，没法做，肯定是公式题...
• 观察发现，这个斐波那契树有一个非常神奇的性质，即每一个以相同颜色节点为根的子树都同构；
• 对于神奇节点对$(u,v)$，有两种情况：
• $lca(u,v)$是白点；
  
  1. 对于这种情况，观察知，$lca$显然是$u,v$中的一个；
  2. 那么这种情况的总数就是有至少$i+1$层的白点为根的子树数量乘上白点为根的树第$i+1$层的白点总数；
• $lca(u,v)$是黑点：
  
  1. 由于黑点有两个儿子，一个白的一个黑的，$u,v$只能分别在这两个儿子的子树里，我们由枚举路径总长度变为枚举$u,v$到$lca(u,v)$的两个儿子的距离；
  2. $ans_{i+j}$也就是一个至少有$i+j$层的黑点为根的子树乘上白点为根的树第$i$层的白点数乘上黑点为根的树第$j$层的白点数；
• 对于白点总数和子树个数，是个斐波那契数列，我们递推预处理出来即可，复杂度$O(n^2)$。

代码

#include <cstdio>
#include <algorithm>
using std::max;
const int MAXN=5005,P=123456789;
int n;
long long ans[MAXN<<1];
long long wht[MAXN],blk[MAXN];
long long sumw[MAXN],sumb[MAXN];
inline void pre_cal(){
    wht[1]=1,wht[2]=0,wht[3]=1;
    for(int i=4;i<=n;++i)
        wht[i]=(wht[i-1]+wht[i-2])%P;
    blk[1]=0,blk[2]=1;
    for(int i=3;i<=n;++i)
        blk[i]=(blk[i-1]+blk[i-2])%P;
    for(int i=1;i<=n;++i){
        sumw[i]=(sumw[i-1]+wht[i])%P;
        sumb[i]=(sumb[i-1]+blk[i])%P;
    }
}
inline void solve(){
    for(int i=1;i<=n;++i)
        ans[i]=sumw[n-i]*wht[i+1]%P;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            ans[i+j]=(ans[i+j]+sumb[n-max(i,j)]*wht[i]%P*blk[j]%P)%P;
    }
}
int main(){
    scanf("%d",&n);
    pre_cal();
    solve();
    for(int i=1,lim=n<<1;i<=lim;++i)
        printf("%d ",ans[i]);
    return 0;
}