atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ 線形代数 転置原理 imos 法 1. 概要 転置原理は，ある問題の解法から別の問題（転置問題）の解法を機械的に導出するという，意外性のある面白い考え方です． 特に多項式の多点評価のアルゴリズムの定数倍高速化が転置原理を通して発見されたことが有名です．他には形式的べき級数の合成のアルゴリズムも，転置原理によって見通し良く導出できることが知られています． 本記事では転置原理についての入門的な解説を行います．また転置原理を競技プログラミング初心者レベルの易しい具体例に適用し，アルゴリズムが機械的に導出される様子を確認します． 転置原理は直感的な理解をしづらいこと，比較的高度なアルゴリズムの導出だけが有名であることもあり，本記事執筆… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Ftransposition_principle" title="転置原理入門 - AtCoderInfo" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/158934417/1702097020779738 Hatena Blog https://hatena.blog 2026-04-10 14:09:25 rich https://info.atcoder.jp/entry/algorithm_lectures/transposition_principle 1.0 100%