| 题目名称 | 2582. [HZOI 2016]动物城的鸳鸯蛋传说 |
|---|---|
| 输入输出 | animalcupid.in/out |
| 难度等级 | ★★ |
| 时间限制 | 5000 ms (5 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 _Itachi
于2017-01-08加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：34， 提交：136， 通过率：25% | ||||
 ~玖湫~ |
100 | 11.756 s | 0.55 MiB | C++ |
 BaDBoY |
100 | 11.951 s | 0.55 MiB | C++ |
 Hzoi_QTY |
100 | 11.956 s | 1.18 MiB | C++ |
 Hallmeow |
100 | 12.160 s | 2.08 MiB | C++ |
|
Hallmeow |
100 | 12.175 s | 2.07 MiB | C++ |
 HZOI_蒟蒻一只 |
100 | 12.176 s | 2.08 MiB | C++ |
|
Hzoi_QTY |
100 | 12.353 s | 2.07 MiB | C++ |
|
Hallmeow |
100 | 12.575 s | 1.87 MiB | C++ |
 河北交通广播992大师来了 |
100 | 14.381 s | 0.43 MiB | C++ |
|
河北交通广播992大师来了 |
100 | 14.449 s | 0.43 MiB | C++ |
| 关于 动物城的鸳鸯蛋传说 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
两个模数不一样 wa到死 。。。
（各种SB错误 ） = = ~玖湫~
2017-10-30 15:44
9楼
| ||||
|
神奇的，人品问题。我的取模死活过不去。见鬼了
Hallmeow
2017-07-26 19:09
8楼
| ||||
|
我连bitset清零都不会还在瞎JB用……
HZOI_蒟蒻一只
2017-07-26 16:30
7楼
| ||||
|
这题是网络流?
 chad
2017-03-30 19:07
6楼
| ||||
|
Dinic?
 Shirry
2017-03-23 00:16
5楼
| ||||
|
提示：x[0]不计入x[]数列的前n项,也不可以使用，同样的,y[0]也不在询问内容之中。
由于本题的正解代码很短（不到100行），所以请AC的同学不要放开代码。 出这道题也是有生活背景的： xxx同学学会了Dinic算法，高兴的对我说：（由于xxx同学的威胁，这里只能用xxx来保护xxx同学的隐私） xxx：嘿！我刚刚非常认真的分析题意，仔仔细细的建模，利用拆点的思想，终于用Dinic过掉了BZOJ上错误次数最多的经典难题。太难了！太难了！ 我：真的吗？好厉害！是哪道题？ xxx：BZOJ1000: a+b problem! 我：我屮艸芔茻！ 于是就有了这道题，本来是想圆蛋节出的，但是给忘了。。最后还是祝各位OIer在2017年里开开心心AK！  _Itachi
2017-01-10 11:21
4楼
| ||||
|
感谢 @kito 同学写暴力鉴定，经鉴定暴力30分（希望不会被小常数暴力踩掉，不过这个题单从常数上优化理论上是过不去的）
不过我优化了点常数（把读入的量设为long long这样可以少膜几次）确实快了很多。 _Itachi
2017-01-08 20:32
3楼
| ||||
|
回复 @若连自己也无相信，那指望谁能信 :
xxx同学还准备用费用流水掉A+B。。。 河北交通广播992大师来了
2017-01-08 15:48
2楼
| ||||
|
@若连自己也无相信，那指望谁能信
真丑。  CRT合并
2017-01-08 11:14
1楼
| ||||
【题目描述】
说明：
由于本蒟蒻的上一道题@2579. 剩蛋节的礼物 因为语言为动物城语言而导致很多人都不懂题，此次出题本蒟蒻决定将动物城语言的题目描述和汪星人语言的题目描述都放出来。
另外，由于本蒟蒻的上一道题被小常数线段树给踩了，所以希望这个题能够卡住暴力。
动物城语言：
动物城来了一对神秘来客：鸳鸯！他们实际上是爱情之神（即动物城的月老或者丘比特），得到他们祝福的恋人可以白头偕老。
想要得到他们的祝福，就需要证明你们有缘分。证明的方法是这样的：
男方抽取一个鸳蛋，女方抽取一个鸯蛋。鸳蛋上是一个数字Y，而鸯蛋上是一个函数：x[i]=a*x[i-1]*x[i-1]+b*x[i-1]+c mod 10007
你可以得到这个函数的前n项，假如你能在前n项内得到的函数中拼出Y，那么你们就能证明你们有缘分，而如果前n项都拼不出Y来，那么说明你们今生无缘。
不过聪明的尼克想办法弄到了“鸳蛋生成器”，即另一个函数：y[i]=d*y[i-1]*y[i-1]+e*y[i-1]+f mod 1000007，但只能使用m次。
尼克和朱迪当然想证明他们很有缘分，但他们不知道鸳蛋生成器的哪一个数可以拼出，哪一个不可以拼出来，现在他们很方，于是就又想到了你--树懒闪电！
汪星人语言：
你有两个函数：x[i]=a*x[i-1]*x[i-1]+b*x[i-1]+c mod 10007 ，y[i]=d*y[i-1]*y[i-1]+e*y[i-1]+f mod 1000007
你想知道所有的x[i]的前n项能不能拼出y[i]的前m项。对于每一个y[i],如果能，请输出yes,否则输出no。（我们规定y[i]==0时一定可以被拼出。）
“拼出y[i]”的意思是：选取一些数使得他们的和为y[i],每个数只能用1次。
【输入格式】
一个T表示测试数据组数。
接下来T行每行10个整数n,m,x0,a,b,c,y0,d,e,f
【输出格式】
T组(T<=20)测试数据，每组m行输出，如果y[i]能被拼出，则输出yes，否则输出no
【样例输入】
1
3 5 1 0 2 0 1 0 2 0
【样例输出】
yes
yes
yes
no
no
【提示】
样例说明：
x[]序列为2 4 8
y[]序列为2 4 8 16 32
x[]能拼出的数有：0 2 4 6 8 10 12 14
数据范围：
对于30%的数据，n*T<=2*10^3
对于100%的数据,n*T<=2*10^4,m<=10^5
【来源】
一只名字很长的蒟蒻