AT_arc233_d.Zigzag Code for Cubic Functions

NOI/NOI+/CTSC

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given positive integers A,B,C,L,RA,B,C,L,R. Here, L≤RL \leq R. Define
f(n)=n3+An2+Bn+Cf(n)=n^3+An^2+Bn+C.
For a non-empty string SS consisting of +\mathtt{+} and −\mathtt{-}, define
g(S)=∑i=1∣S∣{f(i)(Si=+)−f(i)(Si=−)g(S) = \sum_{i=1}^{|S|} \begin{cases} f(i) & (S_i = \mathtt{+}) \\ -f(i) & (S_i = \mathtt{-}) \end{cases}.
Here, SiS_i denotes the ii-th character of SS.
An integer kk is said to be generable from SS if there exists a non-empty substring S′S' of SS such that g(S′)=kg(S')=k.

Construct a string SS that satisfies the following conditions.

  • 1≤∣S∣≤2×1061 \leq |S| \leq 2 \times 10^6
  • SS is a string consisting of +\mathtt{+} and −\mathtt{-}.
  • Among the strings satisfying the two conditions above, SS maximizes the number of integers between LL and RR, inclusive, that are generable from SS.

Furthermore, for the constructed string SS and each k=L,L+1,…,Rk=L,L+1,\dots,R, determine whether there exist two integers l,rl,r satisfying the following conditions, and if they exist, find one such pair.

  • 1≤l≤r≤∣S∣1 \leq l \leq r \leq |S|
  • Letting S′S' be the string formed by the ll-th through rr-th characters of SS, we have g(S′)=kg(S')=k.

What is a substring?

A substring of SS is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of SS.
For example, AB is a substring of ABC, but AC is not a substring of ABC.

给你正整数 A,B,C,L,RA,B,C,L,R,其中 L≤RL \leq R。定义
f(n)=n3+An2+Bn+Cf(n)=n^3+An^2+Bn+C。
对于一个由字符 +\mathtt{+} 和 −\mathtt{-} 构成的非空字符串 SS,定义
g(S)=∑i=1∣S∣{f(i)(Si=+)−f(i)(Si=−)g(S) = \sum_{i=1}^{|S|} \begin{cases} f(i) & (S_i = \mathtt{+}) \\ -f(i) & (S_i = \mathtt{-}) \end{cases}。
这里,SiS_i 表示字符串 SS 的第 ii 个字符。
若存在 SS 的一个非空子串 S′S',使得 g(S′)=kg(S')=k,则称整数 kk 可由 SS 生成。

请构造一个字符串 SS,使其满足以下条件:

  • 1≤∣S∣≤2×1061 \leq |S| \leq 2 \times 10^6;
  • SS 是仅由 +\mathtt{+} 和 −\mathtt{-} 构成的字符串;
  • 在所有满足上述两个条件的字符串中,SS 能够生成的、落在区间 [L,R][L,R] 内(含端点)的整数个数最多。

此外,对所构造出的字符串 SS 以及每个 k=L,L+1,…,Rk = L, L+1, \dots, R,判断是否存在整数 l,rl,r 满足以下条件;若存在,则输出其中任意一对:

  • 1≤l≤r≤∣S∣1 \leq l \leq r \leq |S|;
  • 记 S′S' 为 SS 中从第 ll 个字符到第 rr 个字符(含)构成的子串,则有 g(S′)=kg(S') = k。

什么是子串?

字符串 SS 的一个子串,是指从 SS 的开头删除零个或多个字符、并从 SS 的末尾也删除零个或多个字符后所得到的字符串。
例如,AB 是 ABC 的子串,但 AC 不是 ABC 的子串。

输入格式

The input is given from Standard Input in the following format:

AA BB CC LL RR

输入从标准输入中以如下格式给出:

AA BB CC LL RR

输出格式

Print a solution in the following format:

SS
outputL\mathrm{output}_{L}
outputL+1\mathrm{output}_{L+1}
⋮\vdots
outputR\mathrm{output}_{R}

Here, outputi\mathrm{output}_i denotes the output for k=ik=i.
If there exist two integers l,rl,r satisfying the conditions, print them in the following format:

ll rr

If they do not exist, print -1.

If there are multiple solutions, you may print any of them.

按以下格式输出一个解:

SS
outputL\mathrm{output}_{L}
outputL+1\mathrm{output}_{L+1}
⋮\vdots
outputR\mathrm{output}_{R}

其中,outputi\mathrm{output}_i 表示当 k=ik=i 时的输出。
若存在满足条件的两个整数 l,rl,r,则按以下格式输出它们:

ll rr

若不存在这样的整数,则输出 -1。

若存在多个解,可输出其中任意一个。

输入输出样例

  • 输入#1

    2 2 3 22 23

    输出#1

    +---+--+
    2 5
    6 8
  • 输入#2

    1 2 2 5 7

    输出#2

    ++
    -1
    2 2
    -1

说明/提示

Sample 1 Explanation:
We have
f(n)=n3+2n2+2n+3f(n)=n^3+2n^2+2n+3 and
f(1)=8,  f(2)=23,  f(3)=54,  f(4)=107f(1)=8,\; f(2)=23,\; f(3)=54,\; f(4)=107.
Since
g(−−−+)=−f(1)−f(2)−f(3)+f(4)=−8−23−54+107=22g(\mathtt{---+})=-f(1)-f(2)-f(3)+f(4)=-8-23-54+107=22 and
g(−−+)=−f(1)−f(2)+f(3)=−8−23+54=23g(\mathtt{--+})=-f(1)-f(2)+f(3)=-8-23+54=23,
both 2222 and 2323 are generable from −−−+\mathtt{---+}.

Constraints

  • 1≤A,B,C≤1051 \leq A,B,C \leq 10^5
  • 1≤L≤R≤min⁡(L+105,1014)1 \leq L \leq R \leq \min(L+10^5,10^{14})
  • All input values are integers.

样例 1 解释:
我们有
f(n)=n3+2n2+2n+3f(n)=n^3+2n^2+2n+3,且
f(1)=8,  f(2)=23,  f(3)=54,  f(4)=107f(1)=8,\; f(2)=23,\; f(3)=54,\; f(4)=107。
由于
g(−−−+)=−f(1)−f(2)−f(3)+f(4)=−8−23−54+107=22g(\mathtt{---+})=-f(1)-f(2)-f(3)+f(4)=-8-23-54+107=22,以及
g(−−+)=−f(1)−f(2)+f(3)=−8−23+54=23g(\mathtt{--+})=-f(1)-f(2)+f(3)=-8-23+54=23,
因此 2222 和 2323 均可由 −−−+\mathtt{---+} 生成。

限制条件

  • 1≤A,B,C≤1051 \leq A,B,C \leq 10^5
  • 1≤L≤R≤min⁡(L+105,1014)1 \leq L \leq R \leq \min(L+10^5,10^{14})
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页