典型タグ

乱択代数fingerprint

multiset・素因数指数vector・巨大整数式をランダムな体元やXOR和へ写し、非同値対象が衝突する確率を評価する。

この典型を扱う単元: 乱択代数fingerprint

検索別名: Zobrist hash、multiset hash、randomized algebraic fingerprint

未知問からこの典型を見つける手掛かり

扱う対象
  • multiset
  • 多項式値
  • 指数vector
使う手掛かり
  • 完全冪判定
  • 式の積が等しい
  • 順序を無視
保つ不変量
  • 線形/乗法的合成
  • 衝突上界
求めるもの
  • 確率的等価判定
  • 集合同値query
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: モデル変換

関連する典型

    学習成果と学習単位

    • multiset・素因数指数vector・巨大整数式をランダムな体元やXOR和へ写し、非同値対象が衝突する確率を評価する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

      乱択代数fingerprintで学ぶ

    代表問題

    この典型の考え方を具体的な問題で確かめるための入口です。

    関連問題

    この典型が主タグまたは補助タグとして付いている問題です。