Submission #3025942
Source Code Expand
*> Combination
*> 全体でn個の選択から縦(または横)を
*> r個選ぶ組み合わせ
*> nCr
*> = nPr / r!
*> = n! / {(n - r)! * r!}
*> (W + H)C(W > H ? W : H)
*> = (W + H)! / {(W + H - biggerWH)! * biggerWH!}
PROGRAM-ID. ABC_999_D.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 INF EXTERNAL PIC 9(10).
*> Fact
01 F1 EXTERNAL.
03 F PIC 9(10) OCCURS 150000 INDEXED BY FIX.
01 INF2 PIC 9(10).
01 INP PIC X(34).
01 N PIC 9(6).
01 AX PIC 9(6).
01 BX PIC 9(6).
01 K PIC 9(12).
01 a PIC 9(6) BINARY.
01 b PIC 9(6) BINARY.
01 tmp PIC 9(12) BINARY.
01 rm PIC 9(12).
01 b_txt PIC X(32).
01 d_num PIC 9(10).
01 d_ret PIC 9(10).
01 i PIC 9(18) BINARY.
01 j PIC 9(18) BINARY.
*> N!
01 x PIC 9(10).
*> smalla!
01 smalla PIC 9(10).
*> biga!
01 biga PIC 9(10).
*> smallb!
01 smallb PIC 9(10).
*> bigb!
01 bigb PIC 9(10).
*> smalla! * biga!
01 y PIC 9(10).
*> smallb! * bigb!
01 z PIC 9(10).
*> inverse a
01 inva PIC 9(10).
*> inverse b
01 invb PIC 9(10).
*> combination a
01 comba PIC 9(10).
*> combination b
01 combb PIC 9(10).
01 m PIC 9(10).
01 sm PIC 9(18).
01 ans PIC X(11).
01 ZS PIC Z(18)9.
01 DUMMY PIC X(1).
PROCEDURE DIVISION.
ACCEPT INP.
UNSTRING INP
DELIMITED BY SPACE
INTO N AX BX K.
*> 外部データ
*> 実行単位中の複数のプログラムで使用する定数を設定
CALL "SET_EXTERNAL".
SUBTRACT 2 FROM INF GIVING INF2.
MOVE N TO d_num.
*> 階乗計算
CALL "FACT_CALC" USING BY CONTENT d_num
BY REFERENCE d_ret.
*> (a + b)!
MOVE d_ret TO x.
MOVE ZERO TO sm.
PERFORM VARYING i FROM ZERO BY 1 UNTIL N < i
IF ZERO = K
ADD 1 TO sm
EXIT PERFORM
END-IF
MOVE i TO a
MULTIPLY AX BY a GIVING tmp
IF K < tmp
EXIT PERFORM
END-IF
SUBTRACT tmp FROM K GIVING rm
DIVIDE BX INTO rm GIVING b REMAINDER rm
IF ZERO = rm
*> a!
SET FIX TO a
MOVE F(FIX) TO smalla
*> (N - a)!
SUBTRACT a FROM N GIVING tmp
SET FIX TO tmp
MOVE F(FIX) TO biga
*> b!
SET FIX TO b
MOVE F(FIX) TO smallb
*> (N - b)!
SUBTRACT b FROM N GIVING tmp
SET FIX TO tmp
MOVE F(FIX) TO bigb
*> a! * (N - a)!
CALL "MOD_MULTI" USING BY CONTENT smalla
BY CONTENT biga
BY REFERENCE y
*> 逆元
*> 1 / a! * (N - a)!
CALL "MOD_CALC" USING BY CONTENT y
BY CONTENT INF2
BY REFERENCE inva
*> b! * (N - b)!
CALL "MOD_MULTI" USING BY CONTENT smallb
BY CONTENT bigb
BY REFERENCE z
*> 逆元
*> 1 / b! * (N - b)!
CALL "MOD_CALC" USING BY CONTENT z
BY CONTENT INF2
BY REFERENCE invb
*> combination a
CALL "MOD_MULTI" USING BY CONTENT x
BY CONTENT inva
BY REFERENCE comba
*> combination b
CALL "MOD_MULTI" USING BY CONTENT x
BY CONTENT invb
BY REFERENCE combb
*> combination a * combination b
CALL "MOD_MULTI" USING BY CONTENT comba
BY CONTENT combb
BY REFERENCE m
ADD m TO sm
IF INF < sm
SUBTRACT INF FROM sm
END-IF
END-IF
END-PERFORM.
MOVE sm TO ZS.
PERFORM UNANS.
DISPLAY ans(1:FUNCTION STORED-CHAR-LENGTH(ans)).
STOP RUN.
UNANS SECTION.
UNSTRING
ZS DELIMITED BY ALL SPACE
INTO DUMMY ans
END-UNSTRING.
END PROGRAM ABC_999_D.
PROGRAM-ID. SET_EXTERNAL.
*> 外部データ
*> 実行単位中の複数のプログラムで使用する定数を設定
*> external data
*> Set constants used for multiple programs in running unit
DATA DIVISION.
WORKING-STORAGE SECTION.
01 INF EXTERNAL PIC 9(10).
01 BNY EXTERNAL PIC 9(1).
01 BIT4 EXTERNAL PIC 9(1).
01 BYT4 EXTERNAL PIC 9(1).
01 BYT32 EXTERNAL PIC 9(2).
01 BYT256 EXTERNAL PIC 9(3).
01 HXD EXTERNAL PIC 9(2).
01 NUM_OFF EXTERNAL PIC 9(1).
01 NUM_ON EXTERNAL PIC 9(1).
01 NUM_X EXTERNAL PIC 9(1).
01 OCT EXTERNAL PIC 9(1).
PROCEDURE DIVISION.
MOVE 998244353 TO INF.
MOVE 2 TO BNY.
MOVE 4 TO BIT4.
MOVE 4 TO BYT4.
MOVE 32 TO BYT32.
MOVE 256 TO BYT256.
MOVE 16 TO HXD.
MOVE 0 TO NUM_OFF.
MOVE 1 TO NUM_ON.
MOVE 9 TO NUM_X.
MOVE 8 TO OCT.
END PROGRAM SET_EXTERNAL.
PROGRAM-ID. FACT_CALC.
*> 階乗を計算する (a!)
DATA DIVISION.
WORKING-STORAGE SECTION.
01 INF EXTERNAL PIC 9(10).
01 F1 EXTERNAL.
03 F PIC 9(10) OCCURS 150000 INDEXED BY FIX.
*> 2
01 BNY EXTERNAL PIC 9(1).
01 i PIC 9(10) BINARY.
01 tmpi PIC 9(10) BINARY.
01 d_i PIC 9(10).
LINKAGE SECTION.
*> (IN) d_num
*> (OUT) d_ret
01 d_num PIC 9(10).
01 d_ret PIC 9(10).
PROCEDURE DIVISION USING d_num d_ret.
MOVE 1 TO i.
SET FIX TO i.
MOVE 1 TO F(FIX).
*> 2
PERFORM VARYING i FROM BNY BY 1 UNTIL d_num < i
SUBTRACT 1 FROM i GIVING tmpi
SET FIX TO tmpi
MOVE i TO d_i
CALL "MOD_MULTI" USING BY CONTENT F(FIX)
BY CONTENT d_i
BY REFERENCE d_ret
SET FIX TO i
MOVE d_ret TO F(FIX)
END-PERFORM.
MOVE F(d_num) TO d_ret.
END PROGRAM FACT_CALC.
PROGRAM-ID. MOD_MULTI.
*> aとbを掛けた値をmodする (a * b mod p)
DATA DIVISION.
WORKING-STORAGE SECTION.
01 INF EXTERNAL PIC 9(10).
*> 4
01 BIT4 EXTERNAL PIC 9(1).
*> 2
01 BNY EXTERNAL PIC 9(1).
*> 4
01 BYT4 EXTERNAL PIC 9(1).
*> 32
01 BYT32 EXTERNAL PIC 9(2).
*> 256
01 BYT256 EXTERNAL PIC 9(3).
*> 16
01 HXD EXTERNAL PIC 9(2).
*> 8
01 OCT EXTERNAL PIC 9(1).
*> 1
01 NUM_ON EXTERNAL PIC 9(1).
01 d PIC 9(10).
01 md PIC 9(10).
01 m PIC 9(1).
LINKAGE SECTION.
*> (IN) d_a
*> d_b
*> (OUT) d_ret
01 d_a PIC 9(10).
01 d_b PIC 9(10).
01 d_ret PIC 9(10).
PROCEDURE DIVISION USING d_a d_b d_ret.
MOVE ZERO TO d_ret.
DIVIDE INF INTO d_a GIVING d REMAINDER md.
PERFORM UNTIL d_b <= ZERO
DIVIDE BNY INTO d_b GIVING d REMAINDER m
IF NUM_ON = m
ADD md TO d_ret
IF INF < d_ret
SUBTRACT INF FROM d_ret
END-IF
END-IF
*> 2
*> left shift
MULTIPLY BNY BY md
IF INF < md
SUBTRACT INF FROM md
END-IF
*> 2
*> right shift
DIVIDE BNY INTO d_b
END-PERFORM.
END PROGRAM MOD_MULTI.
PROGRAM-ID. MOD_CALC.
*> aのb乗をpで割った余りを計算する (a ^ b mod p)
DATA DIVISION.
WORKING-STORAGE SECTION.
01 INF EXTERNAL PIC 9(10).
01 tmp PIC 9(10).
01 d PIC 9(10).
01 m PIC 9(1).
*> 4
01 BIT4 EXTERNAL PIC 9(1).
*> 2
01 BNY EXTERNAL PIC 9(1).
*> 4
01 BYT4 EXTERNAL PIC 9(1).
*> 32
01 BYT32 EXTERNAL PIC 9(2).
*> 256
01 BYT256 EXTERNAL PIC 9(3).
*> 16
01 HXD EXTERNAL PIC 9(2).
*> 8
01 OCT EXTERNAL PIC 9(1).
*> 0
01 NUM_OFF EXTERNAL PIC 9(1).
LINKAGE SECTION.
*> (IN) d_a
*> d_b
*> (OUT) d_ret
01 d_a PIC 9(10).
01 d_b PIC 9(10).
01 d_ret PIC 9(10).
PROCEDURE DIVISION USING d_a d_b d_ret.
*> O(log b)
MOVE ZERO TO tmp.
IF ZERO = d_b
MOVE 1 TO d_ret
ELSE
DIVIDE BNY INTO d_b GIVING d REMAINDER m
IF NUM_OFF = m
*> 偶数 bを半分にできる
DIVIDE BNY INTO d_b
CALL "MOD_CALC" USING BY CONTENT d_a
BY CONTENT d_b
BY REFERENCE tmp
CALL "MOD_MULTI" USING BY CONTENT tmp
BY CONTENT tmp
BY REFERENCE d_ret
ELSE
*> 奇数 -1乗から1乗をかける
SUBTRACT 1 FROM d_b
CALL "MOD_CALC" USING BY CONTENT d_a
BY CONTENT d_b
BY REFERENCE tmp
CALL "MOD_MULTI" USING BY CONTENT d_a
BY CONTENT tmp
BY REFERENCE d_ret
END-IF
END-IF.
END PROGRAM MOD_CALC.
Submission Info
| Submission Time | |
|---|---|
| Task | B - RGB Coloring |
| User | ShinjiSHIBATA |
| Language | COBOL - Free (OpenCOBOL 1.1.0) |
| Score | 0 |
| Code Size | 10095 Byte |
| Status | TLE |
| Exec Time | 2103 ms |
| Memory | 1536 KB |
Judge Result
| Set Name | Sample | All | ||||||
|---|---|---|---|---|---|---|---|---|
| Score / Max Score | 0 / 0 | 0 / 700 | ||||||
| Status |
|
|
| Set Name | Test Cases |
|---|---|
| Sample | sample01.txt, sample02.txt, sample03.txt |
| All | sample01.txt, sample02.txt, sample03.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, sample01.txt, sample02.txt, sample03.txt |
| Case Name | Status | Exec Time | Memory |
|---|---|---|---|
| in01.txt | TLE | 2103 ms | 1408 KB |
| in02.txt | TLE | 2103 ms | 1408 KB |
| in03.txt | TLE | 2103 ms | 1408 KB |
| in04.txt | TLE | 2103 ms | 1408 KB |
| in05.txt | TLE | 2103 ms | 1536 KB |
| in06.txt | TLE | 2103 ms | 1408 KB |
| in07.txt | TLE | 2103 ms | 1408 KB |
| in08.txt | AC | 1705 ms | 1280 KB |
| in09.txt | TLE | 2103 ms | 1408 KB |
| in10.txt | TLE | 2103 ms | 1408 KB |
| in11.txt | TLE | 2103 ms | 1408 KB |
| in12.txt | TLE | 2018 ms | 1408 KB |
| in13.txt | TLE | 2103 ms | 1408 KB |
| in14.txt | TLE | 2103 ms | 768 KB |
| in15.txt | TLE | 2103 ms | 1280 KB |
| in16.txt | TLE | 2103 ms | 768 KB |
| in17.txt | TLE | 2103 ms | 1408 KB |
| in18.txt | TLE | 2103 ms | 1408 KB |
| in19.txt | TLE | 2103 ms | 1408 KB |
| in20.txt | TLE | 2103 ms | 1408 KB |
| in21.txt | AC | 1 ms | 384 KB |
| sample01.txt | AC | 8 ms | 384 KB |
| sample02.txt | AC | 1 ms | 384 KB |
| sample03.txt | AC | 1700 ms | 1280 KB |