Beta Round ＃9 (酱油杯noi考后欢乐赛)随机数生成器

题目：http://www.contesthunter.org/contest/Beta%20Round%20%EF%BC%839%20%28%E9%85%B1%E6%B2%B9%E6%9D%AFnoi%E8%80%83%E5%90%8E%E6%AC%A2%E4%B9%90%E8%B5%9B%29/%E9%9A%8F%E6%9C%BA%E6%95%B0%E7%94%9F%E6%88%90%E5%99%A8

题解：这题做的我也是醉了。。。

一阶递推然后还要翻转，那矩阵是不能做了。。。然后发现好像是不可做题。。。简要题解说是循环节？

如果出现以前出现过的显然可以输出ans了，可是模数这么大，如果模数只有100W的话很容易出现，20亿怎么保证会在不超时的情况下重复？

唉？我想到了什么？生日攻击！如果有23个人，那么他们中有同生日的概率超过50%。

然后在hash killer II中，有这样的结论:

生日攻击：如果你在n个数中随机选数，那么最多选√n次就能选到相同的数（不考虑Rp broken)

同样的，这题的Hash值在0到1000000007.

那就要选差不多10^5次

唯一注意的是l要取大，使得方案数超过Mod

否则就不可能有2个数有相同的Hash值

所以我们可以暴力模拟前面的直到出现重复。

代码：

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<string>

#define inf 1000000000

#define maxn 1000000+5

#define maxm 500+100

#define eps 1e-10

#define ll long long

#define pa pair<int,int>

#define for0(i,n) for(int i=0;i<=(n);i++)

#define for1(i,n) for(int i=1;i<=(n);i++)

#define for2(i,x,y) for(int i=(x);i<=(y);i++)

#define for3(i,x,y) for(int i=(x);i>=(y);i--)

#define mod 1000000007

using namespace std;

inline ll read()

{

    ll x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}

    return x*f;

}
int c[maxn];
map<ll,int>mp;

int main()

{

    freopen("input.txt","r",stdin);

    freopen("output.txt","w",stdout);

    ll a=read(),b=read(),m=read(),x=read(),n=read();
    for(ll i=1;i<=n;i++)
    {
        ll y=(a*x+b)%m;x=0;
        for(;y;y/=10)x=10*x+y%10;
        x%=m;
        y=mp[x];
        if(y){printf("%d
",c[y+(n-i+1-1)%(i-1-y+1)+1-1]);return 0;}else c[mp[x]=i]=x;
    }
    cout<<x<<endl;

    return 0;

}