AtCoder Regular Contest++ 221
二的幂之和AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given a positive integer $N$ and a prime $P$.
给定一个正整数 $N$ 和一个素数 $P$。AI (CI翻译)
There is a length-$N$ sequence $A=(A_1,A_2,\ldots,A_N)$ where all elements are $0$.
有一个长度为 $N$ 的序列 $A=(A_1,A_2,\ldots,A_N)$，其中所有元素均为 $0$。AI (CI翻译)
You can repeat the following operation any number of times, possibly zero:
可以重复进行以下操作任意次，也可以一次都不进行：AI (CI翻译)
- Choose a non-empty subset
$S$of$\lbrace 1,2,\ldots,N\rbrace$. Let$\displaystyle x=\sum_{i\in S}2^{i-1}$. For each$i\in S$, replace$A_i$with$x$.
- 选择集合
$\lbrace 1,2,\ldots,N\rbrace$的一个非空子集$S$。令$\displaystyle x=\sum_{i\in S}2^{i-1}$。对于每个$i\in S$，将$A_i$替换为$x$。
Find the number, modulo $P$, of possible sequences $A$ after repeating the operations.
求重复进行操作后，可能得到的不同序列 $A$ 的数量。答案对 $P$ 取模。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1\leq N\leq 700$$P$is a prime satisfying$10^8\lt P\lt 10^9$.- All input values are integers.
$1\leq N\leq 700$$P$是满足$10^8\lt P\lt 10^9$的素数。- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入中按以下格式给出：AI (CI翻译)
N PN POutput
输出格式
AI (CI翻译)Output the answer.
输出答案。AI (CI翻译)
样例
Input #1
1 998244353
Output #1
2
The possible sequences $A$ are $(0),(1)$, giving two possibilities.
Input #2
2 998244353
Output #2
7
The possible sequences $A$ are $(0,0),(0,2),(1,0),(1,2),(1,3),(3,2),(3,3)$, giving seven possibilities.
Input #3
3 998244353
Output #3
57
Input #4
4 998244353
Output #4
1208
Input #5
77 777777773
Output #5
381787647
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。