참가자 프로그램은 N을 읽고, 아래 명세를 따르는 직선형 DSL 프로그램을 출력해야 한다. DSL 실행이 시작되면 길이가 N인 벡터 f가 미리 정의되어 있으며, f[i]는 fi를 나타낸다. DSL에는 반복문과 조건문이 없다. 참가자 프로그램 안에서는 반복문을 사용해도 되지만, 필요한 DSL 명령은 모두 전개하여 출력해야 한다.
출력한 DSL 프로그램은 길이가 N인 벡터 g를 반환해야 하며, 다음을 만족해야 한다.
f(x)g(x)≡1(modxN)
채점기는 입력에 포함된 불투명한 데이터를 비공개 키로 복원하여 f를 얻는다. 참가자에게 공개되는 논리적 입력은 N뿐이다. 채점기는 출력된 DSL 프로그램을 복원한 f에 대해 실제로 실행한다.
DSL 전체 명세
모든 레지스터 값은 F998244353 위의 유한 벡터이다. 벡터 a의 길이는 ∣a∣로 표기하고, 인덱스는 0부터 시작한다. 빈 벡터도 허용된다.
각 명령은 한 줄에 하나씩 다음 형식으로 출력한다.
채점
채점기는 서로 다른 비공개 다항식에 대해 프로그램을 검사한다. 문법 오류, 실행 오류, 잘못된 결과, 시간 제한 초과, 메모리 제한 초과 중 하나라도 발생하면 점수는 0점이다.
N=220인 각 테스트에서
C
Input
입력은 다음과 같은 형식으로 주어진다.
NE0E1⋯
Output
DSL 명령을 한 줄에 하나씩 출력한다. 명령 개수를 먼저 출력하지 않는다. 채점기는 출력 파일의 끝까지 읽는다.
프로그램은 RETURN을 정확히 한 번 실행해야 하며, 반환 벡터의 길이는 N이어야 한다. 가능한 DSL 프로그램이 여러 가지라면 아무거나 출력해도 된다.
Constraints
1≤N≤220.
0≤E ().
Subtasks
#
점수
제한
1
100
추가적인 제약이 없다.
Samples
입력
1
555569908
출력
GATHER f0 f 0 1 1
INV g f0
RETURN g
N=1에서는 상수항의 역원 하나만 반환하면 된다. 두 번째 입력 값은 채점기용 불투명 데이터이므로 참가자 프로그램은 사용하지 않는다.
레지스터 이름은 정규식 [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
xk−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은 음이 아닌 정수이며,
dsti=first+i⋅diff(0≤i<len)
이다.
GEOM
GEOM dst len first ratio
len은 음이 아닌 정수이며,
dsti=first⋅ratioi(0≤i<len)
이다.
GATHER
GATHER dst src start step count
count는 음이 아닌 정수이다. start와 step은 signed 64-bit 정수이며 step=0도 허용된다.
dsti=
이다. 예를 들어 GATHER dst src 0 1 L은 src를 길이 L로 자르거나 뒤에 0을 붙인다.
SCATTER
SCATTER dst src start step
명령 실행 전 src의 값을 s라고 할 때,
dststart+i⋅step+=si(0≤i<∣s∣)
를 수행한다. 모든 목적 인덱스가 [0,∣dst∣) 안에 있어야 한다. step=0과 중복 목적 인덱스를 허용한다.
FOLD
FOLD dst src k c
k는 양의 정수이며,
dsti=j≥0∑srci+jkcj(0≤i<k)
이다. 다항식 계수 벡터로 보면 dst(x)≡src(x)(modxk−c)이다.
ADD와 SUB
짧은 벡터의 뒤를 0으로 확장한 뒤 계수별로 더하거나 뺀다.
ADDi=[i<∣lhs∣]lhSUBi=[i<∣lhs∣]lh
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이 아니어야 한다. dsti=srci−1을 계산한다.
DFT와 IDFT
입력 길이는 1 이상 223 이하인 2의 거듭제곱이어야 한다. DFT 결과의 주파수 순서는 공개되지 않는다. 다음 성질만 보장된다.
IDFT(DFT(a))=a
같은 길이의 두 DFT 결과를 원소별로 곱한 뒤 IDFT를 적용하면 그 길이에서의 cyclic convolution을 얻는다. 같은 길이에 대한 모든 DFT 호출은 동일한 비공개 순서를 사용한다.
CONV
CONV dst lhs rhs
한 피연산자라도 빈 벡터이면 결과는 빈 벡터이다. 그렇지 않으면
∣dst∣=∣lhs∣+∣rhs∣−1,dstk=i+j=k∑lhsirhs
이다. 필요한 변환 길이가 223을 초과하면 실행 오류이다.
RETURN
RETURN src
src를 결과로 반환하고 즉시 실행을 종료한다. 정확히 한 번 실행되어야 하며, 반환 벡터의 길이는 N이어야 한다. RETURN 뒤에 다른 명령이 있으면 실행 오류이다.
길이 L인 DFT 또는 IDFT의 비용은
D(L)=Llog2L
이다. 비어 있지 않은 두 벡터에 대한 CONV에서 S=∣lhs∣+∣rhs∣−1이라 하고, S 이상인 최소의 2의 거듭제곱을 이라 하면 비용은 이다. 그 밖의 명령의 FFT 비용은 이다. 실행된 명령의 비용 합을 라 한다.
정의되지 않은 레지스터 읽기, 잘못된 인자 개수나 정수 형식, 음수 길이, k=0인 FOLD, 길이 조건을 만족하지 않는 MUL, 0을 포함한 INV, 잘못된 DFT 길이, 범위를 벗어나는 SCATTER, 잘못된 RETURN은 실행 오류이다.
t
=
Nlog2NFFT_COSTt
로 정의한다. 이러한 테스트들의 Ct 중 최댓값을 C라 한다. 최종 점수는
100⋅min(1,C9)
이다. FFT_COST=0이면 해당 비율은 1로 해석한다. 따라서 모든 테스트에서 정확하고 C≤9이면 100점을 받는다. N<220인 테스트는 정확성만 검사한다.
테스트
첨부파일로 제공되는 poly_dsl_backend_standalone.hpp를 이용하면 DSL 명령을 C++ 함수 호출과 비슷한 형태로 작성할 수 있다. 예를 들어 다음과 같은 프로그램을 작성할 수 있다.
