MicDZ's blog

比赛地址分别为:

中秋节欢乐赛DIV1

中秋节欢乐赛DIV2

所有比赛标程、数据都放置在了Github

DIV1

作业计数

小凡一门学课的作业不做怒气总值增加bb,那么aa门作业不做怒气值即为a×ba\times b,答案为对mm取膜的结果。

数据范围为1a,b,m10181\leq a,b,m\leq 10^{18},此时你发现a×ba\times b会直接炸int。所以需要一些玄学的优化。

Ps:很抱歉,这题没给部分分。

方法一

使用自带高精度的python解决问题

1
2
3
4
a=int(input())
b=int(input())
m=int(input())
print(a*b%m)

方法二

使用高精度的乘法和魔法

在这里推荐各位到yali_hzy的博客看看。我就不写了。。

高精取膜的方法为: ab×ab \begin{aligned} a-b\times \lfloor\frac{a}{b}\rfloor \end{aligned}

方法三

用快速乘的方法。

原理类似于卡速米。

1
2
3
4
5
6
7
8
9
10
#define ll long long
ll mul(ll a,ll b,ll m) {
ll ans=0;
while(b) {
if(b&1) b=(b+a)%m;
a=(a+a)%m;
b>>=1;
}
return ans;
}

复杂度为Θ(logb)\Theta(\log b)

月饼采购

这可以算是一个非常经典的题目了,紫书、蓝书上都有。

和作业计数类似的,膜术可以这么算ab×aba-b\times \lfloor\frac{a}{b}\rfloor

那么就可以得到以下推导 ans=i=1nki×ab=n×ki=1ni×ki \begin{aligned} ans&=\sum^{n}_{i=1}k-i\times\lfloor\frac{a}{b}\rfloor\\ &=n\times k-\sum^{n}_{i=1}i\times\lfloor\frac{k}{i}\rfloor \end{aligned} 然后可以从ki\lfloor\frac{k}{i}\rfloor出发,得到答案。

复杂度为Θk\Theta{\sqrt{k}}

分配月饼

Cnm=n!m!(nm)!=i=nmni=1m \begin{aligned} C^m_n&=\frac{n!}{m!(n-m)!}\\ &=\frac{\prod^{n}_{i=n-m}}{\prod^{m}_{i=1}} \end{aligned}

得到了以上的结论后即可做到在Θ(2×m)\Theta(2\times m),的复杂度内求解。

而原题的n2×105n\leq2\times10^5,因此可以通过。

值得一提的是,在做除法意义下的膜法时,需要用到逆元。

DIV2

Ps:早知道就用OI赛制了,这样Imakf就不能AK了。

价格统计

直接依照题意模拟即可,把细节把握好。

月光计算

这是一道非常简单的数学题。

nn行,n1n-1列的星星加上一行不少于1的星星肯定是要大于(n1)2(n-1)^2颗星星的。

{y1=n(n1)+1=n2n+1y2=(n1)2=n22n+1 \left\{ \begin{aligned} y1&=n(n-1)+1=n^2-n+1\\ y2&=(n-1)^2=n^2-2n+1\\ \end{aligned} \right. 所以可以得出y1>y2y1>y2。答案即为n2n^2,不过记得开long long

月饼管理

提示中的数据结构是前缀和。

您可以参考我的这篇文章。

这里就不多累赘了。

 评论