出题人题解 | #小y的线段#

原题解链接：https://ac.nowcoder.com/discuss/181037

画出图来，可以发现具有单调性，只要计算出有多少个位置回到了源点就行了。

/*
* @Author: wxyww
* @Date:   2019-01-21 09:11:22
* @Last Modified time: 2019-01-25 18:05:44
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long ll;
const int N = 20000005;
ll read() {
   ll 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*10+c-'0';
      c=getchar();
   }
   return x*f;
}
ll ans[N],f[N];
unsigned int SA, SB, SC;
unsigned int rng61(){
   SA ^= SA << 16;
   SA ^= SA >> 5;
   SA ^= SA << 1;
   unsigned int t = SA;
   SA = SB;
   SB = SC;
   SC ^= t ^ SA;
   return SC;
}
int main() {
   int n = read();
   int now = 1;
   ll mod = read();
    assert(mod >= 1 && mod <= 6662333);
   cin>>SA>>SB>>SC;
   for(int i = 1;i <= n;++i) {
      int x;
      f[i] = n;
      x = rng61() % mod + 1;
      while(now < i && i - now > x) f[now++] = i - 1;
   }
   ll ac = 0;
   ans[n] = -1;
   for(int i = n - 1;i >= 1;--i) {
      ans[i] = ans[f[i]] + f[i] - i + 1;
      ac += ans[i];
      // cout<<ans[i]<<endl;
   }
   cout<<ac;
   return 0;
}
/*
10000000
154442
16546564
14648648
153452546
*/