#390 Polynomial Inverse DSL

Statement

모든 계산은 체 $\mathbb{F}_{998244353}$ 위에서 이루어진다.

길이가 $N$ 인 비공개 다항식

f(x)=f_0+f_1x+\cdots+f_{N-1}x^{N-1}

이 정해져 있다. 항상 $f_0\ne 0$ 이다.

참가자 프로그램은 $N$ 을 읽고, 아래 명세를 따르는 직선형 DSL 프로그램을 출력해야 한다. DSL 실행이 시작되면 길이가 $N$ 인 벡터 f가 미리 정의되어 있으며, f[i]는 $f_i$ 를 나타낸다. DSL에는 반복문과 조건문이 없다. 참가자 프로그램 안에서는 반복문을 사용해도 되지만, 필요한 DSL 명령은 모두 전개하여 출력해야 한다.

출력한 DSL 프로그램은 길이가 $N$ 인 벡터 $g$ 를 반환해야 하며, 다음을 만족해야 한다.

f(x)g(x)\equiv 1\pmod{x^N}

채점기는 입력에 포함된 불투명한 데이터를 비공개 키로 복원하여 $f$ 를 얻는다. 참가자에게 공개되는 논리적 입력은 $N$ 뿐이다. 채점기는 출력된 DSL 프로그램을 복원한 $f$ 에 대해 실제로 실행한다.

DSL 전체 명세

모든 레지스터 값은 $\mathbb{F}_{998244353}$ 위의 유한 벡터이다. 벡터 $a$ 의 길이는 $|a|$ 로 표기하고, 인덱스는 $0$ 부터 시작한다. 빈 벡터도 허용된다.

각 명령은 한 줄에 하나씩 다음 형식으로 출력한다.

OPCODE arg1 arg2 ...

레지스터 이름은 정규식 [A-Za-z\_][A-Za-z0-9\_]*을 만족해야 한다. 정수 리터럴은 십진 표기의 signed 64-bit 정수여야 한다. 체 원소로 쓰이는 리터럴은 modulo $998244353$ 으로 정규화된다.

결과 레지스터 dst가 처음 등장하면 새 레지스터가 정의된다. 이미 정의된 경우에는 기존 값을 덮어쓴다. dst가 피연산자와 같아도 되며, 이때 모든 피연산자는 명령 실행 전의 값을 사용한다. 단, SCATTER는 기존 dst에 누적한다. 정의되지 않은 레지스터를 읽으면 실행 오류이다.

명령	결과 길이	의미
`CONST dst value`	$1$	상수 벡터
`ARITH dst len first diff`	$len$	등차수열
`GEOM dst len first ratio`	$len$	등비수열
`GATHER dst src start step count`	$count$	등간격 인덱스 읽기
`SCATTER dst src start step`	기존 $\|dst\|$	지정 위치에 누적
`FOLD dst src k c`	$k$	$x^k-c$ 에 대한 나머지
`ADD dst lhs rhs`	$\max(\|lhs\|,\|rhs\|)$	계수별 덧셈
`SUB dst lhs rhs`	$\max(\|lhs\|,\|rhs\|)$	계수별 뺄셈
`MUL dst lhs rhs`	아래 규칙	원소별 곱 또는 스칼라배
`INV dst src`	$\|src\|$	원소별 역원
`DFT dst src`	$\|src\|$	NTT
`IDFT dst src`	$\|src\|$	inverse NTT
`CONV dst lhs rhs`	$\|lhs\|+\|rhs\|-1$ 또는 $0$	full convolution
`RETURN src`	없음	결과 반환 후 종료

CONST

CONST dst value

$dst=[value]$ 이다.

ARITH

ARITH dst len first diff

$len$ 은 음이 아닌 정수이며,

dst_i=first+i\cdot diff\qquad(0\le i<len)

이다.

GEOM

GEOM dst len first ratio

$len$ 은 음이 아닌 정수이며,

dst_i=first\cdot ratio^i\qquad(0\le i<len)

이다.

GATHER

GATHER dst src start step count

$count$ 는 음이 아닌 정수이다. $start$ 와 $step$ 은 signed 64-bit 정수이며 $step=0$ 도 허용된다.

dst_i= \begin{cases} src_{start+i\cdot step},&0\le start+i\cdot step<|src|,\\ 0,&\text{그 밖의 경우} \end{cases}

이다. 예를 들어 GATHER dst src 0 1 L은 src를 길이 $L$ 로 자르거나 뒤에 $0$ 을 붙인다.

SCATTER

SCATTER dst src start step

명령 실행 전 src의 값을 $s$ 라고 할 때,

dst_{start+i\cdot step}\mathrel{+}=s_i\qquad(0\le i<|s|)

를 수행한다. 모든 목적 인덱스가 $[0,|dst|)$ 안에 있어야 한다. $step=0$ 과 중복 목적 인덱스를 허용한다.

FOLD

FOLD dst src k c

$k$ 는 양의 정수이며,

dst_i=\sum_{j\ge 0}src_{i+jk}c^j\qquad(0\le i<k)

이다. 다항식 계수 벡터로 보면 $dst(x)\equiv src(x)\pmod{x^k-c}$ 이다.

ADD와 SUB

짧은 벡터의 뒤를 $0$ 으로 확장한 뒤 계수별로 더하거나 뺀다.

ADD_i=[i<|lhs|]lhs_i+[i<|rhs|]rhs_i,

SUB_i=[i<|lhs|]lhs_i-[i<|rhs|]rhs_i.

MUL

MUL dst lhs rhs

다음 규칙을 순서대로 적용한다.

$|lhs|=|rhs|$ 이면 원소별 곱을 계산한다.
길이가 다르고 $|lhs|=1$ 이면 lhs[0]으로 rhs를 스칼라배한다.
길이가 다르고 $|rhs|=1$ 이면 rhs[0]으로 lhs를 스칼라배한다.
그 밖의 경우 실행 오류이다.

MUL은 다항식 convolution이 아니다.

INV

INV dst src

src는 비어 있지 않아야 하고 모든 원소가 $0$ 이 아니어야 한다. $dst_i=src_i^{-1}$ 을 계산한다.

DFT와 IDFT

입력 길이는 $1$ 이상 $2^{23}$ 이하인 $2$ 의 거듭제곱이어야 한다. DFT 결과의 주파수 순서는 공개되지 않는다. 다음 성질만 보장된다.

\operatorname{IDFT}(\operatorname{DFT}(a))=a

같은 길이의 두 DFT 결과를 원소별로 곱한 뒤 IDFT를 적용하면 그 길이에서의 cyclic convolution을 얻는다. 같은 길이에 대한 모든 DFT 호출은 동일한 비공개 순서를 사용한다.

CONV

CONV dst lhs rhs

한 피연산자라도 빈 벡터이면 결과는 빈 벡터이다. 그렇지 않으면

|dst|=|lhs|+|rhs|-1,

dst_k=\sum_{i+j=k}lhs_i rhs_j

이다. 필요한 변환 길이가 $2^{23}$ 을 초과하면 실행 오류이다.

RETURN

RETURN src

src를 결과로 반환하고 즉시 실행을 종료한다. 정확히 한 번 실행되어야 하며, 반환 벡터의 길이는 $N$ 이어야 한다. RETURN 뒤에 다른 명령이 있으면 실행 오류이다.

길이 $L$ 인 DFT 또는 IDFT의 비용은

D(L)=L\log_2L

이다. 비어 있지 않은 두 벡터에 대한 CONV에서 $S=|lhs|+|rhs|-1$ 이라 하고, $S$ 이상인 최소의 $2$ 의 거듭제곱을 $L$ 이라 하면 비용은 $3D(L)$ 이다. 그 밖의 명령의 FFT 비용은 $0$ 이다. 실행된 명령의 비용 합을 $\mathrm{FFT\_COST}$ 라 한다.

정의되지 않은 레지스터 읽기, 잘못된 인자 개수나 정수 형식, 음수 길이, $k=0$ 인 FOLD, 길이 조건을 만족하지 않는 MUL, $0$ 을 포함한 INV, 잘못된 DFT 길이, 범위를 벗어나는 SCATTER, 잘못된 RETURN은 실행 오류이다.

채점

채점기는 서로 다른 비공개 다항식에 대해 프로그램을 검사한다. 문법 오류, 실행 오류, 잘못된 결과, 시간 제한 초과, 메모리 제한 초과 중 하나라도 발생하면 점수는 $0$ 점이다.

$N=2^{20}$ 인 각 테스트에서

C_t=\frac{\mathrm{FFT\_COST}_t}{N\log_2N}

로 정의한다. 이러한 테스트들의 $C_t$ 중 최댓값을 $C$ 라 한다. 최종 점수는

100\cdot\min\left(1,\frac{9}{C}\right)

이다. $\mathrm{FFT\_COST}=0$ 이면 해당 비율은 $1$ 로 해석한다. 따라서 모든 테스트에서 정확하고 $C\le 9$ 이면 $100$ 점을 받는다. $N<2^{20}$ 인 테스트는 정확성만 검사한다.

테스트

첨부파일로 제공되는 poly_dsl_backend_standalone.hpp를 이용하면 DSL 명령을 C++ 함수 호출과 비슷한 형태로 작성할 수 있다. 예를 들어 다음과 같은 프로그램을 작성할 수 있다.

#include <bits/stdc++.h>
#include "poly_dsl_backend_standalone.hpp"

using namespace std;

int main() {
    int N;
    cin >> N;

    READ_INPUT(f, N);

    GATHER(f0, f, 0, 1, 1);
    INV(g, f0);
    RETURN(g);

    PRINT_COSTS();
}

별도의 컴파일 플래그 없이 컴파일하여 실행하면, 입력으로 $N$ 만 주어졌을 때 다음 DSL 프로그램을 표준 출력으로 출력한다.

GATHER f0 f 0 1 1
INV g f0
RETURN g

컴파일할 때 -DEXECUTE_DSL 플래그를 추가하면 DSL 프로그램을 출력하는 대신 각 명령을 직접 실행해 볼 수 있다.

g++ -std=c++17 -O2 -DEXECUTE_DSL solution.cpp -o solution

이 경우 프로그램의 입력으로 $N$ 에 이어 $f_0,f_1,\ldots,f_{N-1}$ 을 주어야 하며, 표준 출력에는 RETURN으로 반환한 벡터가 출력된다.

PRINT_COSTS()를 호출하면 계산된 비용을 표준 오류 출력에서 확인할 수 있다.

FFT_COST = 25165788
AUX_COST = 1114125

이 중 FFT_COST의 값이 실제 점수 계산에 사용된다.

실제 채점기에서도 이 헤더에 포함된 DSL 명령의 구현을 사용한다.

Input

입력은 다음과 같은 형식으로 주어진다.

$N$ $E_0\ E_1\ \cdots\ E_{N-1}$

$E_0,E_1,\ldots,E_{N-1}$ 은 채점기만 해석하는 불투명한 인코딩 데이터이다. 참가자 프로그램은 첫 번째 정수 $N$ 만 읽으면 충분하며, 나머지 입력은 무시해야 한다. $E_i$ 와 비공개 계수 $f_i$ 사이의 대응은 공개되지 않는다.

Output

DSL 명령을 한 줄에 하나씩 출력한다. 명령 개수를 먼저 출력하지 않는다. 채점기는 출력 파일의 끝까지 읽는다.

프로그램은 RETURN을 정확히 한 번 실행해야 하며, 반환 벡터의 길이는 $N$ 이어야 한다. 가능한 DSL 프로그램이 여러 가지라면 아무거나 출력해도 된다.

Constraints

$1\le N\le 2^{20}$ .
$0\le E_i<2^{30}$ ( $0\le i<N$ ).
비공개 계수는 $0\le f_i<998244353$ 을 만족하고, $f_0\ne 0$ 이다 ( $0\le i<N$ ).
출력 크기는 $64\,\mathrm{MiB}$ 이하여야 한다.
공백만 있는 줄을 제외한 DSL 명령은 $200\,000$ 개 이하여야 한다.
한 출력 줄의 길이는 $1024$ 바이트 이하여야 한다.
서로 다른 레지스터는 $4096$ 개 이하여야 하며, 레지스터 이름은 $128$ 바이트 이하여야 한다.
DSL 실행 중 레지스터와 내부 작업 공간에 동시에 저장되는 체 원소 수는 $2^{27}$ 이하여야 한다.

Subtasks

#	Score	Constraints
1	100	추가적인 제약이 없다.

Samples

Input

1
555569908

Output

GATHER f0 f 0 1 1
INV g f0
RETURN g

$N=1$ 에서는 상수항의 역원 하나만 반환하면 된다. 두 번째 입력 값은 채점기용 불투명 데이터이므로 참가자 프로그램은 사용하지 않는다.

Editorial

View editorial

다항식 역원 DSL

Statement

Input

Output

Constraints

Subtasks

Samples

Editorial

Attachments