{"id":1193,"date":"2015-07-29T00:41:34","date_gmt":"2015-07-28T16:41:34","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1193"},"modified":"2015-07-29T00:41:34","modified_gmt":"2015-07-28T16:41:34","slug":"project-euler-434-rigid-graphs","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/project-euler-434-rigid-graphs\/","title":{"rendered":"Project Euler 434. Rigid graphs"},"content":{"rendered":"<p><a href=\"https:\/\/projecteuler.net\/problem=434\">https:\/\/projecteuler.net\/problem=434<\/a><\/p>\n<p><!--more--><\/p>\n<p><a href=\"http:\/\/mathworld.wolfram.com\/RigidGraph.html\">http:\/\/mathworld.wolfram.com\/RigidGraph.html<\/a><br \/>\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/Structural_rigidity\">https:\/\/en.wikipedia.org\/wiki\/Structural_rigidity<\/a><br \/>\n<a href=\"http:\/\/www.johannesbader.ch\/2013\/09\/project-euler-problem-434-rigid-graphs\/\">http:\/\/www.johannesbader.ch\/2013\/09\/project-euler-problem-434-rigid-graphs\/<\/a><\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(1e3) + 9;\r\nInt fact&#x5B;N], B&#x5B;N]&#x5B;N];\r\nint n;\r\n\r\nInt binom(int n, int m){\r\n    if (n&lt;m) return 0;\r\n    return fact&#x5B;n] \/ fact&#x5B;m] \/ fact&#x5B;n-m];\r\n}\r\n\r\nInt b(int a, int b){\r\n    if (a &gt;= b) return B&#x5B;a]&#x5B;b];\r\n    return B&#x5B;b]&#x5B;a];\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    n = 100; fact&#x5B;0] = 1; REP_1(i, n) fact&#x5B;i] = fact&#x5B;i-1] * i;\r\n    Int z = 0;\r\n\r\n    REP_1(i, n){\r\n        B&#x5B;i]&#x5B;0] = i == 1 ? 1 : 0;\r\n        REP_1(j, i){\r\n            B&#x5B;i]&#x5B;j] = pow(2, i*j);\r\n            REP_1(ii, i) FOR_1(jj, 0, j){\r\n                if (i == ii &amp;&amp; j == jj) break;\r\n                B&#x5B;i]&#x5B;j] -= binom(i-1, ii-1) * binom(j, jj) * b(ii, jj) * pow(2, (i-ii)*(j-jj));\r\n            }\r\n            z += B&#x5B;i]&#x5B;j];\r\n            if (i != j) z += B&#x5B;i]&#x5B;j];\r\n        }\r\n    }\r\n\r\n    cout &lt;&lt; z &lt;&lt; endl;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/projecteuler.net\/problem=434<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[143],"tags":[],"class_list":["post-1193","post","type-post","status-publish","format-standard","hentry","category-pe"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-jf","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1193","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1193"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1193\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1193"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1193"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1193"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}