一道感觉好经典的题
mazeyu
posted @ 2015年5月10日 01:59
in 图论
, 791 阅读
体子告诉我有project euler之后就随便看了几道 发现都不会 果然还是太弱
有一道叫做robot walks
我先看了一篇题解 发现了自己也说不清的性质 写了个自己也不知道为什么的dp 然后居然过了
我写的时候感觉自己挺对的 后来越想越不知道为什么 然后就开始翻thread
翻得好辛苦 终于找到让我眼前一亮的东西了 原来这就是一个五边形形状的图
然后很多人都给出了公式
(Sum[(c^4 - 3 c^3 j + 4 c^2 j^2 - 2 c j^3 + j^4) Binomial[c, j]^5, {j, 0, c}] )/c^4
没想到基尔霍夫矩阵还能用在有向图 还能求回路个数
这个定理叫BEST定理 定理的名字真好听 具体可以翻论文
简单地说，用五边形的五个顶点代表五个方向 相邻方向之间的五条边代表五种位移 不管正的还是反的
首先证明五种位移个数一样多（运用五次单位根是至少四次方程的解， 非常巧妙，其他群论我没学好看不懂，其实我也不知道为什么五次单位根是至少四次方程的解，看来我什么都没学好，只是这个看上去比较基本）
然后把每条边分成相同数量的边 利用度数性质证明这是回路 顺便证明顺（逆）时针边都一样多 还能证明经过每个点一样多
然后枚举顺时针边数 用BEST定理求回路数 再求和
话说回来其实一开始我感觉晕是因为没搞清该考虑点还是考虑边 总之这道题好神
2022年8月07日 06:44
Punjab National Bank is a popular yet most preferred National Bank in India, and the Net Banking service for the bank allows its customers to utilize different services online without investing in the branch. PNB net banking new user As the modern days are invoking with the technology, the services from Banks through their Net Banking feature are in good spike, and there are multiple benefits for the customer who does get the access to the PNB Net Banking service.This makes them comfortable in using bank transactions at their fingertips, and yet the online banking is secure which guarded with unique credentials that only allow you to access the online portal.
2022年8月25日 17:55
Play Bartender Perfect Mix Game. We Unblocked it For You to Play at School. We at Unblocked Games 66 77 99 Unblocks All Games Like Bartender Perfect 2021. Unblocked Games GOGO is one of the game sites that are unblocked games at school that I secretly created. unblocked games for school, unblocked games 66 unblocked games 66,unblocked games happy wheels,unblocked games google sites,unblocked games 77,unblocked games 99.Play Bartender Perfect Mix Game. We Unblocked it For You to Play at School. We at Unblocked Games 66 77 99 Unblocks All Games Like Bartender Perfect 2021. Unblocked Games GOGO is one of the game sites that are unblocked games at school that I secretly created. unblocked games for school.
2023年4月13日 23:09
All the basic information about every celebrity is available now on the largest database of celeb networth post where you can find all the information and net worth of a singer, actor, businessman...
2023年7月12日 20:33
WBBSE 6th Class Syllabus 2024 Pdf File Format helps to get an idea About the Concepts and Topics Taught in class for a Subject During this Academic year 2024, Students will be able to Access the Clickable Download Links From where they can WBBSE 6th Class Syllabus 2024 Download the Syllabus of Bengali, English Medium All Subjects.WBBSE Recently Upload West Bengal 6th Class Syllabus 2024, WBBSE will Organise the Class Public Examinations in April 2024, West Bengal Every Year A Huge Number of Students Appeared for 6th Class Should Check the new Syllabus Details here.