[关闭]
@KirinBill 2017-09-18T04:17:39.000000Z 字数 3206 阅读 603

2017.9.9 NOIP模拟赛

题解 套题

目录


1. 兔子序列

rmH1L.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  4. using std::string;
  5. inline void setIO(string file){
  6. string in=file+".in",out=file+".out";
  7. freopen(in.c_str(),"r",stdin);
  8. freopen(out.c_str(),"w",stdout);
  9. }
  10. template<typename type>
  11. inline void read(type &x){
  12. x=0;
  13. int pm=1; char c;
  14. do{c=getchar();}while(!isdigit(c) && c!='-');
  15. c=='-' ? pm=-1:x=c^'0';
  16. while(c=getchar(),isdigit(c))
  17. x=x*10+(c^'0');
  18. x*=pm;
  19. }
  20. template<typename type>
  21. void write(type x,char c=0){
  22. if(x<0) putchar('-'),x=-x;
  23. if(x>9) write(x/10);
  24. putchar(x%10|'0');
  25. if(c) putchar(c);
  26. }
  27. #include <queue>
  28. #include <algorithm>
  29. using std::queue;
  30. using std::min;
  31. const int MAXN=100005,P=1e9+7;
  32. inline int cal_ans(int n,int m){
  33. static int fib[MAXN];
  34. static queue<int> die;
  35. while(die.size()) die.pop();
  36. fib[0]=fib[1]=1;
  37. die.push(fib[0]);
  38. for(int i=2,lim=min(n,m);i<=lim;++i){
  39. fib[i]=(fib[i-1]+fib[i-2])%P;
  40. die.push(fib[i-2]);
  41. }
  42. for(int i=m+1;i<=n;++i){
  43. fib[i]=((fib[i-1]+fib[i-2])%P-die.front()+P)%P;
  44. die.pop();
  45. die.push(fib[i-2]);
  46. }
  47. return fib[n];
  48. }
  49. int main(){
  50. setIO("rabbit");
  51. int T;
  52. read(T);
  53. int n,m;
  54. while(T--){
  55. read(n),read(m);
  56. write(cal_ans(n,m),'\n');
  57. }
  58. return 0;
  59. }

2. 完整的海报

GJw9a.png

思路


3. 互质统计

rmrbW.png

思路

代码

  1. #include <cstdio>
  2. const int MAXN=1e7+5;
  3. int phi[MAXN];
  4. long long ans[MAXN];
  5. inline void Euler_phi(){
  6. static int prm[MAXN];
  7. static bool notP[MAXN];
  8. notP[1]=true,phi[1]=1;
  9. for(int i=2;i<MAXN;++i){
  10. if(!notP[i]){
  11. prm[++prm[0]]=i;
  12. phi[i]=i-1;
  13. }
  14. for(int j=1,tmp;j<=prm[0] && i*prm[j]<MAXN;++j){
  15. tmp=i*prm[j];
  16. notP[tmp]=true;
  17. if(i%prm[j]==0){
  18. phi[tmp]=prm[j]*phi[i];
  19. break;
  20. }
  21. else phi[tmp]=phi[i]*phi[prm[j]];
  22. }
  23. }
  24. }
  25. inline void pre_tab(){
  26. Euler_phi();
  27. for(int i=1;i<MAXN;++i){
  28. ans[i]=ans[i-1];
  29. ans[i]+= i&1 ? phi[i]>>1:phi[i];
  30. }
  31. }
  32. int main(){
  33. freopen("count.in","r",stdin);
  34. freopen("count.out","w",stdout);
  35. pre_tab();
  36. int T;
  37. scanf("%d",&T);
  38. int n;
  39. while(T--){
  40. scanf("%d",&n);
  41. printf("%lld\n",ans[n]);
  42. }
  43. return 0;
  44. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注