htd1的签到题教程 I 题解
可以发现 \(\text{f}_n\) 只由 \(\text{f}_{n-1}\) 和 \(\text{f}_{n-2}\) 决定，也就是 \(\exists n,m\in \mathbb{N}^*\) 且 \(n\not=m\)，\(\text{f}_{n-1}=\text{f}_{m-1},\text{f}_{n-2}=\text{f}_{m-2}\)，则一定有 \(\text{f}_{n}=\text{f}_{m}\)。
有了上面的结论，我们便可以将 \(\text{f}\) 的相邻两项看成一个整体，由于模数 \(q\) 很小，只有 79，所以互不相同的整体最多只会出现 \(q^2\) 项，显然存在循环节。
故我们可以先暴力查找循环节，对于 \(n\to m\) 中完整的循环可以直接乘算，两头零散的单独计算。
特别注意，如果 \(n,m\) 都在同一个循环中需要特判。
参考代码：
def Next(x,a,b):return [x[1],(x[0]*a+x[1]*b)%q]
n,m=map(int,input().split())
a,b,f1,f2=map(int,input().split())
q=79;n-=1;m-=1
F=[[f1,f2]]
now=Next([f1,f2],a,b)
while now not in F:F=F+[now]now=Next(now,a,b)
sum=0
for i in F:sum+=i[0]
l=len(F)
p=(int(m/l)-int((n+l-1)/l))
if p>0:ans=p*sum%qfor i in range(n%l,l):ans+=F[i][0]for i in range(m%l+1):ans+=F[i][0]
else:ans=0for i in range(n%l,m%l+1):ans+=F[i][0]
ans%=q
print(ans)
htd1的位运算教程 题解
观察式子 \(\text{a}_\text{i}+\text{a}_\text{j}=\text{a}_\text{i}\&\text{a}_\text{j}+\text{a}_\text{i}\mid\text{a}_\text{j}+\text{a}_\text{i}\oplus\text{a}_\text{j}\)。
容易发现和位运算基础等式中的 \(\text{a}_\text{i}+\text{a}_\text{j}=\text{a}_\text{i}\&\text{a}_\text{j}+\text{a}_\text{i}\mid\text{a}_\text{j}\) 仅仅相差一项 \(\text{a}_\text{i}\oplus\text{a}_\text{j}\)
且根据异或性质 \(\text{a}_\text{i}\oplus\text{a}_\text{j}=0\) 当且仅当 \(\text{a}_\text{i}=\text{a}_\text{j}\) 。
所以问题转化为有多少个不同的区间使其内数字都相同。
对于一段长度为 \(x\) 的相同数字组成的区间，很容易发现可以找到 \(\frac{x\times(x+1)}{2}\) 个不同的区间。
所以对数组扫一遍即可，复杂度 \(\mathcal{O}(n)\) 。
参考代码：
#include<bits/stdc++.h>
using namespace std;
class SimpleRNG {unsigned int seed;
public:SimpleRNG(unsigned int s){seed=s;}unsigned int next() {seed=(1664525*seed+1013904223)%4294967296;return seed;}unsigned int next(unsigned int maxx) {return next()%(maxx+1);}
};
vector<int>input(int n,int seed,int maxx){SimpleRNG Input(seed);vector<int>res; res.reserve(n);while(n--){res.emplace_back(Input.next(maxx));}return res;
}
int n,seed,maxx,ans;
vector<int>a;
int main(){while(scanf("%d%d%d",&n,&seed,&maxx)!=EOF){a=input(n,seed,maxx);a.push_back(-1);ans=0;for(int i=0;i<a.size()-1;i++){int now=a[i],num=1;while(a[i+1]==now)i++,num++;ans+=(num+1)*num/2;} printf("%d\n",ans);}return 0;
}