Submission #3027620

---

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.                      AGC_025_B.
DATA                             DIVISION.
WORKING-STORAGE                  SECTION.
    01 INF     EXTERNAL PIC 9(10).

*> Fact
    01 F1 EXTERNAL.
        03 F PIC 9(10) OCCURS 300000 INDEXED BY FIX.

    01 V1 EXTERNAL.
        03 V PIC 9(10) OCCURS 300000 INDEXED BY VIX.

*> Inverse
    01 IV1 EXTERNAL.
        03 IV PIC 9(10) OCCURS 300000 INDEXED BY IIX MIX.

    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 dv      PIC 9(12).

    01 dvx     PIC 9(19).

    01 i       PIC 9(18) BINARY.
    01 j       PIC 9(18) BINARY.

*> N!
    01 x       PIC 9(10).

    01 smalla  PIC 9(10) BINARY.
    01 biga    PIC 9(10) BINARY.

    01 smallb  PIC 9(10) BINARY.
    01 bigb    PIC 9(10) BINARY.

    01 d_num   PIC 9(10).
    01 d_ret   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 dv REMAINDER rm

        IF ZERO = rm AND dv <= N
            MOVE dv TO b
*> a
            MOVE 1 TO smalla
            IF ZERO NOT = a
                MOVE a TO smalla
            END-IF
*> N - a
            MOVE 1 TO biga
            IF a NOT = N
                SUBTRACT a FROM N GIVING tmp
                MOVE tmp TO biga
            END-IF
*> b
            MOVE 1 TO smallb
            IF ZERO NOT = b
                MOVE b TO smallb
            END-IF
*> N - b
            MOVE 1 TO bigb
            IF b NOT = N
                SUBTRACT b FROM N GIVING tmp
                MOVE tmp TO bigb
            END-IF
*> 逆元
*> (1 / a!) * (1 / (N - a)!)
            SET IIX TO smalla
            SET MIX TO biga
            MULTIPLY IV(IIX) BY IV(MIX) GIVING dvx
            DIVIDE INF INTO dvx GIVING dvx REMAINDER inva
*> 逆元
*> (1 / b!) * (1 / (N - b)!)
            SET IIX TO smallb
            SET MIX TO bigb
            MULTIPLY IV(IIX) BY IV(MIX) GIVING dvx
            DIVIDE INF INTO dvx GIVING dvx REMAINDER invb
*> combination a
            MULTIPLY x BY inva GIVING dvx
            DIVIDE INF INTO dvx GIVING dvx REMAINDER comba
*> combination b
            MULTIPLY x BY invb GIVING dvx
            DIVIDE INF INTO dvx GIVING dvx REMAINDER combb
*> combination a * combination b
            MULTIPLY comba BY combb GIVING dvx
            DIVIDE INF INTO dvx GIVING dvx REMAINDER 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 AGC_025_B.

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.
*> 階乗テーブル F(i)
*> 逆元テーブル IV(i)
DATA                             DIVISION.
WORKING-STORAGE                  SECTION.
    01 INF     EXTERNAL PIC 9(10).

*> Factorial
    01 F1 EXTERNAL.
        03 F PIC 9(10) OCCURS 300000 INDEXED BY FIX.

    01 V1 EXTERNAL.
        03 V PIC 9(10) OCCURS 300000 INDEXED BY VIX.

*> Inverse
    01 IV1 EXTERNAL.
        03 IV PIC 9(10) OCCURS 300000 INDEXED BY IIX.

*> 2
    01 BNY     EXTERNAL PIC 9(1).

    01 VINF    PIC 9(10).

    01 i       PIC 9(10) BINARY.
    01 mi      PIC 9(10) BINARY.

    01 m       PIC 9(10) BINARY.

    01 tmp     PIC 9(19).
    01 d       PIC 9(19).

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)

    SET VIX TO i
    MOVE 1 TO V(VIX)

    SET IIX TO i
    MOVE 1 TO IV(IIX)

*> 2
    PERFORM VARYING i FROM BNY BY 1 UNTIL d_num < i

        MULTIPLY i BY F(FIX) GIVING tmp
        DIVIDE INF INTO tmp GIVING d REMAINDER m

        SET FIX UP BY 1
        MOVE m TO F(FIX)

*> INF / i
*> INF % i
        DIVIDE i INTO INF GIVING d REMAINDER m

*> V(INF % i) * (INF / i)
        SET VIX TO m
        MULTIPLY V(VIX) BY d

*> V(INF % i) * (INF / i) % INF
        DIVIDE INF INTO d GIVING d REMAINDER m

*> V(i) = INF - V(INF % i) * (INF / i) % INF
        SET VIX TO i
        COMPUTE V(VIX) = INF - m

*> IV(i - 1) * V(i)
        SUBTRACT 1 FROM i GIVING mi

        SET IIX TO mi
        MULTIPLY IV(IIX) BY V(VIX) GIVING d

*> IV(i - 1) * V(i) % INF
        DIVIDE INF INTO d GIVING d REMAINDER m

*> IV(i) = IV(i - 1) * v(i) % INF
        SET IIX UP BY 1
        COMPUTE IV(IIX) = m

    END-PERFORM.

    MOVE F(FIX) TO d_ret.

END PROGRAM FACT_CALC.

Submission Info

Judge Result