Contest 1
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Contest 1,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4109字,纯文字阅读大概需要6分钟。
内容图文
![Contest 1](/upload/InfoBanner/zyjiaocheng/1282/cbc0f7b37fa34bc9b8ae12e44d219a22.jpg)
A:注意到模数是要求lcm的数的倍数,直接先取模就可以了。考场脑抽,对其质因数分解判了一下每个因子有没有,当然也行。
![技术分享图片](/img/jia.gif)
![技术分享图片](/img/jian.gif)
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> usingnamespace std; int read() { int x=0,f=1;char c=getchar(); while (c<‘0‘||c>‘9‘) {if (c==‘-‘) f=-1;c=getchar();} while (c>=‘0‘&&c<=‘9‘) x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define P 1234567890 int a=246913578; int a2,a9,a3607,a3803,aP; int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int main() { freopen("lcm.in","r",stdin); freopen("lcm.out","w",stdout); char c=getchar(); while (c>=‘0‘&&c<=‘9‘) { int x=c^48; a2=x&1; a9=(a9*10+x)%9; a3607=(a3607*10+x)%3607; a3803=(a3803*10+x)%3803; aP=(10ll*aP+x)%P; c=getchar(); } if (a2) aP=2ll*aP%P; if (a3607) aP=3607ll*aP%P; if (a3803) aP=3803ll*aP%P; if (a9) if (a9%3==0) aP=3ll*aP%P; else aP=9ll*aP%P; cout<<aP; return0; }
B:学傻系列。排列计数一般将数从小到大加进去考虑,于是设f[i][j]为i个数的排列其中有j个位置不合法的方案数,考虑每次往里加i+1,可以发现如果在上升段每个数的左侧或下降段每个数的右侧插入会使不合法位置--,反之则++。特殊情况是开头的下降段和结尾的上升段,于是增加二维01记录。正解考虑最大值出现位置于是变成了优美的卷积形式。当然原题n只有1000我的辣鸡dp也能A了。
![技术分享图片](/img/jia.gif)
![技术分享图片](/img/jian.gif)
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> usingnamespace std; int read() { int x=0,f=1;char c=getchar(); while (c<‘0‘||c>‘9‘) {if (c==‘-‘) f=-1;c=getchar();} while (c>=‘0‘&&c<=‘9‘) x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 1010 int n,m,f[N][N][2][2]; //head tail up 0 down 1void inc(int &x,int y){x+=y;if (x>=m) x-=m;} int main() { freopen("irrev.in","r",stdin); freopen("irrev.out","w",stdout); n=read(),m=read(); if (n==1) {cout<<1;return0;} if (n==2) {cout<<2;return0;} f[3][0][1][0]=2,f[3][0][0][1]=2,f[3][1][0][0]=1,f[3][1][1][1]=1; for (int i=3;i<n;i++) for (int j=0;j<=i-2;j++) for (int x=0;x<=1;x++) for (int y=0;y<=1;y++) { if (x==0) inc(f[i+1][j][1][y],f[i][j][x][y]); else { inc(f[i+1][j+1][1][y],f[i][j][x][y]); inc(f[i+1][j][0][y],f[i][j][x][y]); } if (y==1) inc(f[i+1][j][x][0],f[i][j][x][y]); else { inc(f[i+1][j+1][x][0],f[i][j][x][y]); inc(f[i+1][j][x][1],f[i][j][x][y]); }//head&&tail&&special checkif (j) inc(f[i+1][j-1][x][y],1ll*f[i][j][x][y]*j%m); inc(f[i+1][j+1][x][y],1ll*f[i][j][x][y]*(i-1-j-(x==1)-(y==0))%m); } cout<<((f[n][0][0][0]+f[n][0][0][1])%m+(f[n][0][1][0]+f[n][0][1][1])%m)%m; return0; }
C:找规律容易发现系数是组合数。(伪)扩展lucas或者质因数分解都可以。
![技术分享图片](/img/jia.gif)
![技术分享图片](/img/jian.gif)
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> usingnamespace std; int read() { int x=0,f=1;char c=getchar(); while (c<‘0‘||c>‘9‘) {if (c==‘-‘) f=-1;c=getchar();} while (c>=‘0‘&&c<=‘9‘) x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 1050 #define P 100007 int n,m,a[N],f[2][N],C[N],C0[2][N],fac[2][N],inv[2][N]; int lucas(int x,int n,int m,int p) { if (m>n) return0; if (n<p) return 1ll*fac[x][n]*inv[x][n-m]%p*inv[x][m]%p; return 1ll*lucas(x,n%p,m%p,p)*lucas(x,n/p,m/p,p)%p; } void getC(int x,int p) { fac[x][0]=1;for (int i=1;i<p;i++) fac[x][i]=1ll*fac[x][i-1]*i%p; inv[x][0]=inv[x][1]=1;for (int i=2;i<p;i++) inv[x][i]=p-1ll*(p/i)*inv[x][p%i]%p; for (int i=1;i<p;i++) inv[x][i]=1ll*inv[x][i-1]*inv[x][i]%p; for (int i=0;i<=n;i++) C0[x][i]=lucas(x,m,i,p); } int getinv(int x,int y) { for (int i=1;i<y;i++) if (1ll*i*x%y==1) return i; } void crt() { int a=getinv(97,1031),b=getinv(1031,97); for (int i=0;i<=n;i++) C[i]=(1ll*C0[0][i]*1031%P*b%P+1ll*C0[1][i]*97%P*a%P)%P; } int main() { freopen("difer.in","r",stdin); freopen("difer.out","w",stdout); n=read(),m=read(); for (int i=1;i<=n;i++) a[i]=read(); getC(0,97);getC(1,1031); crt(); for (int i=0;i<=n;i++) if (i&1) C[i]=P-C[i]; for (int i=1;i<=n;i++) { int x=0; for (int j=i;j>=1&&i-j<=m;j--) x=(x+1ll*C[i-j]*a[j]%P)%P; cout<<x<<endl; } return0; }
result:300 rank1
原文:https://www.cnblogs.com/Gloid/p/9734755.html
内容总结
以上是互联网集市为您收集整理的Contest 1全部内容,希望文章能够帮你解决Contest 1所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。