| 题目名称 | 2511. 学姐的巧克力盒 |
|---|---|
| 输入输出 | chocolatebox.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 前鬼后鬼的守护
于2016-10-20加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：47， 提交：292， 通过率：16.1% | ||||
 zbw001 |
100 | 3.609 s | 51.32 MiB | C++ |
|
zbw001 |
100 | 3.978 s | 51.56 MiB | C++ |
|
zbw001 |
100 | 4.018 s | 51.32 MiB | C++ |
 tututu |
100 | 4.231 s | 45.11 MiB | C++ |
|
tututu |
100 | 4.294 s | 45.11 MiB | C++ |
 kito |
100 | 4.339 s | 61.33 MiB | C++ |
 FoolMike |
100 | 5.071 s | 171.95 MiB | C++ |
 Hero_of_Someone |
100 | 5.185 s | 156.85 MiB | C++ |
|
zbw001 |
100 | 5.329 s | 55.95 MiB | C++ |
 zyx |
100 | 5.341 s | 87.10 MiB | C++ |
| 本题关联比赛 | |||
| NOIP模拟赛by mzx Day2 | |||
| 关于 学姐的巧克力盒 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @scpointer :
膜拜神犇的代码，不过这个做法似乎还是会卡常 | ||||
|
在这里表达我深深的歉意QAQ
毁了两个大神两节课QAQ ……  半汪
2016-10-27 20:46
14楼
| ||||
|
本题的难度应该不止一星，毕竟裸的剩余定理就3星（剩余定理3星其实也有点太高了……）。
kito
2016-10-22 07:38
13楼
| ||||
|
回复 @Hzoi_AntiLeaf :
ysf大神完全可以写树套树主席树吗~~  _Itachi
2016-10-21 21:17
12楼
| ||||
|
真是醉了。。
这个题明明是考查我们各种数论的。。前6个点应该线段树维护区间乘积。 后4个点应该处理逆元（前6个点不行，因为p1和p2不一定与我们维护的数互质） 而且最后3个点由于p1与p2不是质数，所以必须用中国单身狗定理来处理逆元。。 然而，我最后一个点996242 个询问只有一个不对，一个啊！！！ 当我打表过了以后，我点开另一个过了的大神的代码一看：天哪！ 没有两个程序，没有逆元，没有中国单身狗定理，有的只是前6个点的做法：线段树维护区间乘积，但是， 但是这位大神居然用了ztw线段树然后+快读+快写+卡常卡过了！！！ 真是跪了。。好好地一道数论题输给了常数，还不知道有一个询问是怎么错的。。 最后，希望大神帮我看看我那个询问为什么不对。。 好吧，我知道了，我开了三个数组存逆元（p2的三个因数），但我只把一个的下标为0的初始化为了1，又智障了。。 | ||||
|
回复 @紅蓮之心熾熱_血瞳洞穿無盡陰暗 :
那啥 我代码里不是zkw线段树 不是所有非递归的线段树处理的东西都是zkw线段树 虽然是卡常，这个做法还是讲道理的，我看来不比中国剩余定理做差 算法是这样的，首先对于线段树每个节点(flo,l,r)是第flo层的表示[l,r]区间的节点 设mid=(l+r)/2，a[]为输入的数组，记录下a[mid]一直往左边乘到a[l]的值，和a[mid+1]一直往右边乘到a[r]的值 这样对于一个询问的区间[gl,gr]只要找到一个区间[l,r]满足l<=gl<=mid<gr<=r就可以只做一次乘法就算出答案 整个算法乘法和取模的次数是严格(nlogn+m) 一共是2100万次 你可以数数你的扩展欧几里得和后面中国剩余定理的乘法和取模次数一共有多少次 这个常数完全赶得上一个log (最后我有点好奇后面两位的代码和跑出来的时间是怎么过的  scpointer
2016-10-21 20:59
9楼
| ||||
|
回复 @scpointer :
当然，无论什么做法，能过就是好算法，而且你的做法确实很有道理，这点我服，而且考试时当然是做法越简单越易实现越好，从这点看你的代码好得多。 我发评论只是为了宣泄下自己的痛苦，毕竟我太辣鸡了。。 _Itachi
2016-10-21 20:59
8楼
| ||||
|
回复 @Mike is Fool :
表示严重怀疑十多秒的是偷偷把时限放大过了再把时限改回去的。。 _Itachi
2016-10-21 20:40
7楼
| ||||
|
回复 @Mike is Fool :
你以为非递归线段树就能不T吗...... | ||||
AntiLeaf【题目描述】
学姐得到了一些萨尔那加神器碎片，对于她来说，这些超次元的神器碎片最合适的用途就是：装巧克力，然后送给学长。
学姐拥有n种萨尔那加神器碎片，每个碎片都是一个容器，第i个碎片有ai个空槽，她可以通过俄罗斯套娃娃这样的方式把一些神器碎片组装起来，装巧克力的步骤是这样的，她首先在第一个容器的每个空槽上装上一颗巧克力，然后将第一个容器复制若干份，在第二个容器的每个空槽上装上一个第一个容器，将第二个容器复制若干份放进第三个容器……以此类推。
现在学姐想知道如果选取编号为某个连续区间的一些容器进行组装，那么最终组装出的容器能放多少颗巧克力？由于答案可能很大，你需要将它对p1取模。
当然学姐也考虑到只吃一种巧克力的话肯定是会吃腻的，现在上有K种巧克力，她想问你在上一段的情况下，最终能组装出多少种容器？由于答案可能很大，你需要将它对p2取模。
提示：两个容器不同当且仅当它们某个空槽放的次级容器是不同的，两个一级容器（即直接用来装巧克力的容器）不同当且仅当它们某个空槽放的巧克力种类不同。注意，在容器自我复制的时候紫萱学姐可以指定它复制出的种类，也就是复制出来的容器可能与原容器不同。
【输入格式】
输入数据第一行为五个非负整数n，m，k，p1，p2，m为学姐询问的总次数，其他意义如题目所示。
接下来一行为n个正整数，第i个数代表ai。
接下来m行每行三个正整数ty，l，r。ty∈{1,2}，代表询问种类，询问区间为[l,r]，数据保证l≤r。
此外，若p1为0那么代表数据中不存在第一种询问，p2同理。
【输出格式】
共m行，每行一个非负整数，代表询问的答案。
【样例输入】
3 2 2 9 7 2 2 2 1 1 3 2 1 2
【样例输出】
8 2
【提示】
样例中第一个询问三个容器嵌套在一起一共有8个空位。
第二个询问第一个容器有四种（两个空位，每个空位可以放两种巧克力），第二个容器有16种，对7取模之后答案为2
【19:18更新：数据范围中k的范围】
【来源】
mzx