seuOJ308 - Dark Matter

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：6000 ms
• 空间限制：256 MiB
• 题目标签：冬季, 校赛, 决赛, 2020

题目描述

Teitoku 的能力是「未元物质」。

Teitoku 能产生这个世界上真正不存在的物质。

在被 Accelerator 打败变成冰箱后，Teitoku 获得了利用「未元物质」重新建构人体细胞的技术，通过量产「未元物质」产生自己新的身体。

Teitoku 发现：每一片个体 $i$ 都有自己的力量 $b_i$，将它们组合后，总力量为 $\prod b_i$。

然而，Teitoku 的改造尚未完成，假如组合后的总力量大于他的限度 $L$，即使是「未元物质」的主体也无法维持 Teitoku 这个安定的人格。

Teitoku 想在得到安定人格的基础上获得最大的力量，还想知道有多少种不同的可能性能达到这一目标。

这对于 Level 5 的 Teitoku 来说自然不是问题，但你能做到吗？

形式化描述如下：

给定一个长度为 $n$ 的序列 $a$，求出有多少不同的 $a$ 的子序列 $b$ 使得 $\prod\limits_{i=1}^{|b|}b_i\leq L$ 且 $\prod\limits_{i=1}^{|b|}b_i$ 最大，其中 ${|b|}$ 为 $b$ 的长度。特别地，若 $b$ 为空，定义 $\prod\limits_{i=1}^{|b|}b_i=1$。

$\prod\limits_{i=1}^{|b|}b_i$ 即 $b_1\times b_2\times\cdots\times b_{|b|}$。

一个序列 $a$ 的子序列 $b$ 定义为：在 $a$ 中删除一些数（也可全删或者不删）得到的新的序列。

若两个序列删去的数的下标不同，则称这两个序列不相同。

为了节省输入带来的时间消耗，使用以下随机数生成器生成数列 $a$。 随机种子 xorshift128p_state 将通过输入提供。为了限制数字的范围，random_number_generator 产生 $[0,p)$ 内的随机整数。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
struct xorshift128p_state {
    ull a, b;
};
struct xorshift128p_state state;
/* The state must be seeded so that it is not all zero */
ull xorshift128p()
{
    ull t = state.a;
    ull const s = state.b;
    state.a = s;
    t ^= t << 23;		// a
    t ^= t >> 17;		// b
    t ^= s ^ (s >> 26);	// c
    state.b = t;
    return t + s;
}
ull random_number_generator(ull p)
{
    return xorshift128p() % p;
}

在读入 $n$，$p$，$L$，随机种子 $state$ 之后，你可以直接使用如下代码产生数列 $a$。

ull a[114514], p;
int n;
void data_generator()
{
    for (int i = 1; i <= n; ++i)
        a[i] = random_number_generator(p);
}

输入格式

输入包含若干组测试数据，第一行包含 $1$ 个整数 $T(1\leq T\leq10)$，表示测试数据的数量。

对于每一组测试数据：

第一行为 $3$ 个整数 $n,p,L$，分别表示序列长度 $n(1\leq n\leq 40)$，模数 $p(2 \leq p \leq 10^{18})$，上限 $L(1\leq L\leq 10^{18})$。

第二行为 $2$ 个整数 $state.a,state.b(1\leq state.a, state.b\leq 10^{18})$，表示随机数生成器使用的随机种子。

输出格式

共 $T$ 行，第 $i$ 行表示第 $i$ 组测试数据对应的答案，包含由空格分隔的两个整数，分别为最大的乘积 $m$ 和能得到 $m$ 的不同序列个数。

样例

样例输入

5
1 10 100
114514 1919810
1 10 1
114514 1919810
3 11 50
1000000000000000000 1000000000000000000
40 204569168014627377 530252769325029080
148764716271368324 690723135015690090
40 2 660757177532743731
921878175032867551 587220596214858730

样例输出

8 1
1 1
40 1
191108540084643193 1
1 524288

样例解释

对于随机种子$114514, 1919810$，产生的长度为$1$的序列$a=[8]$。

对于第$1$组数据，$b=[8]$时乘积最大且不超过$100$，此时乘积为$8$，可以证明没有其他方案能得到该乘积。

对于第$2$组数据，$b=[]$，即$b$为空时乘积最大且不超过$1$，此时乘积为$8$，可以证明没有其他方案能得到该乘积。

对于随机种子$1000000000000000000,1000000000000000000$，产生的长度为$3$的序列$a=[2,10,4]$。

对于第$3$组数据，$b=[10,4]$时乘积最大且不超过$50$，此时乘积为$40$，可以证明没有其他方案能得到该乘积。