結果

問題 No.990 N×Mマス計算(Kの倍数)
コンテスト
ユーザー 👑 tttmmmyyyy
提出日時 2026-11-12 22:39:51
言語 Fix
(1.6.1 + cp-library + minilib)
コンパイル:
fix_c _filename_
実行:
./a.out
結果
AC  
実行時間 37 ms / 2,000 ms
+ 999µs
コード長 2,379 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 10,153 ms
コンパイル使用メモリ 670,792 KB
実行使用メモリ 10,984 KB
最終ジャッジ日時 2026-11-12 22:40:04
合計ジャッジ時間 12,874 ms
ジャッジサーバーID
(参考情報)
judge1_0 / judge5_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
make: 'lib.o' は更新済みです.

ソースコード

diff #
raw source code

module Main;

// import BinaryHeap;
// import BoolArray;
import CPLib.Arithmetic;
// import CPLib.Bipartite;
// import CPLib.Bits;
// import CPLib.Convolution;
// import CPLib.DSegtree;
// import CPLib.Graph;
import CPLib.IO;
// import CPLib.LDSegtree;
// import CPLib.LSegtree;
// import CPLib.MaxFlow;
// import CPLib.Memoize;
// import CPLib.MinCostFlow;
// import CPLib.Misc;
// import CPLib.Monoid;
// import CPLib.Segtree;
// import CPLib.String;
// import CPLib.Trait;
// import CPLib.TwoSat;
// import CPLib.UnionFind;
// import CPLib.ZP;
import HashMap;
// import HashSet;

facts_to_divisors_rec : Array (I64, I64) -> I64 -> Array I64 -> Array I64 = |facts, acm, divs| (
    if facts.is_empty { divs.push_back(acm) };
    let (p, e) = facts.@(facts.@size - 1);
    let facts = facts.pop_back;
    range(0, e+1).fold((acm, divs), |n, (acm, divs)|
        let divs = facts_to_divisors_rec(facts, acm, divs);
        let acm = acm * p;
        (acm, divs)
    ).@1
);

facts_to_divisors : Array (I64, I64) -> Array I64 = |facts| (
    facts_to_divisors_rec(facts, 1, [])
);

main : IO () = (
    let n = *read_i; let m = *read_i; let k = *read_i;
    let op = *read_c;
    let bs = *read_is(m); let as = *read_is(n);
    let as = as.map(|x| x % k);
    let bs = bs.map(|x| x % k);
    let b_cnt = range(0, m).fold(HashMap::empty(m), |i, mp|
        let b = bs.@(i);
        match mp.find(b) {
            none() => mp.insert(b, 1),
            some(n) => mp.insert(b, n+1)
        }
    );
    let ans = if op == '+' {
        range(0, n).map(|ai|
            let a = as.@(ai);
            let b = (k - a) % k;
            b_cnt.find_or(b, 0)
        ).sum
    } else {
        let a_cnt = as.to_iter.fold(HashMap::empty(1344), |a, mp|
            let a = calc_gcd(a, k);
            match mp.find(a) {
                none() => mp.insert(a, 1),
                some(n) => mp.insert(a, n+1)
            }
        );
        let b_cnt = bs.to_iter.fold(HashMap::empty(1344), |a, mp|
            let a = calc_gcd(a, k);
            match mp.find(a) {
                none() => mp.insert(a, 1),
                some(n) => mp.insert(a, n+1)
            }
        );
        a_cnt.to_iter.product(b_cnt.to_iter).map(|((bk, bv), (ak, av))|
            if (bk * ak) % k == 0 {
                bv * av
            };
            0
        ).sum
    };
    ans.to_string.println
);
0