牛客IOI周赛18-提高组题解

A:排列
简单题，我们发现m不大，我们暴力模拟m次翻转过程。
然后我们针对一次的变换求出倍增数组，倍增即可。
复杂度：O(nm+nlogk)
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5;
struct Range{int l,r;}a[15];
int n,m,k,id[N],ans[N],f[N][31];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++)scanf("%d%d",&a[i].l,&a[i].r);
    for(int i=1;i<=n;i++)id[i]=i;
    for(int i=1;i<=m;i++)reverse(id+a[i].l,id+a[i].r+1);
    for(int i=1;i<=n;i++)f[i][0]=id[i];
    for(int kk=1;kk<=30;kk++)for(int i=1;i<=n;i++)f[i][kk]=f[f[i][kk-1]][kk-1];
    for(int i=1,now;i<=n;i++){
        now=i;
        for(int kk=0;kk<=30;kk++)if(k&(1<<kk))now=f[now][kk];
        ans[i]=now;
    }
    for(int i=1;i<=n;i++)printf("%d%c",ans[i]," \n"[i==n]);
    return 0;
}

B:拆分
我们发现不考虑合法不合法的总数是2的n-1次方，很好算。
然后要求至少有一个不是牛妹不喜欢的，这种类型的套路就是正难则反，我们考虑全是牛妹不喜欢的，这个显然可以dp算出。
具体dp的实现过程我们发现转移之间的数的范围都可以接受，可以用矩阵优化，因此我们矩阵乘法来优化dp，注意我们要卡卡常，否则可能会变成90分，具体在矩乘内部，有两点提示提示。
1:我们如果是0就不用继续转移了
2:顺带我们有一些奇特的方法减少下取模次数。
这样就可以通过本题了。
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=105;
int P,m,s,res,mat[61][N][N],dp[N],f[N];LL n;bool usd[N];
LL qpow(LL x,LL y){LL res=1;for(;y;y>>=1,x=(LL)x*x%P)if(y&1)res=(LL)res*x%P;return res;}
struct matrix{
    int a[N][N];
    matrix operator*(matrix &b){
        matrix c;for(int i=0;i<=s;i++)for(int j=0;j<=s;j++)c.a[i][j]=0;
        for(int i=0;i<=s;i++)for(int k=0;k<=s;k++)if(a[i][k])
            for(int j=0;j<=s;j++)c.a[i][j]=(c.a[i][j]+(LL)a[i][k]*b.a[k][j]%P)%P;
        return c;
    }
}ans,base;
int main(){
    scanf("%lld%d%d",&n,&P,&m);res=qpow(2,n-1);
    while(m--){int x;scanf("%d",&x);usd[x]=true;s=max(s,x);}
    s--;for(int i=0;i<s;i++)base.a[i][i+1]=1;
    for(int i=0;i<=s+1;i++)if(usd[i])base.a[i-1][0]=1;
    dp[0]=1;
    for(int i=1;i<=s;i++)for(int j=1;j<=i;j++)if(usd[j])dp[i]=(dp[i]+dp[i-j])%P;
    if(n<=s){printf("%d\n",(res-dp[n]+P)%P);return 0;}
    n-=s;for(int i=0;i<=s;i++)ans.a[0][s-i]=dp[i];
    for(;n;n>>=1,base=base*base)if(n&1)ans=ans*base;
    printf("%d\n",(res-ans.a[0][0]+P)%P);
    return 0;
}

C:山脉
好像是神仙题，看官方题解推出的式子一头雾水。
这里作者考试的时候打表找找组合数的规律就通过了本题。
这种题，打表找找行列中的差值还是会有所收获的，况且这种题的规律通常都在组合数上。
实现过程很简单，线性求fac和ifac，注意要线性，否则不能通过，然后组合数一波就好了。
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1.5e7+5,P=1e9+7;
int fac[N],ifac[N];
LL qpow(LL x,LL y){LL res=1;for(;y;y>>=1,x=(LL)x*x%P)if(y&1)res=(LL)res*x%P;return res;}
int C(int x,int y){return (LL)fac[x]*ifac[y]%P*ifac[x-y]%P;}
int main(){
    int T;scanf("%d",&T);fac[0]=1;
    for(int i=1;i<N;i++)fac[i]=fac[i-1]*(LL)i%P;
    ifac[N-1]=qpow(fac[N-1],P-2);
    for(int i=N-2;~i;i--)ifac[i]=ifac[i+1]*(LL)(i+1)%P;
    while(T--){
        int n,m,ans=0;scanf("%d%d",&n,&m);m--;
        for(int i=1,j=m;i<=n;i++,j+=2)ans=(ans+C(j,m))%P;
        printf("%d\n",ans);
    }
    return 0;
}