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

一堆憨批题

A:直接倍增即可。离一血差10s，自闭。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<=y;i++)

int n,m,k;
const int N=1e5+1;
int a[N];
int f[N][31];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m>>k;
    rep(i,1,n)a[i]=i;
    rep(i,1,m){int l,r;cin>>l>>r;reverse(a+l,a+r+1);}
    rep(i,1,n)f[i][0]=a[i];
    rep(j,1,30)rep(i,1,n)f[i][j]=f[f[i][j-1]][j-1];
    rep(i,1,n){
        int now=i;
        rep(j,0,30)if(k>>j&1)now=f[now][j];
        cout<<now<<' ';
    }
    return 0;
}

B:考虑正难则反，直接算出来不合法的。
显而易见总方案数为 。
然后矩阵快速幂加速一下就做完了。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<=y;i++)
long long n;
int p,k;
int mul(const int&x,const int&y){return 1ll*x*y%p;}
int qpow(int x,long long y){int res=1;while(y){if(y&1)res=mul(res,x);x=mul(x,x);y>>=1;}return res;}
struct mat{
    mat(){memset(a,0,sizeof(a));}
    int a[101][101];
    int*operator[](int x){return a[x];}
}base,result;
void upd(int&x,const int&y){x+=y;if(x>=p)x-=p;}
void dec(int&x,const int&y){x-=y;if(x<0)x+=p;}
mat mul(mat x,mat y){mat res;rep(i,0,100)rep(j,0,100)rep(k,0,100)upd(res[i][j],mul(x[i][k],y[k][j]));return res;}
mat qpow(mat x,long long t){
    --t;mat res=x;
    while(t){if(t&1)res=mul(res,x);x=mul(x,x);t>>=1;}
    return res;
}
int main(){
#ifdef LOCAL
    freopen("testdata.txt","r",stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>p>>k;
    int all=qpow(2,n-1);
    rep(i,1,100)base[i][i-1]++;
    rep(i,1,k){int x;cin>>x;base[0][x-1]++;}
    dec(all,qpow(base,n)[0][0]);
    cout<<all<<'\n';
    return 0;
}

C:其实你会发现这个本质上是跟一直递增的是一样的。所以考虑它是一直递增的，枚举最大值 。
就做完了。

#include<cstdio>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
const int N=2e7,mod=1e9+7;
void upd(int&x,const int&y){x+=y;if(x>=mod)x-=mod;}
int mul(const int&x,const int&y){return 1ll*x*y%mod;}
int test;
int fac[N],ifac[N];
int qpow(int x,int y){int r=1;while(y){if(y&1)r=mul(r,x);x=mul(x,x),y>>=1;}return r;}
int C(const int&x,const int&y){return mul(fac[x],mul(ifac[y],ifac[x-y]));}
int main(){
    fac[0]=1;rep(i,1,N-1)fac[i]=mul(fac[i-1],i);
    ifac[N-1]=qpow(fac[N-1],mod-2);per(i,N-2,0)ifac[i]=mul(ifac[i+1],i+1);
    for(scanf("%d",&test);test--;){
        int n,m;scanf("%d%d",&n,&m);n^=m^=n^=m;
        int ans=0;rep(i,1,m){upd(ans,C(2*i-2+n-1,n-1));}printf("%d\n",ans);
    }
    return 0;
}