なんらかの出力ハッシュの方法を決める？

[yosupo06]

実際に出力するには非現実的な量の出力をしたい問題というのがある(素数篩、Aho-Corasickで出力位置全出力など)

こういうのに素直に対処するには、それをサブルーチンとして含めるような問題(例えば、素数の総和を出力など)を用意するというのがある

ただ、出力をなんらかの手段でハッシュ化してしまうというのも手かもしれない。その場合は問題としてあんまり簡潔じゃなくなってしまうが

[tozangezan]

xorとかじゃダメなんですか

[yosupo06]

同じものを2個出力するときに消えるとかが難点

[yosupo06]

三角形列挙で考えたこと

要件

• 計算量が重くない: 少なくともO(M sqrt M)回計算できないといけない
• 可換性がある: トライアングルの出力順を気にする必要がない
• 全要素が影響する: ちょっと間違えたら死ぬというのが好ましい
• 他の問題に使える: 問題ごとにハッシュの方法が違ったら使いにくい
• (Optional: 不正対策): ハッシュの性質を生かした変な解法が出来ない

これを踏まえるとhash(triangle)を列挙して何らかの可換性がある操作でまとめるのが良さそう

• hash(triangle) ^ hash(triangle) ^ ... ^ hash(triangle)
• (hash(triangle) + hash(triangle) + ... + hash(triangle)) % 998244353
• (hash(triangle) * hash(triangle) * ... * hash(triangle)) % 998244353

など、1つめは64bitにするとjavaが困るらしいので注意、3つめはhash(triangle)が0にならないように

[yosupo06]

xorは[x, x]が全部同一視、+は[x, -x]が全部同一視されることを考えると*が一番いい気がするなぁ

[yosupo06]

bit演算系(xorとか)とmod系の操作を混ぜればどうしようもなくなるという話があったな