谢谢，你关注的鸽子博主更新了。
上赛季末段没能忍住网瘾， 转生成 ACMer 了
和队友一起拿了块邀请赛金牌和省赛冠军，下半年区域赛不想拖后腿所以还是得努努力啊。
但是因为博主还要跑科研实验 以及 机器人比赛的事情，所以大概一天只能看几个题
下列列出的 √ 为自己想出来的，× 为看了题解。
[√] 不知名题
求 \(p_i = (a p_{i - 1} ^ 2 + b p_{i - 1} + c) \mod m + \lfloor \frac{p_{i - 1}}{2} \rfloor\)
\(p_0 = k\) 时，求 \(p_{T}\)
\(k,T \leq 1e18\)
\(a,b,c,m \leq 5e5\)
看这个 \(m\) 显然就很能操作啊。
思考 \(p_i \leq 2m\) 时显然最后范围也在 \(2m\) 中，\(m\) 不大显然可以处理值域上的步数信息。
\(p_i > 2m\) 时，理论上 \(log_2{m}\) 步就进入范围了。
所以直接就倍增即可。
点击查看代码
//明剑照霜，秋风走马
#include<bits/stdc++.h>
#define ll long long
#define M 600005
ll mod,a,b,c;
int T;
int A[M * 2][80];
ll mul[80];
signed main(){
// freopen("5.in","r",stdin);
// freopen("5.out","w",stdout);
scanf("%lld%lld%lld%lld",&mod,&a,&b,&c);
a = a % mod;
b = b % mod;
c = c % mod;
mul[0] = 1;
for(int i = 1;i <= 60;++i)mul[i] = mul[i - 1] * 2;
for(int i = 0;i <= 2 * mod;++i){A[i][0] = (1ll * a * (i % mod) * (i % mod) % mod+ 1ll * b * (i % mod) % mod + c) % mod + i / 2;}
for(int t = 1;t <= 60;++t){
for(int i = 0;i <= 2 * mod;++i){
A[i][t] = A[A[i][t - 1]][t - 1];
}
}
scanf("%lld",&T);
while(T -- ){
ll k,y;
scanf("%lld%lld",&k,&y);
while((k > 2 * mod) && y){--y;k = (1ll * a * (k % mod) * (k % mod) % mod + 1ll * b * (k % mod) % mod + c) % mod + k / 2;}
if(y == 0){std::cout<<k<<"\n";continue;}
ll now = k;
for(int t = 60;t >= 0;--t){if(y < 0)return 0;if(y >= mul[t]){now = A[now][t];y -= mul[t];}if(!y)break;}
std::cout<<now<<"\n";
}
}
另外 ll 求余 int 居然是 UB 吗，，，，
标签：24,int,ll,lld%,2m,mul,合集,赛训,mod From： https://www.cnblogs.com/dixiao/p/18279702