递归实现指数型枚举

知识点：递归

递归实现组合型枚举

知识点：递归

递归实现排列型枚举

知识点：递归

费解的开关

知识点：递推，二进制枚举
枚举第一行上要改变的灯，然后来递推第二行、第三行…要改变的灯。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
  4. #define per(i,j,k) for(int i=int(j);i>=int(k);i--)
  5. typedef long long ll;
  6. const int N = 7;
  7. int T, n, a[N][N], b[N][N];
  8. char s[6];
  9. bool check(){
  10.     rep(i,1,5) rep(j,1,5) if(a[i][j] == 0) return false;
  11.     return true;
  12. }
  13. void run(int x, int y) {
  14.     a[x][y] ^= 1;
  15.     a[x-1][y] ^= 1;
  16.     a[x+1][y] ^= 1;
  17.     a[x][y-1] ^= 1;
  18.     a[x][y+1] ^= 1;
  19. }
  20. void solve() {
  21.     int rs = 10;
  22.     rep(s, 0, 31) {
  23.         memcpy(a, b, sizeof b);
  24.         int cnt = 0;
  25.         rep(i, 0, 4) {
  26.             if(s >> i & 1) run(1, i + 1), cnt ++;
  27.         }
  28.         rep(i, 2, 5) {
  29.             rep(j, 1, 5) {
  30.                 if(a[i-1][j] == 0) run(i, j), cnt ++;
  31.             }
  32.         }
  33.         if(check()) rs = min(rs, cnt);
  34.     }
  35.     if(rs > 6) rs = -1;
  36.     printf("%d\n", rs);
  37. }
  38. int main(){
  39.     scanf("%d", &T);
  40.     n = 5;
  41.     while(T--){
  42.         rep(i,1,5) {
  43.             scanf("%s", s + 1);
  44.             rep(j,1,5) a[i][j] = b[i][j] = s[j] - '0';
  45.         }
  46.         solve();
  47.     }
  48. }

奇怪的汉诺塔

知识点：递推
设 3 个柱子的解为 d[n], 4 个柱子的解为 f[n]。
首先考虑 3 个柱子的递推公式：0x02 递推与递归 - 图1%22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-64%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-5B%22%20x%3D%22523%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-6E%22%20x%3D%22802%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-5D%22%20x%3D%221402%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-3D%22%20x%3D%221958%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-32%22%20x%3D%223015%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2217%22%20x%3D%223737%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-64%22%20x%3D%224460%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-5B%22%20x%3D%224984%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-6E%22%20x%3D%225262%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2212%22%20x%3D%226085%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%20x%3D%227085%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-5D%22%20x%3D%227586%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2B%22%20x%3D%228087%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%20x%3D%229087%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=d%5Bn%5D%20%3D%202%2Ad%5Bn-1%5D%20%2B%201&id=TDF9s)，即构造一个中转柱的思想。
然后 4 个柱子时，由于有两个中转柱 B, C，所以考虑 i 个盘子转到第 B（方案数 f[i])，n - i - 1 个盘子转到 C（方案数d[n-i-1]），那么递推公式为 0x02 递推与递归 - 图2 。
0x02 递推与递归 - 图3

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
  4. #define per(i,j,k) for(int i=int(j);i>=int(k);i--)
  5. typedef long long ll;
  6. const int N = 15;
  7. int n;
  8. ll d[N], f[N];
  10. int main(){
  11.     n = 12;
  12.     d[1] = 1;
  13.     rep(i,2,n) d[i] = d[i-1] * 2 + 1;
  14.     f[1] = 1; f[2] = 3;
  15.     rep(i,3,n) {
  16.         f[i] = f[i-1] * 2 + 1;
  17.         rep(j, 1, i - 2) {
  18.             f[i] = min(f[i], f[j] * 2 + d[i - j]);
  19.         }
  20.     }
  21.     rep(i,1,12) {
  22.         printf("%lld\n",f[i]);
  23.     }
  24. }

另外一种做法，只需要考虑 n 个盘子，有 i 个转到 B（方案数 f[i]），其他 n-i 个转到D（方案数 d[n-1]）。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
  4. #define per(i,j,k) for(int i=int(j);i>=int(k);i--)
  5. typedef long long ll;
  6. const int N = 15;
  7. int n;
  8. ll d[N], f[N];
  10. int main(){
  11.     n = 12;
  12.     d[1] = 1;
  13.     rep(i,2,n) d[i] = d[i-1] * 2 + 1;
  14.     f[1] = 1; f[2] = 3;
  15.     rep(i,3,n) {
  16.         f[i] = f[i-1] * 2 + 1;
  17.         rep(j, 1, i - 1) {
  18.             f[i] = min(f[i], 2 * f[j] + d[i-j]);
  19.         }
  20.     }
  21.     rep(i,1,12) {
  22.         printf("%lld\n",f[i]);
  23.     }
  24. }

约数之和

知识点：递归
把 A 分解质因数，表示为 0x02 递推与递归 - 图4。
那么 0x02 递推与递归 - 图5 可以表示为 0x02 递推与递归 - 图6。
由此，0x02 递推与递归 - 图7的约数集合可以表示为 0x02 递推与递归 - 图8
根据乘法分配律， 0x02 递推与递归 - 图9的约数之和为：
0x02 递推与递归 - 图10

所以问题被化简为一个等比数列求和问题，但直接用公式求解，需要用到除法，而分母与模数 9901 之间并不一定有逆元存在，所以这种行不通。进而，可以采用分治思路求解。
设 0x02 递推与递归 - 图11%20%3D%201%20%2B%20p%20%2B%20p%20%5E%202%20%2B%20%5Ccdots%20%2B%20p%5Ec%20%3D%20%3F%3C%2Ftitle%3E%0A%3Cdefs%20aria-hidden%3D%22true%22%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-73%22%20d%3D%22M131%20289Q131%20321%20147%20354T203%20415T300%20442Q362%20442%20390%20415T419%20355Q419%20323%20402%20308T364%20292Q351%20292%20340%20300T328%20326Q328%20342%20337%20354T354%20372T367%20378Q368%20378%20368%20379Q368%20382%20361%20388T336%20399T297%20405Q249%20405%20227%20379T204%20326Q204%20301%20223%20291T278%20274T330%20259Q396%20230%20396%20163Q396%20135%20385%20107T352%2051T289%207T195%20-10Q118%20-10%2086%2019T53%2087Q53%20126%2074%20143T118%20160Q133%20160%20146%20151T160%20120Q160%2094%20142%2076T111%2058Q109%2057%20108%2057T107%2055Q108%2052%20115%2047T146%2034T201%2027Q237%2027%20263%2038T301%2066T318%2097T323%20122Q323%20150%20302%20164T254%20181T195%20196T148%20231Q131%20256%20131%20289Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-75%22%20d%3D%22M21%20287Q21%20295%2030%20318T55%20370T99%20420T158%20442Q204%20442%20227%20417T250%20358Q250%20340%20216%20246T182%20105Q182%2062%20196%2045T238%2027T291%2044T328%2078L339%2095Q341%2099%20377%20247Q407%20367%20413%20387T427%20416Q444%20431%20463%20431Q480%20431%20488%20421T496%20402L420%2084Q419%2079%20419%2068Q419%2043%20426%2035T447%2026Q469%2029%20482%2057T512%20145Q514%20153%20532%20153Q551%20153%20551%20144Q550%20139%20549%20130T540%2098T523%2055T498%2017T462%20-8Q454%20-10%20438%20-10Q372%20-10%20347%2046Q345%2045%20336%2036T318%2021T296%206T267%20-6T233%20-11Q189%20-11%20155%207Q103%2038%20103%20113Q103%20170%20138%20262T173%20379Q173%20380%20173%20381Q173%20390%20173%20393T169%20400T158%20404H154Q131%20404%20112%20385T82%20344T65%20302T57%20280Q55%20278%2041%20278H27Q21%20284%2021%20287Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-6D%22%20d%3D%22M21%20287Q22%20293%2024%20303T36%20341T56%20388T88%20425T132%20442T175%20435T205%20417T221%20395T229%20376L231%20369Q231%20367%20232%20367L243%20378Q303%20442%20384%20442Q401%20442%20415%20440T441%20433T460%20423T475%20411T485%20398T493%20385T497%20373T500%20364T502%20357L510%20367Q573%20442%20659%20442Q713%20442%20746%20415T780%20336Q780%20285%20742%20178T704%2050Q705%2036%20709%2031T724%2026Q752%2026%20776%2056T815%20138Q818%20149%20821%20151T837%20153Q857%20153%20857%20145Q857%20144%20853%20130Q845%20101%20831%2073T785%2017T716%20-10Q669%20-10%20648%2017T627%2073Q627%2092%20663%20193T700%20345Q700%20404%20656%20404H651Q565%20404%20506%20303L499%20291L466%20157Q433%2026%20428%2016Q415%20-11%20385%20-11Q372%20-11%20364%20-4T353%208T350%2018Q350%2029%20384%20161L420%20307Q423%20322%20423%20345Q423%20404%20379%20404H374Q288%20404%20229%20303L222%20291L189%20157Q156%2026%20151%2016Q138%20-11%20108%20-11Q95%20-11%2087%20-5T76%207T74%2017Q74%2030%20112%20181Q151%20335%20151%20342Q154%20357%20154%20369Q154%20405%20129%20405Q107%20405%2092%20377T69%20316T57%20280Q55%20278%2041%20278H27Q21%20284%2021%20287Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-28%22%20d%3D%22M94%20250Q94%20319%20104%20381T127%20488T164%20576T202%20643T244%20695T277%20729T302%20750H315H319Q333%20750%20333%20741Q333%20738%20316%20720T275%20667T226%20581T184%20443T167%20250T184%2058T225%20-81T274%20-167T316%20-220T333%20-241Q333%20-250%20318%20-250H315H302L274%20-226Q180%20-141%20137%20-14T94%20250Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-70%22%20d%3D%22M23%20287Q24%20290%2025%20295T30%20317T40%20348T55%20381T75%20411T101%20433T134%20442Q209%20442%20230%20378L240%20387Q302%20442%20358%20442Q423%20442%20460%20395T497%20281Q497%20173%20421%2082T249%20-10Q227%20-10%20210%20-4Q199%201%20187%2011T168%2028L161%2036Q160%2035%20139%20-51T118%20-138Q118%20-144%20126%20-145T163%20-148H188Q194%20-155%20194%20-157T191%20-175Q188%20-187%20185%20-190T172%20-194Q170%20-194%20161%20-194T127%20-193T65%20-192Q-5%20-192%20-24%20-194H-32Q-39%20-187%20-39%20-183Q-37%20-156%20-26%20-148H-6Q28%20-147%2033%20-136Q36%20-130%2094%20103T155%20350Q156%20355%20156%20364Q156%20405%20131%20405Q109%20405%2094%20377T71%20316T59%20280Q57%20278%2043%20278H29Q23%20284%2023%20287ZM178%20102Q200%2026%20252%2026Q282%2026%20310%2049T356%20107Q374%20141%20392%20215T411%20325V331Q411%20405%20350%20405Q339%20405%20328%20402T306%20393T286%20380T269%20365T254%20350T243%20336T235%20326L232%20322Q232%20321%20229%20308T218%20264T204%20212Q178%20106%20178%20102Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-2C%22%20d%3D%22M78%2035T78%2060T94%20103T137%20121Q165%20121%20187%2096T210%208Q210%20-27%20201%20-60T180%20-117T154%20-158T130%20-185T117%20-194Q113%20-194%20104%20-185T95%20-172Q95%20-168%20106%20-156T131%20-126T157%20-76T173%20-3V9L172%208Q170%207%20167%206T161%203T152%201T140%200Q113%200%2096%2017Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-63%22%20d%3D%22M34%20159Q34%20268%20120%20355T306%20442Q362%20442%20394%20418T427%20355Q427%20326%20408%20306T360%20285Q341%20285%20330%20295T319%20325T330%20359T352%20380T366%20386H367Q367%20388%20361%20392T340%20400T306%20404Q276%20404%20249%20390Q228%20381%20206%20359Q162%20315%20142%20235T121%20119Q121%2073%20147%2050Q169%2026%20205%2026H209Q321%2026%20394%20111Q403%20121%20406%20121Q410%20121%20419%20112T429%2098T420%2083T391%2055T346%2025T282%200T202%20-11Q127%20-11%2081%2037T34%20159Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-29%22%20d%3D%22M60%20749L64%20750Q69%20750%2074%20750H86L114%20726Q208%20641%20251%20514T294%20250Q294%20182%20284%20119T261%2012T224%20-76T186%20-143T145%20-194T113%20-227T90%20-246Q87%20-249%2086%20-250H74Q66%20-250%2063%20-250T58%20-247T55%20-238Q56%20-237%2066%20-225Q221%20-64%20221%20250T66%20725Q56%20737%2055%20738Q55%20746%2060%20749Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-3D%22%20d%3D%22M56%20347Q56%20360%2070%20367H707Q722%20359%20722%20347Q722%20336%20708%20328L390%20327H72Q56%20332%2056%20347ZM56%20153Q56%20168%2072%20173H708Q722%20163%20722%20153Q722%20140%20707%20133H70Q56%20140%2056%20153Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-31%22%20d%3D%22M213%20578L200%20573Q186%20568%20160%20563T102%20556H83V602H102Q149%20604%20189%20617T245%20641T273%20663Q275%20666%20285%20666Q294%20666%20302%20660V361L303%2061Q310%2054%20315%2052T339%2048T401%2046H427V0H416Q395%203%20257%203Q121%203%20100%200H88V46H114Q136%2046%20152%2046T177%2047T193%2050T201%2052T207%2057T213%2061V578Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-2B%22%20d%3D%22M56%20237T56%20250T70%20270H369V420L370%20570Q380%20583%20389%20583Q402%20583%20409%20568V270H707Q722%20262%20722%20250T707%20230H409V-68Q401%20-82%20391%20-82H389H387Q375%20-82%20369%20-68V230H70Q56%20237%2056%20250Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-32%22%20d%3D%22M109%20429Q82%20429%2066%20447T50%20491Q50%20562%20103%20614T235%20666Q326%20666%20387%20610T449%20465Q449%20422%20429%20383T381%20315T301%20241Q265%20210%20201%20149L142%2093L218%2092Q375%2092%20385%2097Q392%2099%20409%20186V189H449V186Q448%20183%20436%2095T421%203V0H50V19V31Q50%2038%2056%2046T86%2081Q115%20113%20136%20137Q145%20147%20170%20174T204%20211T233%20244T261%20278T284%20308T305%20340T320%20369T333%20401T340%20431T343%20464Q343%20527%20309%20573T212%20619Q179%20619%20154%20602T119%20569T109%20550Q109%20549%20114%20549Q132%20549%20151%20535T170%20489Q170%20464%20154%20447T109%20429Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-22EF%22%20d%3D%22M78%20250Q78%20274%2095%20292T138%20310Q162%20310%20180%20294T199%20251Q199%20226%20182%20208T139%20190T96%20207T78%20250ZM525%20250Q525%20274%20542%20292T585%20310Q609%20310%20627%20294T646%20251Q646%20226%20629%20208T586%20190T543%20207T525%20250ZM972%20250Q972%20274%20989%20292T1032%20310Q1056%20310%201074%20294T1093%20251Q1093%20226%201076%20208T1033%20190T990%20207T972%20250Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-3F%22%20d%3D%22M226%20668Q190%20668%20162%20656T124%20632L114%20621Q116%20621%20119%20620T130%20616T145%20607T157%20591T162%20567Q162%20544%20147%20529T109%20514T71%20528T55%20566Q55%20625%20100%20661T199%20704Q201%20704%20210%20704T224%20705H228Q281%20705%20320%20692T378%20656T407%20612T416%20567Q416%20503%20361%20462Q267%20395%20247%20303Q242%20279%20242%20241V224Q242%20205%20239%20202T222%20198T205%20201T202%20218V249Q204%20320%20220%20371T255%20445T292%20491T315%20537Q317%20546%20317%20574V587Q317%20604%20315%20615T304%20640T277%20661T226%20668ZM162%2061Q162%2089%20180%20105T224%20121Q247%20119%20264%20104T281%2061Q281%2031%20264%2016T222%201Q197%201%20180%2016T162%2061Z%22%3E%3C%2Fpath%3E%0A%3C%2Fdefs%3E%0A%3Cg%20stroke%3D%22currentColor%22%20fill%3D%22currentColor%22%20stroke-width%3D%220%22%20transform%3D%22matrix(1%200%200%20-1%200%200)%22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-73%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-75%22%20x%3D%22469%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-6D%22%20x%3D%221042%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-28%22%20x%3D%221920%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-70%22%20x%3D%222310%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2C%22%20x%3D%222813%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-63%22%20x%3D%223258%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-29%22%20x%3D%223692%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-3D%22%20x%3D%224359%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%20x%3D%225415%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2B%22%20x%3D%226138%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-70%22%20x%3D%227139%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2B%22%20x%3D%227864%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(8865%2C0)%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-70%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-32%22%20x%3D%22712%22%20y%3D%22583%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2B%22%20x%3D%2210045%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-22EF%22%20x%3D%2211045%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2B%22%20x%3D%2212440%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(13441%2C0)%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-70%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMATHI-63%22%20x%3D%22712%22%20y%3D%22583%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-3D%22%20x%3D%2214629%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-3F%22%20x%3D%2215407%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=sum%28p%2Cc%29%20%3D%201%20%2B%20p%20%2B%20p%20%5E%202%20%2B%20%5Ccdots%20%2B%20p%5Ec%20%3D%20%3F&id=MzaM0)
0x02 递推与递归 - 图12%20%3D%20%5Cbegin%7Bcases%7D%0A(1%20%2B%20p%5E%7Bc%2B1%20%5Cover%202%7D)%20%20sum(p%2C%20%7Bc%20-%201%20%5Cover%202%7D)%20%26amp%3B%20%5Ctext%7Bc%20%E6%98%AF%E5%A5%87%E6%95%B0%7D%20%5C%5C%0A(1%20%2B%20p%5E%7Bc%5Cover%202%7D)%20%20sum(p%2C%20%7Bc%5Cover%202%7D%20-1)%20%2B%20p%5Ec%20%26amp%3B%20%5Ctext%7Bc%E6%98%AF%E5%81%B6%E6%95%B0%7D%0A%5Cend%7Bcases%7D%3C%2Ftitle%3E%0A%3Cdefs%20aria-hidden%3D%22true%22%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-73%22%20d%3D%22M131%20289Q131%20321%20147%20354T203%20415T300%20442Q362%20442%20390%20415T419%20355Q419%20323%20402%20308T364%20292Q351%20292%20340%20300T328%20326Q328%20342%20337%20354T354%20372T367%20378Q368%20378%20368%20379Q368%20382%20361%20388T336%20399T297%20405Q249%20405%20227%20379T204%20326Q204%20301%20223%20291T278%20274T330%20259Q396%20230%20396%20163Q396%20135%20385%20107T352%2051T289%207T195%20-10Q118%20-10%2086%2019T53%2087Q53%20126%2074%20143T118%20160Q133%20160%20146%20151T160%20120Q160%2094%20142%2076T111%2058Q109%2057%20108%2057T107%2055Q108%2052%20115%2047T146%2034T201%2027Q237%2027%20263%2038T301%2066T318%2097T323%20122Q323%20150%20302%20164T254%20181T195%20196T148%20231Q131%20256%20131%20289Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-75%22%20d%3D%22M21%20287Q21%20295%2030%20318T55%20370T99%20420T158%20442Q204%20442%20227%20417T250%20358Q250%20340%20216%20246T182%20105Q182%2062%20196%2045T238%2027T291%2044T328%2078L339%2095Q341%2099%20377%20247Q407%20367%20413%20387T427%20416Q444%20431%20463%20431Q480%20431%20488%20421T496%20402L420%2084Q419%2079%20419%2068Q419%2043%20426%2035T447%2026Q469%2029%20482%2057T512%20145Q514%20153%20532%20153Q551%20153%20551%20144Q550%20139%20549%20130T540%2098T523%2055T498%2017T462%20-8Q454%20-10%20438%20-10Q372%20-10%20347%2046Q345%2045%20336%2036T318%2021T296%206T267%20-6T233%20-11Q189%20-11%20155%207Q103%2038%20103%20113Q103%20170%20138%20262T173%20379Q173%20380%20173%20381Q173%20390%20173%20393T169%20400T158%20404H154Q131%20404%20112%20385T82%20344T65%20302T57%20280Q55%20278%2041%20278H27Q21%20284%2021%20287Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-6D%22%20d%3D%22M21%20287Q22%20293%2024%20303T36%20341T56%20388T88%20425T132%20442T175%20435T205%20417T221%20395T229%20376L231%20369Q231%20367%20232%20367L243%20378Q303%20442%20384%20442Q401%20442%20415%20440T441%20433T460%20423T475%20411T485%20398T493%20385T497%20373T500%20364T502%20357L510%20367Q573%20442%20659%20442Q713%20442%20746%20415T780%20336Q780%20285%20742%20178T704%2050Q705%2036%20709%2031T724%2026Q752%2026%20776%2056T815%20138Q818%20149%20821%20151T837%20153Q857%20153%20857%20145Q857%20144%20853%20130Q845%20101%20831%2073T785%2017T716%20-10Q669%20-10%20648%2017T627%2073Q627%2092%20663%20193T700%20345Q700%20404%20656%20404H651Q565%20404%20506%20303L499%20291L466%20157Q433%2026%20428%2016Q415%20-11%20385%20-11Q372%20-11%20364%20-4T353%208T350%2018Q350%2029%20384%20161L420%20307Q423%20322%20423%20345Q423%20404%20379%20404H374Q288%20404%20229%20303L222%20291L189%20157Q156%2026%20151%2016Q138%20-11%20108%20-11Q95%20-11%2087%20-5T76%207T74%2017Q74%2030%20112%20181Q151%20335%20151%20342Q154%20357%20154%20369Q154%20405%20129%20405Q107%20405%2092%20377T69%20316T57%20280Q55%20278%2041%20278H27Q21%20284%2021%20287Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-28%22%20d%3D%22M94%20250Q94%20319%20104%20381T127%20488T164%20576T202%20643T244%20695T277%20729T302%20750H315H319Q333%20750%20333%20741Q333%20738%20316%20720T275%20667T226%20581T184%20443T167%20250T184%2058T225%20-81T274%20-167T316%20-220T333%20-241Q333%20-250%20318%20-250H315H302L274%20-226Q180%20-141%20137%20-14T94%20250Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-70%22%20d%3D%22M23%20287Q24%20290%2025%20295T30%20317T40%20348T55%20381T75%20411T101%20433T134%20442Q209%20442%20230%20378L240%20387Q302%20442%20358%20442Q423%20442%20460%20395T497%20281Q497%20173%20421%2082T249%20-10Q227%20-10%20210%20-4Q199%201%20187%2011T168%2028L161%2036Q160%2035%20139%20-51T118%20-138Q118%20-144%20126%20-145T163%20-148H188Q194%20-155%20194%20-157T191%20-175Q188%20-187%20185%20-190T172%20-194Q170%20-194%20161%20-194T127%20-193T65%20-192Q-5%20-192%20-24%20-194H-32Q-39%20-187%20-39%20-183Q-37%20-156%20-26%20-148H-6Q28%20-147%2033%20-136Q36%20-130%2094%20103T155%20350Q156%20355%20156%20364Q156%20405%20131%20405Q109%20405%2094%20377T71%20316T59%20280Q57%20278%2043%20278H29Q23%20284%2023%20287ZM178%20102Q200%2026%20252%2026Q282%2026%20310%2049T356%20107Q374%20141%20392%20215T411%20325V331Q411%20405%20350%20405Q339%20405%20328%20402T306%20393T286%20380T269%20365T254%20350T243%20336T235%20326L232%20322Q232%20321%20229%20308T218%20264T204%20212Q178%20106%20178%20102Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-2C%22%20d%3D%22M78%2035T78%2060T94%20103T137%20121Q165%20121%20187%2096T210%208Q210%20-27%20201%20-60T180%20-117T154%20-158T130%20-185T117%20-194Q113%20-194%20104%20-185T95%20-172Q95%20-168%20106%20-156T131%20-126T157%20-76T173%20-3V9L172%208Q170%207%20167%206T161%203T152%201T140%200Q113%200%2096%2017Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-63%22%20d%3D%22M34%20159Q34%20268%20120%20355T306%20442Q362%20442%20394%20418T427%20355Q427%20326%20408%20306T360%20285Q341%20285%20330%20295T319%20325T330%20359T352%20380T366%20386H367Q367%20388%20361%20392T340%20400T306%20404Q276%20404%20249%20390Q228%20381%20206%20359Q162%20315%20142%20235T121%20119Q121%2073%20147%2050Q169%2026%20205%2026H209Q321%2026%20394%20111Q403%20121%20406%20121Q410%20121%20419%20112T429%2098T420%2083T391%2055T346%2025T282%200T202%20-11Q127%20-11%2081%2037T34%20159Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-29%22%20d%3D%22M60%20749L64%20750Q69%20750%2074%20750H86L114%20726Q208%20641%20251%20514T294%20250Q294%20182%20284%20119T261%2012T224%20-76T186%20-143T145%20-194T113%20-227T90%20-246Q87%20-249%2086%20-250H74Q66%20-250%2063%20-250T58%20-247T55%20-238Q56%20-237%2066%20-225Q221%20-64%20221%20250T66%20725Q56%20737%2055%20738Q55%20746%2060%20749Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-3D%22%20d%3D%22M56%20347Q56%20360%2070%20367H707Q722%20359%20722%20347Q722%20336%20708%20328L390%20327H72Q56%20332%2056%20347ZM56%20153Q56%20168%2072%20173H708Q722%20163%20722%20153Q722%20140%20707%20133H70Q56%20140%2056%20153Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-7B%22%20d%3D%22M434%20-231Q434%20-244%20428%20-250H410Q281%20-250%20230%20-184Q225%20-177%20222%20-172T217%20-161T213%20-148T211%20-133T210%20-111T209%20-84T209%20-47T209%200Q209%2021%20209%2053Q208%20142%20204%20153Q203%20154%20203%20155Q189%20191%20153%20211T82%20231Q71%20231%2068%20234T65%20250T68%20266T82%20269Q116%20269%20152%20289T203%20345Q208%20356%20208%20377T209%20529V579Q209%20634%20215%20656T244%20698Q270%20724%20324%20740Q361%20748%20377%20749Q379%20749%20390%20749T408%20750H428Q434%20744%20434%20732Q434%20719%20431%20716Q429%20713%20415%20713Q362%20710%20332%20689T296%20647Q291%20634%20291%20499V417Q291%20370%20288%20353T271%20314Q240%20271%20184%20255L170%20250L184%20245Q202%20239%20220%20230T262%20196T290%20137Q291%20131%20291%201Q291%20-134%20296%20-147Q306%20-174%20339%20-192T415%20-213Q429%20-213%20431%20-216Q434%20-219%20434%20-231Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-31%22%20d%3D%22M213%20578L200%20573Q186%20568%20160%20563T102%20556H83V602H102Q149%20604%20189%20617T245%20641T273%20663Q275%20666%20285%20666Q294%20666%20302%20660V361L303%2061Q310%2054%20315%2052T339%2048T401%2046H427V0H416Q395%203%20257%203Q121%203%20100%200H88V46H114Q136%2046%20152%2046T177%2047T193%2050T201%2052T207%2057T213%2061V578Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-2B%22%20d%3D%22M56%20237T56%20250T70%20270H369V420L370%20570Q380%20583%20389%20583Q402%20583%20409%20568V270H707Q722%20262%20722%20250T707%20230H409V-68Q401%20-82%20391%20-82H389H387Q375%20-82%20369%20-68V230H70Q56%20237%2056%20250Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-32%22%20d%3D%22M109%20429Q82%20429%2066%20447T50%20491Q50%20562%20103%20614T235%20666Q326%20666%20387%20610T449%20465Q449%20422%20429%20383T381%20315T301%20241Q265%20210%20201%20149L142%2093L218%2092Q375%2092%20385%2097Q392%2099%20409%20186V189H449V186Q448%20183%20436%2095T421%203V0H50V19V31Q50%2038%2056%2046T86%2081Q115%20113%20136%20137Q145%20147%20170%20174T204%20211T233%20244T261%20278T284%20308T305%20340T320%20369T333%20401T340%20431T343%20464Q343%20527%20309%20573T212%20619Q179%20619%20154%20602T119%20569T109%20550Q109%20549%20114%20549Q132%20549%20151%20535T170%20489Q170%20464%20154%20447T109%20429Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-2217%22%20d%3D%22M229%20286Q216%20420%20216%20436Q216%20454%20240%20464Q241%20464%20245%20464T251%20465Q263%20464%20273%20456T283%20436Q283%20419%20277%20356T270%20286L328%20328Q384%20369%20389%20372T399%20375Q412%20375%20423%20365T435%20338Q435%20325%20425%20315Q420%20312%20357%20282T289%20250L355%20219L425%20184Q434%20175%20434%20161Q434%20146%20425%20136T401%20125Q393%20125%20383%20131T328%20171L270%20213Q283%2079%20283%2063Q283%2053%20276%2044T250%2035Q231%2035%20224%2044T216%2063Q216%2080%20222%20143T229%20213L171%20171Q115%20130%20110%20127Q106%20124%20100%20124Q87%20124%2076%20134T64%20161Q64%20166%2064%20169T67%20175T72%20181T81%20188T94%20195T113%20204T138%20215T170%20230T210%20250L74%20315Q65%20324%2065%20338Q65%20353%2074%20363T98%20374Q106%20374%20116%20368T171%20328L229%20286Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-2212%22%20d%3D%22M84%20237T84%20250T98%20270H679Q694%20262%20694%20250T679%20230H98Q84%20237%2084%20250Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-63%22%20d%3D%22M370%20305T349%20305T313%20320T297%20358Q297%20381%20312%20396Q317%20401%20317%20402T307%20404Q281%20408%20258%20408Q209%20408%20178%20376Q131%20329%20131%20219Q131%20137%20162%2090Q203%2029%20272%2029Q313%2029%20338%2055T374%20117Q376%20125%20379%20127T395%20129H409Q415%20123%20415%20120Q415%20116%20411%20104T395%2071T366%2033T318%202T249%20-11Q163%20-11%2099%2053T34%20214Q34%20318%2099%20383T250%20448T370%20421T404%20357Q404%20334%20387%20320Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJSZ4-23A7%22%20d%3D%22M712%20899L718%20893V876V865Q718%20854%20704%20846Q627%20793%20577%20710T510%20525Q510%20524%20509%20521Q505%20493%20504%20349Q504%20345%20504%20334Q504%20277%20504%20240Q504%20-2%20503%20-4Q502%20-8%20494%20-9T444%20-10Q392%20-10%20390%20-9Q387%20-8%20386%20-5Q384%205%20384%20230Q384%20262%20384%20312T383%20382Q383%20481%20392%20535T434%20656Q510%20806%20664%20892L677%20899H712Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJSZ4-23A9%22%20d%3D%22M718%20-893L712%20-899H677L666%20-893Q542%20-825%20468%20-714T385%20-476Q384%20-466%20384%20-282Q384%203%20385%205L389%209Q392%2010%20444%2010Q486%2010%20494%209T503%204Q504%202%20504%20-239V-310V-366Q504%20-470%20508%20-513T530%20-609Q546%20-657%20569%20-698T617%20-767T661%20-812T699%20-843T717%20-856T718%20-876V-893Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJSZ4-23A8%22%20d%3D%22M389%201159Q391%201160%20455%201160Q496%201160%20498%201159Q501%201158%20502%201155Q504%201145%20504%20924Q504%20691%20503%20682Q494%20549%20425%20439T243%20259L229%20250L243%20241Q349%20175%20421%2066T503%20-182Q504%20-191%20504%20-424Q504%20-600%20504%20-629T499%20-659H498Q496%20-660%20444%20-660T390%20-659Q387%20-658%20386%20-655Q384%20-645%20384%20-425V-282Q384%20-176%20377%20-116T342%2010Q325%2054%20301%2092T255%20155T214%20196T183%20222T171%20232Q170%20233%20170%20250T171%20268Q171%20269%20191%20284T240%20331T300%20407T354%20524T383%20679Q384%20691%20384%20925Q384%201152%20385%201155L389%201159Z%22%3E%3C%2Fpath%3E%0A%3C%2Fdefs%3E%0A%3Cg%20stroke%3D%22currentColor%22%20fill%3D%22currentColor%22%20stroke-width%3D%220%22%20transform%3D%22matrix(1%200%200%20-1%200%200)%22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-73%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-75%22%20x%3D%22469%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-6D%22%20x%3D%221042%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-28%22%20x%3D%221920%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-70%22%20x%3D%222310%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2C%22%20x%3D%222813%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-63%22%20x%3D%223258%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-29%22%20x%3D%223692%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-3D%22%20x%3D%224359%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(5415%2C0)%22%3E%0A%3Cg%20transform%3D%22translate(0%2C2006)%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJSZ4-23A7%22%20x%3D%220%22%20y%3D%22-900%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJSZ4-23A8%22%20x%3D%220%22%20y%3D%22-2007%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJSZ4-23A9%22%20x%3D%220%22%20y%3D%22-2614%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3Cg%20transform%3D%22translate(1056%2C0)%22%3E%0A%3Cg%20transform%3D%22translate(-11%2C0)%22%3E%0A%3Cg%20transform%3D%22translate(0%2C696)%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-28%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%20x%3D%22389%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2B%22%20x%3D%221112%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(2112%2C0)%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-70%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(503%2C508)%22%3E%0A%3Cg%20transform%3D%22translate(120%2C0)%22%3E%0A%3Crect%20stroke%3D%22none%22%20width%3D%221103%22%20height%3D%2260%22%20x%3D%220%22%20y%3D%22146%22%3E%3C%2Frect%3E%0A%3Cg%20transform%3D%22translate(60%2C418)%22%3E%0A%20%3Cuse%20transform%3D%22scale(0.574)%22%20xlink%3Ahref%3D%22%23E1-MJMATHI-63%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.574)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-2B%22%20x%3D%22433%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.574)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%20x%3D%221212%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%20%3Cuse%20transform%3D%22scale(0.574)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-32%22%20x%3D%22710%22%20y%3D%22-698%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-29%22%20x%3D%224059%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2217%22%20x%3D%224671%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-73%22%20x%3D%225393%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-75%22%20x%3D%225863%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-6D%22%20x%3D%226435%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-28%22%20x%3D%227314%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-70%22%20x%3D%227703%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2C%22%20x%3D%228207%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(8652%2C0)%22%3E%0A%3Cg%20transform%3D%22translate(120%2C0)%22%3E%0A%3Crect%20stroke%3D%22none%22%20width%3D%221330%22%20height%3D%2260%22%20x%3D%220%22%20y%3D%22220%22%3E%3C%2Frect%3E%0A%3Cg%20transform%3D%22translate(60%2C503)%22%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMATHI-63%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-2212%22%20x%3D%22433%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%20x%3D%221212%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-32%22%20x%3D%22690%22%20y%3D%22-589%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-29%22%20x%3D%2210223%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3Cg%20transform%3D%22translate(0%2C-1077)%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-28%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%20x%3D%22389%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2B%22%20x%3D%221112%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(2112%2C0)%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-70%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(503%2C508)%22%3E%0A%3Cg%20transform%3D%22translate(120%2C0)%22%3E%0A%3Crect%20stroke%3D%22none%22%20width%3D%22407%22%20height%3D%2260%22%20x%3D%220%22%20y%3D%22146%22%3E%3C%2Frect%3E%0A%20%3Cuse%20transform%3D%22scale(0.574)%22%20xlink%3Ahref%3D%22%23E1-MJMATHI-63%22%20x%3D%22138%22%20y%3D%22659%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.574)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-32%22%20x%3D%22104%22%20y%3D%22-698%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-29%22%20x%3D%223363%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2217%22%20x%3D%223975%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-73%22%20x%3D%224698%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-75%22%20x%3D%225167%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-6D%22%20x%3D%225740%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-28%22%20x%3D%226618%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-70%22%20x%3D%227008%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2C%22%20x%3D%227511%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(7956%2C0)%22%3E%0A%3Cg%20transform%3D%22translate(120%2C0)%22%3E%0A%3Crect%20stroke%3D%22none%22%20width%3D%22473%22%20height%3D%2260%22%20x%3D%220%22%20y%3D%22220%22%3E%3C%2Frect%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMATHI-63%22%20x%3D%22118%22%20y%3D%22641%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-32%22%20x%3D%2284%22%20y%3D%22-589%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2212%22%20x%3D%228893%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%20x%3D%229893%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-29%22%20x%3D%2210394%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2B%22%20x%3D%2211005%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(12006%2C0)%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-70%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMATHI-63%22%20x%3D%22712%22%20y%3D%22513%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3Cg%20transform%3D%22translate(13906%2C0)%22%3E%0A%3Cg%20transform%3D%22translate(0%2C696)%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-63%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(694%2C0)%22%3E%0A%3Ctext%20font-family%3D%22monospace%22%20stroke%3D%22none%22%20transform%3D%22scale(71.759)%20matrix(1%200%200%20-1%200%200)%22%3E%E6%98%AF%3C%2Ftext%3E%0A%3C%2Fg%3E%0A%3Cg%20transform%3D%22translate(1627%2C0)%22%3E%0A%3Ctext%20font-family%3D%22monospace%22%20stroke%3D%22none%22%20transform%3D%22scale(71.759)%20matrix(1%200%200%20-1%200%200)%22%3E%E5%A5%87%3C%2Ftext%3E%0A%3C%2Fg%3E%0A%3Cg%20transform%3D%22translate(2560%2C0)%22%3E%0A%3Ctext%20font-family%3D%22monospace%22%20stroke%3D%22none%22%20transform%3D%22scale(71.759)%20matrix(1%200%200%20-1%200%200)%22%3E%E6%95%B0%3C%2Ftext%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3Cg%20transform%3D%22translate(0%2C-1077)%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-63%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(444%2C0)%22%3E%0A%3Ctext%20font-family%3D%22monospace%22%20stroke%3D%22none%22%20transform%3D%22scale(71.759)%20matrix(1%200%200%20-1%200%200)%22%3E%E6%98%AF%3C%2Ftext%3E%0A%3C%2Fg%3E%0A%3Cg%20transform%3D%22translate(1377%2C0)%22%3E%0A%3Ctext%20font-family%3D%22monospace%22%20stroke%3D%22none%22%20transform%3D%22scale(71.759)%20matrix(1%200%200%20-1%200%200)%22%3E%E5%81%B6%3C%2Ftext%3E%0A%3C%2Fg%3E%0A%3Cg%20transform%3D%22translate(2310%2C0)%22%3E%0A%3Ctext%20font-family%3D%22monospace%22%20stroke%3D%22none%22%20transform%3D%22scale(71.759)%20matrix(1%200%200%20-1%200%200)%22%3E%E6%95%B0%3C%2Ftext%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=sum%28p%2Cc%29%20%3D%20%5Cbegin%7Bcases%7D%0A%281%20%2B%20p%5E%7Bc%2B1%20%5Cover%202%7D%29%20%2A%20sum%28p%2C%20%7Bc%20-%201%20%5Cover%202%7D%29%20%26%20%5Ctext%7Bc%20%E6%98%AF%E5%A5%87%E6%95%B0%7D%20%5C%5C%0A%281%20%2B%20p%5E%7Bc%5Cover%202%7D%29%20%2A%20sum%28p%2C%20%7Bc%5Cover%202%7D%20-1%29%20%2B%20p%5Ec%20%26%20%5Ctext%7Bc%E6%98%AF%E5%81%B6%E6%95%B0%7D%0A%5Cend%7Bcases%7D&id=dNtIT)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int mod = 9901;
  5. ll a, b, rs;
  6. ll ksm(ll a, ll b){
  7.     ll rs = 1;
  8.     for(;b;b>>=1) {
  9.         if (b & 1) rs = rs * a % mod;
  10.         a = a * a % mod;
  11.     }
  12.     return rs;
  13. }
  14. ll get(ll p, ll c) {
  15.     if(c == 0) return 1;
  16.     if(c & 1) {
  17.         return (ksm(p, (c + 1) / 2) + 1) * get(p, (c - 1) / 2) % mod;
  18.     } else {
  19.         return ((ksm(p, c / 2) + 1) * get(p, (c - 2) / 2) % mod + ksm(p, c)) % mod;
  20.     }
  21. }
  22. int main(){
  23.     scanf("%lld%lld", &a, &b);
  24.     if(a == 0) {
  25.         puts("0");
  26.         return 0;
  27.     }
  28.     rs = 1;
  29.     for(ll i = 2; i * i <= a; i ++){
  30.         if(a % i == 0) {
  31.             ll c = 0;
  32.             while(a % i == 0) {
  33.                 a /= i; c ++;
  34.             }
  35.             c *= b;
  36.             rs = rs * get(i, c) % mod;
  37.         }
  38.     }
  39.     if(a > 1) rs = rs * get(a, b) % mod;
  40.     printf("%lld\n", rs);
  41.     return 0;
  42. }

分形之城

知识点：递归
问题简化：求解 n 级城市中，编号为 m 的位置（x, y)。
n 级城市共有 0x02 递推与递归 - 图13 个房屋，而 n-1 级城市共有 0x02 递推与递归 - 图14 个城市，所以可以确定 m 在四个 n-1 级城市中的那一个。利用递归求解 n-1 级城市中 0x02 递推与递归 - 图15号房屋的位置，然后进行调整即可。
注意调整时，不仅坐标有旋转，还有翻转。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<ll,ll> pll;
  5. int T;
  6. ll n, a, b;
  7. pll get(int n, ll m) {
  8.     if(n == 0) return {1, 1};
  9.     ll len = 1ll << (n - 1), sz = 1ll << (2 * n - 2);
  10.     int z = m / sz;
  11.     pll pos = get(n - 1, m % sz);
  12.     ll x = pos.first, y = pos.second;
  13.     if(z == 0) return make_pair(y, x);
  14.     if(z == 1) return make_pair(x, y + len);
  15.     if(z == 2) return make_pair(x + len, y + len);
  16.     return make_pair(2 * len - y + 1, len - x + 1);
  17. }
  18. double getS(ll x, ll y){
  19.     return sqrt(x * x + y * y);
  20. }
  21. int main(){
  22.     scanf("%d", &T);
  23.     while(T--){
  24.         scanf("%lld%lld%lld", &n, &a, &b);
  25.         a --; b --;
  26.         pll x = get(n, a), y = get(n, b);
  27.         double rs = getS(x.first - y.first,x.second - y.second);
  28.         rs *= 10;
  29.         printf("%.0f\n", rs);
  30.     }
  31.     return 0;
  32. }