2017.10.6 NOIP模拟赛

题解 套题

要相信自己，但不要过分相信自己的直觉。

目录

• 2017.10.6 NOIP模拟赛
  • 装备部的难题
    • 思路
    • 代码
  • 尼伯龙根之歌
    • 思路
    • 代码
  • 冰窖之谜
    • 思路
    • 代码

装备部的难题

思路

• 弹性碰撞类型的题，按照套路，交换速度就是两个人互相穿透过去；
• 那么一个人会撞到的人数就是他之后有多少个速度小于他的或者方向和他相反的；
• 那么如果我们设右为正方向，那方向相反这个就可以忽略了，剩下的就是求逆序对了。

代码

#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 <cstring>
const int MAXN=500005;
int n;
int v[MAXN];
inline void read_chr(char &c){
    do{c=getchar();}while(c!='L' && c!='R');
}
template<class T>
long long mge_sort(int l,int r,T a[]){
    static T tmp[MAXN];
    if(l==r) return 0;
    int mid=l+r>>1;
    long long ret=mge_sort(l,mid,a)+mge_sort(mid+1,r,a);
    int cur=l-1,lp=l,rp=mid+1;
    while(lp<=mid && rp<=r){
        if(a[lp]>a[rp]){
            tmp[++cur]=a[rp++];
            ret+=mid-lp+1;
        }
        else tmp[++cur]=a[lp++];
    }
    while(lp<=mid) tmp[++cur]=a[lp++];
    while(rp<=r) tmp[++cur]=a[rp++];
    memcpy(a+l,tmp+l,(r-l+1)*sizeof(T));
    return ret;
}
int main(){
    setIO("problem");
    read(n);
    char cmd;
    for(int i=1;i<=n;++i){
        read_chr(cmd);
        read(v[i]);
        if(cmd=='L') v[i]=-v[i];
    }
    write(mge_sort(1,n,v));
    return 0;
}

尼伯龙根之歌

思路

• 显然就是一个DAG上的DP，那么我们按拓扑序做就好了，实现方式也有很多；

代码

#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);
}
const int MAXN=100005,MAXM=5*MAXN,P=998244353;
int n,m;
int he[MAXN],dp[MAXN],inD[MAXN],outD[MAXN];
bool noIn[MAXN];
struct line{int to,nex;}ed[MAXM];
inline void addE(int u,int v){
    static int cnt=0;
    ed[++cnt]=(line){v,he[u]};
    he[u]=cnt;
}
inline int pow(int x,int y){
    int ret=1;
    for(;y;y>>=1,x=(long long)x*x%P){
        if(y&1) ret=(long long)ret*x%P;
    }
    return ret;
}
inline int inv(int x){return pow(x,P-2);}
void DAG_DP(int u){
    if(u==n){
        write(dp[u]);
        exit(0);
    }
    int psb=(long long)dp[u]*inv(outD[u])%P;
    for(int i=he[u],v;i;i=ed[i].nex){
        v=ed[i].to;
        dp[v]=(dp[v]+psb)%P;
        if(--inD[v]==0) DAG_DP(v);
    }
}
int main(){
    setIO("deathsong");
    read(n),read(m);
    for(int i=1,u,v;i<=m;++i){
        read(u),read(v);
        addE(u,v);
        ++outD[u],++inD[v];
    }
    for(int i=1;i<=n;++i) noIn[i]=(inD[i]==0);
    dp[1]=1;
    for(int i=1;i<=n;++i){
        if(noIn[i]) DAG_DP(i);
    }
}

冰窖之谜

思路

• 观察到，$n,k$没有同时到达最大值的点，所以这题可能是分类求解的；
• 考虑$n \leq 10^6$时，直接暴力快速幂求就可以了；
• 而$n>10^6$时，发现$k$很小，我们考虑用斐波那契数列的通项公式硬带，用二项式定理展开看看：
  $$\begin{eqnarray*} ans &=& \sum_{i=1}^n f_i^k\\ &=& \sum_{i=1}^n \left\{\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^i+\left(\frac{1-\sqrt{5}}{2}\right)^i\right]\right\}^k\\ &=& \frac{1}{(\sqrt{5})^k}\sum_{i=1}^n \left[\left(\frac{1+\sqrt{5}}{2}\right)^i+\left(\frac{1-\sqrt{5}}{2}\right)^i\right]^k\\ &令&a=\frac{1+\sqrt{5}}{2},b=\frac{1-\sqrt{5}}{2}\\ &=& \frac{1}{(\sqrt{5})^k}\sum_{i=1}^n (a^i+b^i)^k\\ &=& \frac{1}{(\sqrt{5})^k}\times\left[\sum_{i=1}^n \left(\sum_{j=0}^k (-1)^j C_k^j a^{k-j}b^j \right)^i \right]\\ &=& \frac{1}{(\sqrt{5})^k}\times\left[\sum_{j=0}^k (-1)^j C_k^j \times\sum_{i=1}^n (a^{k-j}b^j)^i \right] \end{eqnarray*}$$
• 观察到，$\sum_{i=1}^n (a^{k-j}b^j)^i$是个等比数列前$n$项和（要特判$a^{k-j}b^j=1$的情况），那么就可以在$O(k \log n)$的时间复杂度内求出答案；
• 对于在模$10^9+9$意义下的$\sqrt{5}$，这里可以先暴力跑出来，其实可以用二次剩余定理求，这里就不再赘述。

代码

#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);
}
const int P=1e9+9;
long long n,k;
inline int pow(int x,long long y){
    int ret=1;
    for(;y;y>>=1,x=(long long)x*x%P){
        if(y&1) ret=(long long)ret*x%P;
    }
    return ret;
}
namespace solve1
{
const int MAXN=1e6+5;
int fib[MAXN],sum[MAXN];
inline void pre_tab(){
    fib[1]=1;
    for(int i=2;i<MAXN;++i)
        fib[i]=(fib[i-1]+fib[i-2])%P;
}
inline int solve(){
    for(int i=1;i<=n;++i)
        sum[i]=(sum[i-1]+pow(fib[i],k))%P;
    return sum[n];
}
}
namespace solve2
{
const int sqrt_5=383008016,X=691504013,Y=308495997,MAXK=1e5+5;
int fac[MAXK],fac_inv[MAXK];
inline int inv(int x){return pow(x,P-2);}
inline void pre_tab(){
    fac[0]=1;
    for(int i=1;i<MAXK;++i)
        fac[i]=(long long)fac[i-1]*i%P;
    fac_inv[MAXK-1]=inv(fac[MAXK-1]);
    for(int i=MAXK-2;i>=0;--i)
        fac_inv[i]=(long long)fac_inv[i+1]*(i+1)%P;
}
inline int C(int n,int m){
    return (long long)fac[n]*fac_inv[m]%P*fac_inv[n-m]%P;
}
inline int cal(int a){
    int b=k-a;
    int z=(long long)pow(X,b)*pow(Y,a)%P;
    int ret;
    if(z==1) ret=n%P;
    else{
        ret=(pow(z,n+1)-z+P)%P;
        ret=(long long)ret*inv((z-1+P)%P)%P;
    }
    return (long long)ret*C(k,a)%P;
}
inline int solve(){
    int ret=0;
    for(int i=0;i<=k;++i){
        if(i&1) ret=(ret-cal(i)+P)%P;
        else ret=(ret+cal(i))%P;
    }
    return (long long)ret*pow(inv(sqrt_5),k)%P;
}
}
int main(){
    setIO("ice");
    int T;
    read(T);
    solve1::pre_tab();
    solve2::pre_tab();
    while(T--){
        read(n),read(k);
        if(n<solve1::MAXN) write(solve1::solve(),'\n');
        else write(solve2::solve(),'\n');
    }
    return 0;
}