2017.10.14 NOIP模拟赛

题解 套题

目录

• 2017.10.14 NOIP模拟赛
  • 次芝麻
    • 思路
    • 代码
  • 喝喝喝
    • 思路
    • 代码
  • 长寿花
    • 思路
    • 代码

次芝麻

思路

• 很妙的题，考虑我们每次操作时需要关注哪个最小，很不方便，我们进行一下转换；
• 不妨设$x<y$，则操作一次就是$x*=2,y-=x$；
• 若设$sum=x+y$，考虑以下式子$x=x \times 2 \bmod{sum},y=y \times 2 \bmod{sum}$；
• 显然第一个式子就等于$x*=2$，但是第二个我们需要化简一下：$原式=(y+y)\bmod{x+y}=y+y-x-y=y-x$；
• 发现了吗，每次操作就相当于$x,y$都乘$2$再模$sum$，所以快速幂就好了。

代码

#include <cstdio>
#include <algorithm>
using std::min;
inline int pow(int x,int y,int p){
    int ret=1;
    for(;y;y>>=1,x=(long long)x*x%p){
        if(y&1) ret=(long long)ret*x%p;
    }
    return ret;
}
int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    int sum=n+m;
    printf("%d",min((long long)n*pow(2,k,sum)%sum,(long long)m*pow(2,k,sum)%sum));
    return 0;
}

喝喝喝

思路

• 显然，对于每个$x$，我们只考虑最小的符合条件的$y$即可，因为若不考虑其它$x$，以$x$为左端点的合法区间右端点只能到$y-1$，后面即使有合法的$y$也没用了；
• 怎么求这个$y$呢？我们把那个式子放到模$a_y$的意义下看：$a_x \equiv k \pmod{a_y}$，所以有$a_x-k \equiv 0 \pmod{a_y}$，显然$a_y \mid a_x-k$；
• 那么对于每个$a_x$，我们找一下$a_x-k$的约数就好了；
• 至于求最小的$y$也很简单，注意到$a$的范围很小，可以用数组存一下$a_i$的位置；
• 我们倒着扫，分解$a_x-k$的约数，之后用$a_x$更新一下$pos$数组即可；
• 但是还要特判两种情况：
  
  1. $a_x-k<0$，那么这样的$y$不存在，将其$y$值设为$n+1$即可，为什么不设为别的值？后面会讲；
  2. $a_x-k=0$，那么$\forall y \in [x+1,n]$都满足要求，我们找一个$x$之后第一个大于$k$的$a_y$即可；
• 那么对于每个$x$，以其为左端点的合法区间还要考虑到是否存在$x'>x,y'<y$的情况；
• 其实，这个只要对$y$求一个后缀最小值即可，每一个$x$的贡献便是$miny(x)-x$。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using std::min;
const int MAXN=1e5+5;
int n,k;
int a[MAXN],pos[MAXN],nex[MAXN];
inline int find(int tmp,int pos){
    if(tmp<0) return n+1;
    else if(tmp==0) return nex[pos];
    int ret=n+1;
    for(int i=1;i*i<=tmp;++i){
        if(tmp%i==0){
            if(i>k) ret=min(ret,::pos[i]);
            if(tmp/i>k) ret=min(ret,::pos[tmp/i]);
        }
    }
    return ret;
}
inline int solve(){
    static int y[MAXN];
    nex[n+1]=n+1;
    for(int i=n;i;--i)
        nex[i]= a[i]>k ? i:nex[i+1];
    memset(pos,0x7f,sizeof(pos));
    for(int i=n;i;--i){
        y[i]=find(a[i]-k,i);
        pos[a[i]]=i;
    }
    long long ret=0;
    for(int i=n,miny=n+1;i;--i){
        miny=min(miny,y[i]);
        ret+=miny-i;
    }
    return ret;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    printf("%lld",solve());
    return 0;
}

长寿花

思路

• 显然组合数学题。。。
• 考虑$50$分状压的话怎么写；
• 首先，求一个$f(i,j)$，表示$i$个格子染$j$种颜色的合法方案数（这里不考虑染了哪$j$种，以及这$j$种怎么排列）；
• 之后设$dp(i,j)$，表示第$i$列染色状态为$j$时，前$i$列的合法方案总数；
• 那么方程很好转移，就是不考虑不合法的减去不合法的；
• 进而我们可以发现，其实这个状态$j$是不需要记录的，因为我们只考虑染了$j$种颜色即可，一定会和上一次的某些重，我们直接算就好了；
• 那么重新定义$j$的含义，变成染了$j$种颜色；
• 首先不考虑不合法的情况，那么$dp(i,j)=A_m^j \times f(a_i,j) \times\sum_{k=1}^{a_{i-1}} dp(i-1,k)$；
• 也就是从总共$m$种颜色里选$j$个形成一个排列的方案数乘上这$j$种颜色按一个排列去染$a_i$个格子的方案数乘上前$i-1$列的总方案数；
• 不合法的情况有哪些，就是第$i$列染了$j$种颜色的方案数（考虑这$j$种颜色的排列）乘上上一列染$j$种颜色的前$i-1$列的总方案数；
• 也就是$dp(i,j)-=A_j^j \times f(a_i,j) \times dp(i-1,j)$；
• 对于第一开始那个$\sum$，我们每次转移一个$i$后维护一下它的和即可。

代码

#include <cstdio>
const int MAXN=1e6+5,MAXA=5005,MAXM=MAXN;
int n,m,P;
int a[MAXN],fac[MAXA],A[MAXM],f[MAXA][MAXA];
//A(i,i)=i!,A(i)=A(m,i)
inline void pre_tab(){
    A[0]=1;
    for(int i=1;i<=m;++i)
        A[i]=(long long)A[i-1]*(m-i+1)%P;
    fac[0]=1;
    for(int i=1;i<MAXA;++i)
        fac[i]=(long long)fac[i-1]*i%P;
    f[0][0]=1;
    for(int i=1;i<MAXA;++i){
        for(int j=1;j<=i;++j)
            f[i][j]=((long long)f[i-1][j]*(j-1)%P+f[i-1][j-1])%P;
    }
}
inline int DP(){
    static int dp[2][MAXA];
    //dp[0/1][0]=sum
    dp[0][0]=1;
    for(int i=1;i<=n;++i){
        dp[i&1][0]=0;
        for(int j=1;j<=a[i];++j){
            dp[i&1][j]=(long long)A[j]*f[a[i]][j]%P*dp[~i&1][0]%P;
            if(j<=a[i-1])
                dp[i&1][j]=(dp[i&1][j]-(long long)fac[j]*f[a[i]][j]%P*dp[~i&1][j]%P+P)%P;
            dp[i&1][0]=(dp[i&1][0]+dp[i&1][j])%P;
        }
    }
    return dp[n&1][0];
}
int main(){
    scanf("%d%d%d",&n,&m,&P);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    pre_tab();
    printf("%d",DP());
    return 0;
}