結果

問題 No.2793 Mancala Master
コンテスト
ユーザー Lisp_Coder
提出日時 2024-06-22 17:41:45
言語 Common Lisp
(sbcl 2.5.0)
結果
AC  
実行時間 781 ms / 2,000 ms
コード長 978 bytes
コンパイル時間 524 ms
コンパイル使用メモリ 29,696 KB
実行使用メモリ 27,392 KB
最終ジャッジ日時 2024-06-25 10:45:23
合計ジャッジ時間 6,498 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 25 JUN 2024 10:45:16 AM):

; file: /home/judge/data/code/Main.lisp
; in: DEFUN MODINT998
;     (MOD CODEFORCES::X 998244353)
; 
; note: unable to
;   optimize
; due to type uncertainty:
;   The first argument is a REAL, not a SINGLE-FLOAT.
; 
; note: unable to
;   optimize
; due to type uncertainty:
;   The first argument is a REAL, not a DOUBLE-FLOAT.
; 
; note: unable to
;   optimize
; due to type uncertainty:
;   The first argument is a REAL, not a INTEGER.
; 
; note: unable to
;   convert division by 2^k to shift
; due to type uncertainty:
;   The first argument is a REAL, not a INTEGER.

; in: DEFUN MINT-POW
;     (> CODEFORCES::N 0)
; 
; note: unable to
;   open-code FLOAT to RATIONAL comparison
; due to type uncertainty:
;   The first argument is a REAL, not a SINGLE-FLOAT.
; 
; note: unable to
;   open-code FLOAT to RATIONAL comparison
; due to type uncertainty:
;   The first argument is a REAL, not a DOUBLE-FLOAT.
; 
; note: forced to do GENERIC-> (cost 10)
;       unable to do inline fixnum comparison (cost 3) because:
;       The first argument is a REAL, not a FIXNUM.
;       unable to do inline fixnum comparison (cost 4) because:
;       The first argument is a REAL, not a FIXNUM.
;       etc.

;     (* CODEFORCES::RESULT CODEFORCES::BASE)
; 
; note: forced to do GENERIC-* (cost 30)
;       unable to do inline fixnum arithmetic (cost 2) because:
;       The first argument is a (OR FLOAT (RATIONAL 0 (998244353))), not a FIXNUM.
;       The second argument is a (OR FLOAT (RATIONAL 0 (998244353))), not a FIXNUM.
;       The result is a (VALUES (OR FLOAT (RATIONAL 0 (996491788296388609)))
;                               &OPTIONAL), not a (VALUES FIXNUM &OPTIONAL).
;       unable to do inline (signed-byte 64) arithmetic (cost 4) because:
;       The first argument is a (OR FLOAT (RATIONAL 0 (998244353))), not a (SIGNED-BYTE
;

ソースコード

diff # 

(defpackage :codeforces
  (:use :cl :sb-int))
(in-package :codeforces)

(declaim (optimize (speed 3) (safety 0)))

(defun modint998 (x)
  (mod x 998244353))

(defun mint-pow (x n)
  (let ((result 1)
        (base (modint998 x)))
    (loop while (> n 0) do
          (when (oddp n)
            (setf result (modint998 (* result base))))
          (setf base (modint998 (* base base)))
          (setf n (floor n 2)))
    result))

(defun solve (n k a)
  (let ((ans 1))
    (loop for i from 1 to n do
          (setf ans (modint998 (* ans (- (mint-pow k i) 1)))))
    (loop for i from 0 below n do
          (setf ans (modint998 (* ans (mint-pow k (* (+ i 1) (1- (aref a i))))))))
    (princ ans) (terpri)))

(defun main ()
  (let ((num-cases (read)))
    (loop for _ from 1 to num-cases do
          (let* ((n (read))
                 (k (read))
                 (a (make-array n :initial-contents (loop for _ from 1 to n collect (read)))))
            (solve n k a)))))

(main)
0