← 返回题目列表

AtCoder · agc044_f

F. 保名俱乐部

中文机器翻译题面 查看原题

分数: 2400 点

问题陈述

有 N 人(具有不同的名字)和 K 俱乐部。对于每个俱乐部,您都知道成员名单(因此您有 K 无序列表)。每个人都可以是许多俱乐部的成员(也可以是 0 俱乐部)和两个不同的俱乐部可能拥有完全相同的成员。 数字的值 K 是最小可能值,使得以下属性对于至少一种球杆配置成立。 如果每个人都改变了她的名字(保持所有名字都不同的属性)并且你知道新的 K 俱乐部成员名单(但你不知道哪个名单对应哪个俱乐部),你确信你能够将旧名字与新名字相匹配。

数一下这种配置的球杆的数量(或者说有超过 1000)。 两种配置的球杆可以从另一种获得,如果 N 人们改名被认为是平等的。

正式声明: 俱乐部是(可能是空的)子集 \{1,\dots, N\} (子集标识成员,假设人员按数字索引 1, 2,\dots, N)。 俱乐部的配置是无序的集合 K 俱乐部(不一定不同)。 给定一个排列 \sigma(1), \dots, \sigma(N) of \{1,\dots, N\} 和俱乐部的配置 L=\{C_1, C_2, \dots, C_K\},我们用 \sigma(L) 俱乐部的配置 \{\sigma(C_1), \sigma(C_2), \dots, \sigma(C_K)\} (如果 C 是一个俱乐部, \sigma(C)=\{\sigma(x):\, x\in C\})。 俱乐部的配置 L 是名称保留的,如果对于任何一对不同的排列 \sigma\not=\tau,它成立 \sigma(L)\not=\tau(L).

你必须用尽可能少的球杆数来计算球杆的名称保留配置的数量(所以 K 是最小值)。两种配置 L_1, L_2 这样 L_2=\sigma(L_1) (对于某些排列 \sigma) 被认为是相等的。 如果有超过 1000 这样的配置,打印 -1.

约束

  • 2 \le N \le 2\cdot10^{18}

输入

输入由标准输入以以下格式给出

N

输出

If ans 是具有语句中描述的属性的配置数量,您应该在标准输出上打印

ans

如果有超过 1000 这样的配置,打印 -1.


示例输入 1

2

示例输出 1

1

的值 此输入中给出的 K is 1 俱乐部独特的名称保留配置是 \{\{1\}\} (配置 \{\{2\}\} 被认为是相同的)。


示例输入 2

3

示例输出 2

1

的值 此输入中给出的 K is 2 并且俱乐部的独特(最多排列)名称保留配置是 \{\{1\}, \{1, 2\}\}.


示例输入 3

4

示例输出 3

7

的值 此输入中给出的 K is 3 以及俱乐部的名称保留配置 3 俱乐部是:

  • \{\{1\}, \{2\}, \{1, 3\}\}
  • \{\{1\}, \{1, 2\}, \{2, 3\}\}
  • \{\{1, 2\}, \{1, 2\}, \{1, 3\}\}
  • \{\{1\}, \{1, 2\}, \{1, 2, 3\}\}
  • \{\{1\}, \{2, 3\}, \{1, 2, 4\}\}
  • \{\{1, 2\}, \{1, 3\}, \{1, 2, 4\}
  • \{\{1, 2\}, \{1, 2, 3\}, \{2, 3, 4\}\}

示例输入 4

13

示例输出 4

6

示例输入 5

26

示例输出 5

-1

示例输入 6

123456789123456789

示例输出 6

-1