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; }