問題一覧 > 通常問題

No.3278 Avoid Division

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 31
作問者 : とりゐ / テスター : AngrySadEight
ProblemId : 10319 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-09-19 17:31:37

問題文

素数 $P$ と $\mathrm{mod}\ P$ における足し算・掛け算・割り算をおこなうことができるプログラミング言語があります．$P$ は入力では与えられず，$10^8\lt P\lt 10^9$ を満たします．（$P$ は事前に決定されています．）
この言語を用いて，高々 $100$ 回の足し算と高々 $100$ 回の掛け算と高々 $1$ 回の割り算を行うことで，以下の問題の答えを求めるプログラムを作成してください．

$N$ 個の演算の命令，および変数 $x$ があります．初め，$x=0$ で初期化されています．今から $i=1,2,\ldots,N$ に対して以下の操作を順番に行います．
  • $op_i=$ +のとき
    $x$ を $x + A_i\pmod P$ で置き換える $(1\leq A_i\lt 10^8)$
  • $op_i=$ *のとき
    $x$ を $x \times A_i\pmod P$ で置き換える $(1\leq A_i\lt 10^8)$
  • $op_i=$ /のとき
    $x$ を $x / A_i\pmod P$ で置き換える $(1\leq A_i\lt 10^8)$
    • ここで，$a/b\pmod P\ (0\leq a\lt P, 1\leq b\lt P)$ とは $a\equiv bc\pmod P$ を満たす唯一の整数 $c\ (0\leq c\lt P)$ である．
これらの操作を行った後の $x$ の値を求めてください．

プログラムの仕様

このプログラムでは英小文字で表される $a,b,\ldots,z$ の $26$ 個の変数を扱うことができる．
各変数には $0$ 以上 $P$ 未満の整数値を保持することができる．
プログラムの実行開始時点では，すべての変数に $0$ が代入されている．
また，プログラムの開始時点に長さ $N$ の配列 $A$ が与えられ，この配列を参照することができる．(配列の値を変更することはできない．)
プログラムの実行終了時点で変数 $a$ に答えの値が保持されている必要がある．

プログラムの形式

プログラムの $1$ 行目にはプログラムの命令数を表す整数 $M(\geq 0)$ が書かれる． プログラムの $2$ 行目から $M+1$ 行目には $M$ 個の命令が書かれる．命令は上から下に順次実行される．
命令は次の $3$ つのいずれかである．
  • add X Y Z
    • $X$ に $Y+Z \pmod P$ を代入する．ここで $X$ は変数，$Y,Z$ は変数または配列 $A$ の要素である
  • mul X Y Z
    • $X$ に $Y\times Z \pmod P$ を代入する．ここで $X$ は変数，$Y,Z$ は変数または配列 $A$ の要素である
  • div X Y Z
    • $X$ に $Y/Z \pmod P$ を代入する．ここで $X$ は変数，$Y,Z$ は変数または配列 $A$ の要素であり，$Z\neq 0$ を満たす必要がある
$A$ の $i\ (1\leq i\leq N)$ 番目の要素を参照する場合は A[i] のように記述すること．

プログラム実行コード

コードテスト等で上のプログラムが動作します．ご利用ください．
プログラム実行コード（130 行程度あります．） 

P = 998244353

import re
import sys

pattern = re.compile(r"A\[(\-?\d+)\]$")


def parse_A(s: str):
    m = pattern.fullmatch(s)
    if m:
        return True, int(m.group(1))
    else:
        return False, None


def is_lowercase_letter(s: str) -> bool:
    return len(s) == 1 and "a" <= s <= "z"


def add(x, y):
    return (x + y) % P


def mul(x, y):
    return x * y % P


def div(x, y):
    if y == 0:
        assert False, "Division by zero is not allowed"
    return x * pow(y, P - 2, P) % P


n = int(input())
op = [""] * (n + 1)
A = [0] * (n + 1)
for i in range(1, n + 1):
    op[i], A[i] = input().split()
    A[i] = int(A[i])


x = 0
for i in range(1, n + 1):
    if op[i] == "+":
        x = add(x, A[i])
    elif op[i] == "*":
        x = mul(x, A[i])
    elif op[i] == "/":
        x = div(x, A[i])
    else:
        print("op[{}] is not '+', '*' and '/'".format(i))
        assert 0

vals = {}
for i in range(26):
    vals[chr(97 + i)] = 0

m = int(input())
if m < 0:
    print("M must be 0 or positive.")
    assert 0
add_count = 0
mul_count = 0
div_count = 0

for i in range(1, m + 1):
    OP, X, Y, Z = input().split()
    Yval = 0
    if not is_lowercase_letter(X):
        print("X[{}] is invalid format.".format(i))
        assert 0
    if is_lowercase_letter(Y):
        Yval = vals[Y]
    else:
        valid, val = parse_A(Y)
        if not valid:
            print("Y[{}] is invalid format.".format(i))
            assert 0
        else:
            if not 1 <= val <= n:
                print("Y[{}] is invalid format.".format(i))
                assert 0
            Yval = A[val]
    Zval = 0
    if is_lowercase_letter(Z):
        Zval = vals[Z]
    else:
        valid, val = parse_A(Z)
        if not valid:
            print("Z[{}] is invalid format.".format(i))
            assert 0
        else:
            if not 1 <= val <= n:
                print("Z[{}] is invalid format.".format(i))
                assert 0
            Zval = A[val]

    if OP == "add":
        vals[X] = add(Yval, Zval)
        add_count += 1
    elif OP == "mul":
        vals[X] = mul(Yval, Zval)
        mul_count += 1
    elif OP == "div":
        vals[X] = div(Yval, Zval)
        div_count += 1
    else:
        print("OP[{}] is invalid format.".format(i))
        assert 0


rest = sys.stdin.read().strip()
if rest:
    print("Unexpected extra input")
    assert 0

if add_count > 100:
    print("number of add is greater than 100")
    assert 0
if mul_count > 100:
    print("number of mul is greater than 100")
    assert 0
if div_count > 1:
    print("number of div is greater than 1")
    assert 0

print("Problem answer : {}".format(x))
print("Program 'a'    : {}".format(vals["a"]))

使い方

コードは Python で動作します． 問題の入力とプログラムの命令を順につなげたものを，Python のコードに入力として渡してください．Python コード冒頭の $P$ は好きな素数に置き換えられます．

サンプルの例 

4
+ 1
* 2
/ 3
+ 4
4
add b A[1] b
mul c A[2] b
div d c A[3]
add a A[4] d

入力

$N$
$op_1\ A_1$
$\vdots$
$op_N\ A_N$

  • $1\leq N\leq 100$
  • $op_i$ は +,*,/ のいずれか
  • $1\leq A_i\lt 10^8$
  • $N,A_i$ は整数

出力

問題文に書かれている仕様・形式に従ったプログラムを出力せよ．

サンプル

サンプル1
入力
4
+ 1
* 2
/ 3
+ 4
出力
4
add b A[1] b
mul c A[2] b
div d c A[3]
add a A[4] d

$P=998244353$ だった場合を考えます．

問題の答えは次のようになります．

  • はじめ，$x=0$ で初期化されています．
  • $i=1$ では，$x$ は $x+A_1\equiv 0+1\equiv1\pmod {998244353}$ になります．
  • $i=2$ では，$x$ は $x\times A_2\equiv 1\times 2\equiv2 \pmod {998244353}$ になります．
  • $i=3$ では，$x$ は $x/A_3\equiv 2/3\equiv 665496236 \pmod {998244353}$ になります．
  • $i=4$ では，$x$ は $x+A_4\equiv 4+665496236\equiv 665496240\pmod {998244353}$ になります．
  • 最終的に $x=665496240$ となります．
一方，プログラムは以下のように動作します．
  • はじめ，$a=b=c=\ldots=0$ で初期化されています．
  • $1$ 個目の命令では，$b$ は $A_1+b \equiv1+0\equiv 1\pmod {998244353}$ になります．
  • $2$ 個目の命令では，$c$ は $A_2\times b\equiv 2\times 1\equiv2 \pmod {998244353}$ になります．
  • $3$ 個目の命令では，$d$ は $c/A_3\equiv2/3\equiv 665496236 \pmod {998244353}$ になります．
  • $4$ 個目の命令では，$a$ は $A_4+d\equiv4+665496236\equiv 665496240\pmod {998244353}$ になります．
  • 最終的に $a=665496240$ となります．
問題の答えと，プログラムの $a$ が一致するため正しい出力です．プログラムの足し算の回数，掛け算の回数，割り算の回数の条件も満たしています．

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。