题解 P1573 【栈的操作】

王奕瑜 · 2020-02-13 10:55:08 · 题解

算法：找规律（这是啥算法）

• 思路其他人已经讲的很明白了，注意N≤2*10^9，不能用O(n^2)的递推方法，于是——找规律（注意我是从n=0开始的）：

  0,1,3,5,9,13,17,......

• 表示没有发现啥规律。突然想到可以看一下前后两项的差（其实早就想到了）：

  1,2,2,4,4,4,8,......
• 原来还是有规律的，那么代码不就写出来了吗？
• 看了一下其它的题解，决定发一篇比较清（fan）新（suo）的代码：

  
  #include <cstdio>
  using namespace std;
  void in(long long &n)//快读，注意long long
  {
  n=0;long long f=1;char c=getchar();
  while (c<'0'||'9'<c){if (c=='-')f*=-1;c=getchar();}
  while ('0'<=c&&c<='9'){n=n*10+(c-'0');c=getchar();}
  n*=f;
  }
  const long long M=1000007; //定义Mod
  int main()
  {
  long long n;
  in(n); //读入
  long long ans=0;
  long long i,j;//此时的数为j,个数为i
  for (i=1,j=1;n>=i;n-=i,i++,j=(j*2)%M)//每次n-i,i+1,j*2
      ans=(ans+i*j)%M; //更新ans
  printf ("%lld",(ans+n*j)%M); //注意最后要把剩余的加上
  return 0;
  }