Problem D. Liars and Serge
\n.. \u6709 n \u4e2a\u4eba\u3002\u3002\u8be2\u95ee\u6bcf\u4e2a\u4eba\u6709\u591a\u5c11\u4e2a Liars\u3002\u3002\u3002\u6bcf\u4e2a\u4eba\u90fd\u77e5\u9053\u6709\u591a\u5c11 Liars\u3002\u3002\u3002\u8bf4\u771f\u8bdd\u7684\u4eba\u8fd4\u56de\u7684\u603b\u662f\u7b54\u6848\u3002\u3002\u8bf4\u5047\u8bdd\u7684\u4eba\u4ece [1, n] \u4e2d\u4e0d\u662f\u7b54\u6848\u7684\u67d0\u4e2a\u503c\u3002\u3002
\n\u3002\u3002\u95ee\u6709\u591a\u5c11\u79cd\u56de\u7b54\u65b9\u6848\u3002\u3002\u53ef\u4ee5\u786e\u5b9a \u6070\u597d\u6709 k \u4e2a \u8bf4\u8c0e\u8005\u3002\u3002\u3002
\n( 1 \u2264 k \u2264 n \u2264 2^8 …n \u4e3a 2 \u7684\u6574\u6b21\u5e42\u3002\u3002<\/p>\n
Problem E. Lucky Arrays
\n\u7ed9\u5b9a n \u4e2a\u5143\u7d20\u7684\u6570\u5217\u3002\u6bcf\u4e2a\u6570\u5b57\u53ef\u4ee5\u662f 1\u30012\u30013 \u4ee5\u53ca\u5f85\u5b9a\u4e09\u79cd\u72b6\u6001\u3002\u3002\u5f85\u5b9a\u7684\u8bdd\u53ef\u4ee5\u4efb\u53d6 1\u30012\u30013 \u4e09\u8005\u4e4b\u4e00\u3002
\n\u7ed9\u5b9a\u4e00\u4e2a 3*3 \u7684\u5408\u6cd5\u76f8\u90bb\u77e9\u9635 aij\u3002\u3002\u8868\u793a\u76f8\u90bb\u7684\u4f4d\u7f6e\u5982\u679c\u662f i,j \u7684\u8bdd\u662f\u5426\u5408\u6cd5\u3002\u3002\u3002
\n\u521d\u59cb\u6240\u6709\u4f4d\u7f6e\u90fd\u662f\u5f85\u5b9a\u3002\u3002m \u4e2a\u64cd\u4f5c\u3002\u3002\u6bcf\u4e2a\u64cd\u4f5c\u4fee\u6539\u5176\u4e2d\u4e00\u4e2a\u6570\u7684\u72b6\u6001\u3002\u3002\u7136\u540e\u8be2\u95ee\u5f53\u524d\u6709\u591a\u5c11\u5408\u6cd5\u6570\u5217\u3002\u3002\u3002
\n(1\u2009\u2264\u2009n,\u2009m\u2009\u2264\u200977777 .. <\/p>\n
<\/p>\n
…
\nProblem D. Liars and Serge
\n\u7ec4\u5408 DP\u3002\u3002\u8003\u8651\u5230\u5982\u679c\u56de\u7b54 i \u7684\u4eba\u6570\u4e0d\u662f i \u90a3\u4e48\u8fd9\u4e9b\u4e00\u5b9a\u90fd\u5728\u8bf4\u8c0e\u3002\u3002
\ndp[i][j][k] \u8868\u793a\u5f53\u524d\u8003\u5bdf\u7684\u662f\u56de\u7b54 i \u7684\u4e00\u7ec4\uff0c\u4e14\u5df2\u7ecf\u6709 j \u4e2a\u4eba\u56de\u7b54\u8fc7\u4e86\u5176\u4e2d\u786e\u5b9a k \u4e2a\u4eba\u5728\u8bf4\u8c0e\u7684\u65b9\u6848\u6570\u3002
\n\u3002\u3002\u679a\u4e3e\u56de\u7b54\u7b54\u6848 i \u7684\u6709\u591a\u5c11\u4eba\u5373\u53ef\u3002\u3002O(n4) DP\u3002\u3002\u3002
\n\u3002\u3002\u3002\u4f1a\u7a0d\u7a0d\u8d85\u65f6\u3002\u3002\u6700\u540e\u6ce8\u610f\u5230 n \u5f88\u7a00\u758f\u53ef\u4ee5\u6253\u8868\u3002\u3002<\/p>\n
Problem E. Lucky Arrays
\n\u305f\u3060\u666e\u901a\u306e\u30bb\u30b0\u30e1\u30f3\u30c8\u6728\u3060\u3051\u3002\u3002<\/p>\n
D..<\/a> Brief description: Problem D. Liars and Serge .. \u6709 n \u4e2a\u4eba\u3002\u3002\u8be2\u95ee\u6bcf\u4e2a\u4eba\u6709\u591a\u5c11\u4e2a Liars\u3002\u3002\u3002\u6bcf\u4e2a\u4eba\u90fd\u77e5\u9053\u6709\u591a\u5c11 Liars\u3002\u3002\u3002\u8bf4\u771f\u8bdd\u7684\u4eba\u8fd4\u56de\u7684\u603b\u662f\u7b54\u6848\u3002\u3002\u8bf4\u5047\u8bdd\u7684\u4eba\u4ece [1, n] \u4e2d\u4e0d\u662f\u7b54\u6848\u7684\u67d0\u4e2a\u503c\u3002\u3002 \u3002\u3002\u95ee\u6709\u591a\u5c11\u79cd\u56de\u7b54\u65b9\u6848\u3002\u3002\u53ef\u4ee5\u786e\u5b9a \u6070\u597d\u6709 k \u4e2a \u8bf4\u8c0e\u8005\u3002\u3002\u3002 ( 1 \u2264 k \u2264 n \u2264 2^8 …n \u4e3a 2 \u7684\u6574\u6b21\u5e42\u3002\u3002 Problem E. Lucky Arrays \u7ed9\u5b9a n \u4e2a\u5143\u7d20\u7684\u6570\u5217\u3002\u6bcf\u4e2a\u6570\u5b57\u53ef\u4ee5\u662f 1\u30012\u30013 \u4ee5\u53ca\u5f85\u5b9a\u4e09\u79cd\u72b6\u6001\u3002\u3002\u5f85\u5b9a\u7684\u8bdd\u53ef\u4ee5\u4efb\u53d6 1\u30012\u30013 \u4e09\u8005\u4e4b\u4e00\u3002 \u7ed9\u5b9a\u4e00\u4e2a 3*3 \u7684\u5408\u6cd5\u76f8\u90bb\u77e9\u9635 aij\u3002\u3002\u8868\u793a\u76f8\u90bb\u7684\u4f4d\u7f6e\u5982\u679c\u662f i,j \u7684\u8bdd\u662f\u5426\u5408\u6cd5\u3002\u3002\u3002 \u521d\u59cb\u6240\u6709\u4f4d\u7f6e\u90fd\u662f\u5f85\u5b9a\u3002\u3002m \u4e2a\u64cd\u4f5c\u3002\u3002\u6bcf\u4e2a\u64cd\u4f5c\u4fee\u6539\u5176\u4e2d\u4e00\u4e2a\u6570\u7684\u72b6\u6001\u3002\u3002\u7136\u540e\u8be2\u95ee\u5f53\u524d\u6709\u591a\u5c11\u5408\u6cd5\u6570\u5217\u3002\u3002\u3002 (1\u2009\u2264\u2009n,\u2009m\u2009\u2264\u200977777 ..<\/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":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[18],"tags":[],"class_list":["post-600","post","type-post","status-publish","format-standard","hentry","category-codeforces"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-9G","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/600","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=600"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/600\/revisions"}],"predecessor-version":[{"id":602,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/600\/revisions\/602"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=600"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=600"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=600"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nE..<\/a><\/p>\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 256 + 1;\r\n\r\nint a[10][N] = { { 0 }, { 2, 1 }, { 32, 30, 80, 109 }, { 6824, 59808, 147224, 415870, 1757896, 1897056, 4898872, 7593125 }, { 776830421, 290516100, 746623577, 293783147, 33900006, 735127505,\r\n\t\t565460332, 428982705, 472062098, 161873957, 117354594, 515619293, 578944191, 312106242, 569389279, 391464593 }, { 261086313, 584837659, 683961846, 468868529, 211593382, 736955478, 229471758,\r\n\t\t157617135, 398169441, 360252438, 629394768, 264125799, 647490480, 342079395, 391579767, 225200475, 486011304, 513156108, 628771752, 132906648, 142138221, 20119449, 444199674, 195188679,\r\n\t\t387329805, 44684703, 651912135, 737154512, 612549793, 519860281, 186175544, 212568440 }, { 240805271, 239509872, 581127897, 6511239, 156126222, 509425833, 672407328, 366667722, 459185405,\r\n\t\t509737025, 554790222, 165216555, 703150560, 74806569, 398730015, 383350905, 506108358, 51326142, 298053147, 104256117, 391428765, 374020479, 206607807, 87664059, 275899176, 56407680,\r\n\t\t551553401, 448939463, 582889860, 129676638, 226078251, 135769095, 61292868, 578972226, 190181628, 390739055, 184587732, 446575689, 732674124, 232198470, 676760679, 352474101, 611444862,\r\n\t\t575661807, 628905585, 320813094, 522840969, 469781928, 156006018, 554473341, 239654268, 643714911, 433540170, 199307003, 496385218, 291740751, 67309914, 370826673, 202356819, 279421821,\r\n\t\t421203111, 63744786, 520987612, 550671827 }, { 482164403, 768209115, 462063756, 154906374, 36099042, 341766705, 678182556, 621882744, 478771358, 231881111, 175889805, 243630450, 168908523,\r\n\t\t671961765, 55761813, 652682670, 773939082, 517628076, 756201264, 124604900, 750976272, 498253248, 676047609, 137170026, 705610017, 495032139, 561797418, 703097347, 500815609, 95984586,\r\n\t\t739707108, 265613565, 387099846, 777331779, 594676173, 591219559, 407997044, 208947235, 93337440, 478908360, 685013007, 487033953, 671903001, 39521181, 738490312, 33785059, 465470131,\r\n\t\t310453920, 54648783, 346831137, 427694175, 474743430, 705296781, 435828036, 429824745, 663532359, 261388683, 244690731, 533997135, 596108961, 506813013, 371892402, 590145264, 104733162,\r\n\t\t143420103, 654339672, 700348950, 685038942, 578826927, 286484229, 501639192, 434962491, 299270097, 27702486, 335375775, 111746817, 565603164, 294926121, 676063665, 735862995, 710035809,\r\n\t\t437011960, 668528077, 138765186, 508213986, 615036450, 353784942, 624827616, 343900011, 241289776, 52410890, 72018835, 352406796, 415705878, 4802637, 376367145, 65589678, 333633477, 341834527,\r\n\t\t303717460, 282387700, 42951006, 254706039, 423048528, 526429710, 68131467, 669954708, 12787348, 500636381, 317959019, 479433192, 657133515, 416259390, 610216692, 340129188, 44594256,\r\n\t\t257373347, 138718678, 530767740, 292922628, 37220268, 605295159, 480722613, 458170419, 30540300, 487159055, 232966794, 149150650 }, { 412133651, 386543325, 139952108, 289303402, 102404925,\r\n\t\t317067177, 396414708, 80515854, 663739304, 317300809, 228877044, 493725043, 715317967, 490300965, 315527373, 743539734, 488329191, 553627998, 533025234, 242583957, 706116537, 614109258,\r\n\t\t645447222, 523195911, 492109128, 722623041, 111085128, 766395126, 654378921, 691964847, 496688157, 399056049, 654363234, 102052314, 191720088, 473910948, 259736526, 332840025, 388047555,\r\n\t\t665791056, 627111387, 139696515, 441456687, 443032569, 283264821, 771641703, 452641455, 511306362, 117572859, 127701891, 721298331, 176520078, 357242229, 611296308, 696994956, 405628839,\r\n\t\t429224274, 465336054, 695091546, 689828796, 574648641, 351220905, 507964023, 675326610, 517248963, 453528621, 220301928, 494463186, 681789969, 339589656, 44524053, 417125457, 339589404,\r\n\t\t747135963, 341780733, 734158215, 396817281, 21997836, 5728464, 147611205, 456248898, 714128667, 377654949, 3862068, 128418948, 589390074, 304947090, 11703825, 228266073, 127304142, 429215724,\r\n\t\t361541124, 521572968, 468358191, 341231688, 65323503, 613778508, 15985323, 291661029, 410970006, 591638112, 349541550, 89967528, 224922159, 361094166, 584206074, 640051812, 324264456,\r\n\t\t652625388, 693768537, 11740617, 309238398, 211085469, 194905872, 639416484, 110110707, 296645895, 748118511, 131177718, 511142751, 775975599, 421403409, 475528473, 434685258, 1768977,\r\n\t\t80301375, 708023862, 569195676, 56238084, 632887668, 88089750, 631539342, 396695565, 38780154, 695798271, 469819224, 439587099, 69045921, 682966116, 112310856, 64943298, 534475872, 40215357,\r\n\t\t389728458, 286368453, 736006257, 501181650, 54829908, 603489402, 338032656, 512182818, 627500097, 462674016, 3103092, 157324491, 43978329, 596818971, 259025598, 9088632, 91991781, 577291428,\r\n\t\t211245489, 429471231, 142626330, 172560633, 510907446, 444609585, 758102058, 375112647, 744786693, 276174402, 19259856, 233672418, 745389414, 225772848, 23385663, 324290610, 519804558,\r\n\t\t120337812, 402578568, 360676008, 450089262, 551043738, 337388940, 512108856, 28879011, 690040638, 106017282, 558262341, 99972432, 608226003, 612152037, 42414435, 776201013, 39580443,\r\n\t\t518796945, 494437752, 583194366, 723936555, 415359657, 309569589, 751104774, 166684527, 249229170, 353120823, 130668327, 753823584, 580966092, 561963717, 543672234, 393846327, 586278000,\r\n\t\t327398400, 278403867, 156455586, 363920382, 190245195, 290039148, 547014447, 466218648, 146037150, 585462906, 666008595, 691786683, 374707494, 622498779, 231158277, 685740951, 115612245,\r\n\t\t681825249, 545555745, 551718468, 277206615, 640171035, 757727334, 195193908, 658656684, 457760646, 225925875, 505761984, 18685233, 506832921, 112511021, 396846646, 290147622, 113924623,\r\n\t\t669986155, 336008070, 63611061, 238586775, 119956662, 616557739, 772784623, 334527774, 410403148, 51933421 } };\r\n\r\n\r\nint dp[N][N][N]; int comb[N][N];\r\nint n, k;\r\n\r\n\r\nvoid makeTable() {\r\n\r\n\tcout << "int a[10][300]={";\r\n\r\n\tFOR(i, 0, N){comb[i][0] = 1; REP_1(j, i) comb[i][j] = sum(comb[i-1][j-1], comb[i-1][j]);}\r\n\r\n\tfor (int n = 1; n <= 256; n <<= 1) {\r\n\r\n\t\tcout << "{"; \/\/cout << n << endl;\r\n\r\n\t\tRST(dp); dp[0][0][0] = 1;\r\n\r\n#define u dp[i-1][j][k]\r\n#define v dp[i][j+ii][k+(ii!= i?ii:0)]\r\n#define nn (n-j)\r\n\r\n\t\tREP_1(i, n) FOR_1(j, 0, n) FOR_1(k, 0, j) if (u){\r\n FOR_1(ii, 0, nn) INC(v, pdt(u, comb[nn][ii]));\r\n }\r\n\r\n\t\tfor (int i = 1; i <= n; ++i) {\r\n\t\t\tcout << dp[n][n][i];\r\n\t\t\tif (i + 1 <= n) cout << ",";\r\n\t\t}\r\n\t\tcout << "},";\r\n\t}\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n#endif\r\n\r\n \/\/makeTable();\r\n int n, k; RD(n, k), OT(a[lg2(n)][k-1]);\r\n}\r\n<\/pre>\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 1 << 17, NN = N * 2 + 9;\r\nint a[NN][3][3]; bool f[3][3];\r\nint n, m, p, v;\r\n\/\/ Segment Tree\r\n\r\n#define lx (x<<1)\r\n#define rx (lx|1)\r\n#define mid (l+r>>1)\r\n#define lcc lx, l, mid\r\n#define rcc rx, mid+1, r\r\n\r\nvoid Upd(int x){\r\n RST(a[x]); REP_2(i, j, 3, 3) if (f[i][j]) REP_2(s, t, 3, 3)\r\n INC(a[x][s][t], pdt(a[lx][s][i], a[rx][j][t]));\r\n}\r\n\r\nvoid Set(int x){\r\n RST(a[x]); if (v) a[x][v-1][v-1] = 1;\r\n else REP(i, 3) a[x][i][i] = 1;\r\n}\r\n\r\nint Sum(int x = 1){\r\n int res = 0; REP_2(i, j, 3, 3) INC(res, a[x][i][j]);\r\n return res;\r\n}\r\n\r\nvoid Build(int x = 1, int l = 1, int r = n){\r\n if (l == r) Set(x);\r\n else {\r\n Build(lcc), Build(rcc);\r\n Upd(x);\r\n }\r\n}\r\n\r\nvoid Modify(int x = 1, int l = 1, int r = n){\r\n if (l == r) Set(x);\r\n else {\r\n if (p <= mid) Modify(lcc); else Modify(rcc);\r\n Upd(x);\r\n }\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n#endif\r\n\r\n\tRD(n, m); REP_2(i, j, 3, 3) RD(f[i][j]); Build();\r\n\tDO(m) RD(p, v), Modify(), OT(Sum());\r\n}\r\n<\/pre>\nExternal link: <\/h3>\n","protected":false},"excerpt":{"rendered":"