vket summer 2026 LT

Transcript

1. Lightning Talk FPS で殴る二項係数の畳み込み ぷせうど (seekworser) 2026-07-22
2. プロフィール ぷせうど (seekworser) • AtCoder 黄色！ 2269 • 競プロとお写真 • 数え上げと性質を丁寧に眺める問題 が好き 2
3. ちょっとめんどくさい 二項係数の 総和 求めたいとき、 ありますよね？ 3
4. めんどくさい二項係数の総和 𝑛 ∑ 𝑘( ) 𝑘 𝑘 4
5. めんどくさい二項係数の総和 𝑛 ∑ 𝑘( ) 𝑘 𝑘 5
6. めんどくさい二項係数の総和 𝑛 𝑛−1 ∑ 𝑘( ) = ∑ 𝑛( 𝑘−1 ) 𝑘 一段下げる 𝑘 𝑘 6
7. めんどくさい二項係数の総和 𝑛 𝑛−1 ∑ 𝑘( ) = 𝑛 ∑( ) 𝑘 𝑘−1 外に出す 𝑘 𝑘 7
8. めんどくさい二項係数の総和 𝑛 ∑ 𝑘( ) = 𝑛 2𝑛−1 𝑘 二項定理 𝑘 8
9. めんどくさい二項係数の総和 𝑛 ∑𝑘 ( ) 𝑘 𝑘 2 9
10. めんどくさい二項係数の総和 𝑛 ∑ 𝑘2 ( ) 𝑘 𝑘 𝑛 = ∑ (𝑘(𝑘 − 1) + 𝑘) ( ) 𝑘 分解 𝑘 10
11. めんどくさい二項係数の総和 𝑛 ∑ 𝑘2 ( ) 𝑘 𝑘 𝑛−2 = ∑( 𝑛(𝑛 − 1)( 𝑘−2 ) 2 段落とす 𝑘 𝑛−1 + 𝑛( )) 𝑘−1 11
12. めんどくさい二項係数の総和 𝑛 ∑ 𝑘 ( ) = 𝑛(𝑛 − 1)2𝑛−2 + 𝑛2𝑛−1 𝑘 二項定理 𝑘 2 12
13. めんどくさい二項係数の総和 𝑛 ・・。 ∑𝑘 ( ) ・ 𝑘 𝑘 3 13
14. FPS（形式的べき級数） 𝑎0 , 𝑎1 , 𝑎2 , … ↕ 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥2 + … 14
15. FPS（形式的べき級数） 𝑝 𝑞 ∑( )( ) 𝑘 𝑐−𝑘 𝑘 15
16. FPS（形式的べき級数） 𝑝 𝑞 ∑( )( ) = ∑𝑘 [𝑥𝑘 ](1 + 𝑥)𝑝 [𝑥𝑐−𝑘 ](1 + 𝑥)𝑞 𝑘 𝑐−𝑘 二項係数を FPS で表現 𝑘 16
17. FPS（形式的べき級数） 𝑝 𝑞 ∑( )( ) = [𝑥𝑐 ](1 + 𝑥)𝑝 (1 + 𝑥)𝑞 𝑘 𝑐−𝑘 積の係数 𝑘 17
18. FPS（形式的べき級数） 𝑝 𝑞 ∑( )( ) = [𝑥𝑐 ] (1 + 𝑥)𝑝+𝑞 𝑘 𝑐−𝑘 まとめる 𝑘 18
19. FPS（形式的べき級数） 𝑝 𝑞 𝑝+𝑞 ∑( )( )= ( 𝑐 ) 𝑘 𝑐−𝑘 係数を見る 𝑘 19
20. FPS: 𝑘 を作用素にする 𝑑 𝐷=𝑥 𝑑𝑥 𝐷𝑥𝑘 = 𝑘𝑥𝑘 𝑘 が出る 20
21. FPS: 𝑘 を作用素にする 𝑛 ∑ 𝑘 ( ) = (𝐷3 (1 + 𝑥)𝑛 ) |𝑥=1 𝑘 𝑘 を 𝐷 にする 𝑘 3 3 3 アドホックな式変形を微分作用素として 機械的に処理できる！ 21
22. ABC290F Maximum Diameter (diff 2300) 𝑛 𝑛−3 ∑(𝑘 + 1)( )( ) 𝑘 𝑛−2−𝑘 𝑘 22
23. ABC290F Maximum Diameter (diff 2300) 𝑛 𝑛−3 ∑(𝑘 + 1)( )( ) 𝑘 𝑛−2−𝑘 𝑘 = [𝑥𝑛−2 ](𝐷 + 1)(1 + 𝑥)𝑛 (1 + 𝑥)𝑛−3 係数抽出 23
24. ABC290F Maximum Diameter (diff 2300) 𝑛 𝑛−3 ∑(𝑘 + 1)( )( ) 𝑘 𝑛 − 2 − 𝑘 𝑘 𝑛−1 = [𝑥𝑛−2 ] (𝑛𝑥(1 + 𝑥) = [𝑥 𝑛−2 + (1 + 𝑥)𝑛 ) (1 + 𝑥)𝑛−3 作用させる 2𝑛−4 ](𝑛𝑥(1 + 𝑥) + (1 + 𝑥)2𝑛−3 ) 24
25. ABC290F Maximum Diameter (diff 2300) 𝑛 𝑛−3 ∑(𝑘 + 1)( )( ) 𝑘 𝑛−2−𝑘 𝑘 2𝑛−4 2𝑛−3 = 𝑛( 𝑛−3 ) + ( 𝑛−2 ) 係数を見る 25
26. まとめ • 数式を多項式と紐づけて考えると嬉しい！ 𝑑 • 𝑘 倍は 𝐷 = 𝑥 𝑑𝑥 • 手で分解する代わりに FPS に作用させることで アドホックな式変形を回避できる 26