娱乐 每 日 算 法 挑 战 【第6期】

[Mr.K 018]

第6期来啦！

本题有4个输入数据量的版本，分别对应不同复杂度的算法。大家能做到的最好的复杂度是多少呢？

第6期 PQ的魔法石

 

题目描述：

    PQ收集到了很多魔法石。

    魔法石一共有红黄蓝三种颜色，每块魔法石都有一个魔力值。PQ每种颜色的魔法石都有N块。

    传说，只要三块魔力值的和恰好等于M的三种魔法石各一块聚在一起时，就可以召唤出会长大人（注：出题时还没有Hololive，大家不用往那个方向想），并满足PQ的三个愿望。

    请问，PQ有多少种方法可以召唤出会长大人? 

输入：

第一行,两个整数N,M. 

    接下来三行,代表三种魔法石,每行N个整数,依次代表魔法石的魔力值. 所有魔力值的取值范围都在[0 , max(M)/3).

输出：

    符合条件的方案数. 保证结果在int范围内。

作者：

    PQ

 

---数据量---

Easy:         0 < N <= 500 , 0 < M <= 3000

Normal:    0 < N <= 5000 , 0 < M <= 3000

Hard:        0 < N <= 3000 , 0 < M <= 3 * 10 ^ 8

Extreme:   0 < N <= 10000 , 0 < M <= 3 * 10 ^ 17

做出难度更高的版本，奖励的节操更多哦！

召唤阵：

@yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵

四月 15, 2020，由Mr.K 018修改

[Mr.K 018]

1 分钟前, yhz012 说道:

等下是我理解错了么？M/3侧是开区间，所以三个加一起怎么也小于M？

领会精神就好M已修改为M的右界

[Mr.K 018]

2 分钟前, yhz012 说道:

顺带是不是应该用maxM +1，不然如果M刚好取最大值也可以直接说没方法了（x

原题如此

n^3怕是只能AC掉easy……

四月 15, 2020，由Mr.K 018修改

[Mr.K 018]

刚刚, Muriya Tensei 说道:

（继续潜水等大佬思路）（我太菜了，只能想到快排二分或者用空间换时间）

说说看嘛

反正不要钱，多少写一点，何况有节操

[Mr.K 018]

刚刚, yhz012 说道:

C啊……我记得C甚至不自带hash相关库吧……会很痛苦…………

C++的set和map库都是用堆实现的，C甚至根本就没那库