[关闭]
@KirinBill 2017-10-15T15:27:01.000000Z 字数 3025 阅读 1127

2017.10.14 NOIP模拟赛

题解 套题

目录


次芝麻

OekZ6.png

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. using std::min;
  4. inline int pow(int x,int y,int p){
  5. int ret=1;
  6. for(;y;y>>=1,x=(long long)x*x%p){
  7. if(y&1) ret=(long long)ret*x%p;
  8. }
  9. return ret;
  10. }
  11. int main(){
  12. int n,m,k;
  13. scanf("%d%d%d",&n,&m,&k);
  14. int sum=n+m;
  15. printf("%d",min((long long)n*pow(2,k,sum)%sum,(long long)m*pow(2,k,sum)%sum));
  16. return 0;
  17. }

喝喝喝

OeVT7.png

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cstring>
  4. using std::min;
  5. const int MAXN=1e5+5;
  6. int n,k;
  7. int a[MAXN],pos[MAXN],nex[MAXN];
  8. inline int find(int tmp,int pos){
  9. if(tmp<0) return n+1;
  10. else if(tmp==0) return nex[pos];
  11. int ret=n+1;
  12. for(int i=1;i*i<=tmp;++i){
  13. if(tmp%i==0){
  14. if(i>k) ret=min(ret,::pos[i]);
  15. if(tmp/i>k) ret=min(ret,::pos[tmp/i]);
  16. }
  17. }
  18. return ret;
  19. }
  20. inline int solve(){
  21. static int y[MAXN];
  22. nex[n+1]=n+1;
  23. for(int i=n;i;--i)
  24. nex[i]= a[i]>k ? i:nex[i+1];
  25. memset(pos,0x7f,sizeof(pos));
  26. for(int i=n;i;--i){
  27. y[i]=find(a[i]-k,i);
  28. pos[a[i]]=i;
  29. }
  30. long long ret=0;
  31. for(int i=n,miny=n+1;i;--i){
  32. miny=min(miny,y[i]);
  33. ret+=miny-i;
  34. }
  35. return ret;
  36. }
  37. int main(){
  38. scanf("%d%d",&n,&k);
  39. for(int i=1;i<=n;++i)
  40. scanf("%d",&a[i]);
  41. printf("%lld",solve());
  42. return 0;
  43. }

长寿花

Oet5T.png
OeJqs.png

思路

代码

  1. #include <cstdio>
  2. const int MAXN=1e6+5,MAXA=5005,MAXM=MAXN;
  3. int n,m,P;
  4. int a[MAXN],fac[MAXA],A[MAXM],f[MAXA][MAXA];
  5. //A(i,i)=i!,A(i)=A(m,i)
  6. inline void pre_tab(){
  7. A[0]=1;
  8. for(int i=1;i<=m;++i)
  9. A[i]=(long long)A[i-1]*(m-i+1)%P;
  10. fac[0]=1;
  11. for(int i=1;i<MAXA;++i)
  12. fac[i]=(long long)fac[i-1]*i%P;
  13. f[0][0]=1;
  14. for(int i=1;i<MAXA;++i){
  15. for(int j=1;j<=i;++j)
  16. f[i][j]=((long long)f[i-1][j]*(j-1)%P+f[i-1][j-1])%P;
  17. }
  18. }
  19. inline int DP(){
  20. static int dp[2][MAXA];
  21. //dp[0/1][0]=sum
  22. dp[0][0]=1;
  23. for(int i=1;i<=n;++i){
  24. dp[i&1][0]=0;
  25. for(int j=1;j<=a[i];++j){
  26. dp[i&1][j]=(long long)A[j]*f[a[i]][j]%P*dp[~i&1][0]%P;
  27. if(j<=a[i-1])
  28. dp[i&1][j]=(dp[i&1][j]-(long long)fac[j]*f[a[i]][j]%P*dp[~i&1][j]%P+P)%P;
  29. dp[i&1][0]=(dp[i&1][0]+dp[i&1][j])%P;
  30. }
  31. }
  32. return dp[n&1][0];
  33. }
  34. int main(){
  35. scanf("%d%d%d",&n,&m,&P);
  36. for(int i=1;i<=n;++i)
  37. scanf("%d",&a[i]);
  38. pre_tab();
  39. printf("%d",DP());
  40. return 0;
  41. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注