今天早上学习容斥原理

容斥原理

看上去很简单，实际应用很难想到

下午打题

S+J组

S组 10/400
J组 120/400

S组直接爆炸了

晚自习改题

改题

J组

小H的字符串

这题比较简单，比赛时AC了

S组

幂

这题下午让我思考了好一会，结果只拿了十分

十分伤心

broken_heart:

so，晚上继续解决这题

题目相当简洁，但做起来确实也不容易

可以看出，我们可以把题目中的形式写作递归的形式
我们不妨设
f(n)=n^f(n)
那么记
r=f(n)%p
因此有
f(n)≡r mod p
f(n)-r+1≡1 mod p
f(n)-r+1≡1 mod p
f(n)^phi(p)≡f(n)-r+1 mod p
n^f(n)(n^phi(p)-1)+r≡1 mod p
n^f(n)(n^phi(p)-1)+n^f(n)≡1 mod p
n^(f(n)+phi(n))≡1 mod p

如此迭代，就有以下递归代码