{"id":3404,"date":"2019-03-30T22:18:08","date_gmt":"2019-03-30T17:48:08","guid":{"rendered":"https:\/\/quera.ir\/blog\/?p=3404"},"modified":"2022-01-06T07:08:39","modified_gmt":"2022-01-06T07:08:39","slug":"%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c","status":"publish","type":"post","link":"https:\/\/quera.org\/blog\/%d9%be%d8%a7%d8%b3%d8%ae-%d8%b3%d9%88%d8%a7%d9%84%d8%a7%d8%aa-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%db%b2%db%b6-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85%db%8c\/","title":{"rendered":"\u067e\u0627\u0633\u062e \u0633\u0648\u0627\u0644\u0627\u062a \u0645\u0633\u0627\u0628\u0642\u0647 \u06f2\u06f6 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc"},"content":{"rendered":"\n

\u062e\u0628 \u0628\u062f\u0648\u0646 \u0645\u0642\u062f\u0645\u0647 \u0645\u06cc\u0631\u06cc\u0645 \u0633\u0631\u0627\u063a \u0633\u0648\u0627\u0644 \u0647\u0627 :<\/p>\n\n\n\n

\u0633\u0648\u0627\u0644 \u0646\u0641\u0633\u200c\u06af\u06cc\u0631:\u200c<\/a><\/p>\n\n\n\n

\u0628\u0631\u0627\u06cc \u0633\u0648\u0627\u0644 <\/span> \u0627\u0645 \u060c a_i \\times b_i <\/span> \u0628\u0627\u0631 \u0646\u0641\u0633 \u0647\u0627 \u06af\u0631\u0641\u062a\u0647 \u0645\u06cc \u0634\u0648\u062f. \u067e\u0633 \u067e\u0627\u0633\u062e \u0628\u0631\u0627\u0628\u0631 \u0627\u0633\u062a \u0628\u0627 \\sum_{i=1}^{n} a_i \\times b_i <\/span>.<\/p>\n\n\n\n\n\n\n\n

\u06a9\u062f ++C<\/a> \u0627\u0632 \u0633\u0627\u06cc\u06cc\u0646 \u0627\u0639\u0644\u0627<\/a><\/p>\n\n\n\n

\u06a9\u062f Python 3<\/a> \u0627\u0632 \u0639\u0644\u06cc \u06a9\u0627\u0648\u06cc\u0627\u0646\u06cc<\/a><\/p>\n\n\n\n

\u06a9\u062f Java<\/a> \u0627\u0632 \u0645\u0639\u0635\u0648\u0645\u0647 \u0627\u0628\u0631\u0627\u0647\u06cc\u0645\u06cc<\/a><\/p>\n\n\n\n

\u06a9\u062f Mono C#<\/a> \u0627\u0632 \u0645\u062d\u0645\u062f \u0627\u062d\u0633\u0627\u0646 \u0634\u0639\u0628\u0627\u0646\u06cc<\/a><\/p>\n\n\n\n

\u0645\u0633\u0626\u0644\u0647 \u0647\u0627\u0644\u062a:<\/a><\/p>\n\n\n\n

\u0628\u0631\u0646\u0627\u0645\u0647 \u0631\u0627 \u0634\u0628\u06cc\u0647 \u0633\u0627\u0632\u06cc \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u0648 \u062e\u0637 \u0628\u0647 \u062e\u0637 \u0622\u0646 \u0631\u0627 \u0627\u062c\u0631\u0627 \u0645\u06cc \u06a9\u0646\u06cc\u0645. \u0686\u0648\u0646 \u0648\u0631\u0648\u062f\u06cc \u0647\u0627\u06cc \u062f\u0633\u062a\u0648\u0631 goto \u062b\u0627\u0628\u062a \u0647\u0633\u062a\u0646\u062f \u0627\u06af\u0631 \u06cc\u06a9 \u062f\u0633\u062a\u0648\u0631 \u0631\u0627 \u062f\u0648 \u0628\u0627\u0631 \u0628\u0628\u06cc\u0646\u06cc\u0645 \u0647\u06cc\u0686 \u0648\u0642\u062a \u0628\u0631\u0646\u0627\u0645\u0647 \u062a\u0645\u0627\u0645 \u0646\u0645\u06cc \u0634\u0648\u062f. \u067e\u0633 \u0647\u0631 \u062e\u0637\u06cc \u06a9\u0647 \u0645\u06cc\u0628\u06cc\u0646\u06cc\u0645 \u0631\u0627 \u0645\u0627\u0631\u06a9 \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u0648 \u0627\u06af\u0631 \u0628\u0647 \u062e\u0637 \u0645\u0627\u0631\u06a9 \u0634\u062f\u0647 \u0627\u06cc \u062f\u0648\u0628\u0627\u0631\u0647 \u0631\u0633\u06cc\u062f\u06cc\u0645 \u060c -1<\/span> \u0686\u0627\u067e \u0645\u06cc \u06a9\u0646\u06cc\u0645. \u0627\u06af\u0631 \u0647\u0645 \u06a9\u0647 \u0628\u0631\u0646\u0627\u0645\u0647 \u062a\u0645\u0627\u0645 \u0634\u062f \u0645\u0642\u0627\u062f\u06cc\u0631 cout \u0631\u0627 \u062f\u0631 \u0627\u0646\u062a\u0647\u0627 \u0686\u0627\u067e \u0645\u06cc \u06a9\u0646\u06cc\u0645.<\/p>\n\n\n\n

\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc O(n) <\/span><\/p>\n\n\n\n

\u062e\u0633\u062a\u06af\u0627\u0646:<\/a><\/p>\n\n\n\n

\u0627\u0645\u06cc\u062f \u0631\u06cc\u0627\u0636\u06cc \u062a\u0639\u062f\u0627\u062f \u0627\u0639\u062f\u0627\u062f \u0645\u062a\u0641\u0627\u0648\u062a \u0628\u0631\u0627\u0628\u0631 \u0627\u0633\u062a \u0628\u0627 \u062c\u0645\u0639 \u0627\u062d\u062a\u0645\u0627\u0644 \u0627\u06cc\u0646 \u06a9\u0647 \u0639\u062f\u062f x<\/span> \u0631\u0648\u06cc \u0633\u0631\u062f\u0631 \u0634\u0627\u0632 \u0646\u0635\u0628 \u0634\u0648\u062f \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0645\u0647 x<\/span> \u0647\u0627\u06cc \u0645\u0645\u06a9\u0646. \u0627\u0632 O(n^2) <\/span> \u0645\u06cc \u062a\u0648\u0627\u0646\u06cc\u0645 x<\/span> \u0647\u0627\u06cc\u06cc \u06a9\u0647 \u0627\u062d\u062a\u0645\u0627\u0644\u0634\u0627\u0646 0<\/span> \u0646\u06cc\u0633\u062a(\u062c\u0645\u0639 \u062d\u062f\u0627\u0642\u0644 \u06cc\u06a9 \u0628\u0627\u0632\u0647 \u0647\u0633\u062a\u0646\u062f) \u0631\u0627 \u0628\u062f\u0633\u062a \u0622\u0648\u0631\u06cc\u0645. \u062d\u0627\u0644 \u0628\u0647 \u0627\u0632\u0627\u06cc \u06cc\u06a9 \u0639\u062f\u062f x<\/span> \u0645\u06cc \u062e\u0648\u0627\u0647\u06cc\u0645 \u0627\u062d\u062a\u0645\u0627\u0644 \u0627\u06cc\u0646 \u06a9\u0647 x<\/span> \u0648\u062c\u0648\u062f \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f \u0631\u0627 \u0628\u062f\u0633\u062a \u0622\u0648\u0631\u06cc\u0645. dp_a <\/span> \u0631\u0627 \u0628\u0631\u0627\u0628\u0631 \u062a\u0639\u062f\u0627\u062f \u062d\u0627\u0644\u062a \u0633\u0627\u062e\u062a\u0647 \u0646\u0634\u062f\u0646 x<\/span> \u062f\u0631 a<\/span> \u062a\u0627\u06cc \u0627\u0648\u0644 \u062f\u0646\u0628\u0627\u0644\u0647 \u062f\u0631 \u0646\u0638\u0631 \u0645\u06cc \u06af\u06cc\u0631\u06cc\u0645. dp_a = \\sum_{b=0}^{a-1} dp_b <\/span> \u0628\u0647 \u0634\u0631\u0637\u06cc \u06a9\u0647 \u062c\u0645\u0639 \u0628\u0627\u0632\u0647 (b,a]<\/span> \u0628\u0631\u0627\u0628\u0631 x<\/span> \u0646\u0628\u0627\u0634\u062f.\u067e\u0633 \u0627\u06af\u0631 \u0628\u0647 \u0627\u0632\u0627\u06cc x<\/span> \u062a\u0639\u062f\u0627\u062f \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc\u06cc \u06a9\u0647 \u062c\u0645\u0639\u0634\u0627\u0646 x<\/span> \u0627\u0633\u062a \u0631\u0627 cnt<\/span> \u0628\u0646\u0627\u0645\u06cc\u0645 \u0622\u0646\u06af\u0627\u0647 \u0645\u06cc \u062a\u0648\u0627\u0646 dp<\/span> \u0631\u0627 \u0627\u0632 O(n+cnt)<\/span> \u0645\u06cc \u062a\u0648\u0627\u0646 \u0645\u062d\u0627\u0633\u0628\u0647 \u06a9\u0631\u062f.\u0627\u062d\u062a\u0645\u0627\u0644 \u062d\u0636\u0648\u0631 x<\/span> \u0647\u0645 \u0645\u06cc \u0634\u0648\u062f - \\frac{dp_n}{2^{n-1}} <\/span> 1 . \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc O(n^3) <\/span><\/p>\n\n\n\n

\u0627\u0631\u062a\u0628\u0627\u0637\u0627\u062a \u0641\u0627\u0645\u06cc\u0644\u06cc:<\/a><\/p>\n\n\n\n

\u0627\u0628\u062a\u062f\u0627 \u062d\u0644\u06cc \u0628\u0627 O(n^2)<\/span> \u0631\u0627 \u0628\u0631\u0631\u0633\u06cc \u0645\u06cc \u06a9\u0646\u06cc\u0645.\u0628\u0627\u06cc\u062f \u06af\u0631\u0627\u0641\u06cc \u0628\u0633\u0627\u0632\u06cc\u0645 \u06a9\u0647 \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0628\u0637\u0647 \u0645\u062b\u0644 \u0639\u0645\u0648 \u0627\u06af\u0631 b<\/span> \u0639\u0645\u0648\u06cc a<\/span> \u0628\u0648\u062f \u0622\u0646\u06af\u0627\u0647 \u0627\u0632 a<\/span> \u0628\u0647 b<\/span> \u06cc\u0627\u0644\u06cc \u062c\u0647\u062a \u062f\u0627\u0631 \u0642\u0631\u0627\u0631 \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f \u06a9\u0647 \u0631\u0648\u06cc \u0622\u0646 \u0648\u0627\u0698\u0647 \u0639\u0645\u0648 \u0646\u0648\u0634\u062a\u0647 \u0634\u062f\u0647 \u0627\u0633\u062a. \u062d\u0627\u0644\u0627 \u062c\u0647\u062a \u06cc\u0627\u0644 \u0647\u0627\u06cc \u06af\u0631\u0627\u0641 \u0631\u0627 \u0628\u0631\u0639\u06a9\u0633 \u0645\u06cc \u06a9\u0646\u06cc\u0645.\u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0627\u0632 b<\/span> \u0628\u0647 a<\/span> \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f(\u0648 \u062f\u0631 \u0635\u0648\u0631\u062a\u06cc\u06a9\u0647 \u0686\u0646\u062f \u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0628\u0648\u062f \u0645\u0633\u06cc\u0631\u06cc \u06a9\u0647 \u0627\u0632 \u0644\u062d\u0627\u0638 \u0644\u063a\u062a \u0646\u0627\u0645\u0647 \u0627\u06cc \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0627\u0633\u062a \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f).\u062c\u0648\u0627\u0628 \u0645\u0633\u0626\u0644\u0647 \u0631\u0634\u062a\u0647 \u0645\u062a\u0646\u0627\u0638\u0631 \u0628\u0627 \u0627\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0627\u0633\u062a!(\u062f\u0631 \u0627\u0646\u062a\u0647\u0627 \u062a\u0648\u0636\u06cc\u062d \u0645\u06cc \u062f\u0647\u06cc\u0645 \u06a9\u0647 \u0686\u0637\u0648\u0631 \u0645\u06cc \u062a\u0648\u0627\u0646 \u06cc\u06a9 \u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0628\u0627 \u0634\u0631\u0637 \u0628\u0632\u0631\u06af\u062a\u0631\u06cc\u0646 \u0628\u0648\u062f\u0646 \u0627\u0632 \u0644\u062d\u0627\u0638 \u062a\u0631\u062a\u06cc\u0628 \u0644\u063a\u062a \u0646\u0627\u0645\u0647 \u0627\u06cc \u0631\u0627 \u06cc\u0627\u0641\u062a).<\/p>\n\n\n\n

\u062d\u0627\u0644\u0627 \u0628\u0631\u0627\u06cc \u0627\u06cc\u0646\u06a9\u0647 \u062a\u0639\u062f\u0627\u062f \u06cc\u0627\u0644 \u0647\u0627\u06cc \u06af\u0631\u0627\u0641 \u0631\u0627 \u06a9\u0645 \u06a9\u0646\u06cc\u0645 \u0627\u0632 \u0627\u06cc\u062f\u0647 \u0627\u0636\u0627\u0641\u0647 \u06a9\u0631\u062f\u0646 \u0631\u0627\u0633 \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u0645\u06cc \u06a9\u0646\u06cc\u0645. \u0628\u0647 \u0627\u06cc\u0646 \u0635\u0648\u0631\u062a \u06a9\u0647 \u0627\u06af\u0631 \u0628\u062e\u0648\u0627\u0647\u06cc\u0645 \u0645\u062c\u0645\u0648\u0639\u0647 \u0631\u0627\u0633 \u0647\u0627\u06cc A<\/span> \u0631\u0627 \u0628\u0647 \u0645\u062c\u0645\u0648\u0639\u0647 \u0631\u0627\u0633 \u0647\u0627\u06cc B<\/span> \u0648\u0635\u0644 \u06a9\u0646\u06cc\u0645 \u0648 \u0631\u0648\u06cc \u0647\u0645\u0647 \u06cc\u0627\u0644 \u0647\u0627 \u0631\u0634\u062a\u0647 s<\/span> \u0631\u0627 \u0628\u0646\u0648\u06cc\u0633\u06cc\u0645 \u0622\u0646\u06af\u0627\u0647 \u0628\u0647 \u062c\u0627\u06cc \u0627\u06cc\u0646\u06a9\u0627\u0631 \u06cc\u06a9 \u0631\u0627\u0633 \u062c\u062f\u06cc\u062f \u0627\u0636\u0627\u0641\u0647 \u06a9\u0631\u062f\u0647 \u0648 \u0647\u0645\u0647 A<\/span> \u0631\u0627 \u0628\u0647 \u0631\u0627\u0633 \u062c\u062f\u06cc\u062f \u0648 \u0631\u0627\u0633 \u062c\u062f\u06cc\u062f \u0631\u0627 \u0628\u0647 \u0647\u0645\u0647 \u200cB<\/span> \u0648\u0635\u0644 \u0645\u06cc\u06a9\u0646\u06cc\u0645 \u0648 \u0631\u0648\u06cc \u0631\u0627\u0633 \u062c\u062f\u06cc\u062f \u0631\u0634\u062a\u0647 s<\/span> \u0631\u0627 \u0645\u06cc \u0646\u0648\u06cc\u0633\u06cc\u0645(\u0627\u06cc\u0646 \u0639\u0645\u0644\u06cc\u0627\u062a f_{A,B,s}<\/span> \u0646\u0627\u0645\u06af\u0630\u0627\u0631\u06cc \u0645\u06cc \u06a9\u0646\u06cc\u0645) . \u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u062f\u0631 \u0627\u06cc\u0646 \u06af\u0631\u0627\u0641 \u062c\u062f\u06cc\u062f \u0631\u0634\u062a\u0647 \u0647\u0627 \u0631\u0648\u06cc \u0631\u0627\u0633 \u0647\u0627 \u0646\u0648\u0634\u062a\u0647 \u0645\u06cc \u0634\u0648\u0646\u062f \u0646\u0647 \u06cc\u0627\u0644 \u0647\u0627!<\/p>\n\n\n\n

\u0628\u0631\u0627\u06cc \u0633\u0627\u062e\u062a\u0646 \u0631\u0627\u0628\u0637\u0647 \u0647\u0627\u06cc \u067e\u062f\u0631 \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0645\u062b\u0644 u<\/span> \u0628\u0627\u06cc\u062f f_{A,B,pedar}<\/span> \u0631\u0627 \u0627\u062c\u0631\u0627 \u06a9\u0646\u06cc\u0645:<\/p>\n\n\nA={u}<\/span>\n\n\n\n

B={par1_u,par2_u}<\/span> <\/p>\n\n\n\n

\u0633\u0627\u062e\u062a\u0646 \u0631\u0627\u0628\u0637\u0647 \u0647\u0627\u06cc \u067e\u0633\u0631 \u0645\u0634\u0627\u0628\u0647 \u067e\u062f\u0631 \u0627\u0646\u062c\u0627\u0645 \u0645\u06cc \u0634\u0648\u062f.<\/p>\n\n\n\n

\u0628\u0631\u0627\u06cc \u0633\u0627\u062e\u062a\u0646 \u0631\u0627\u0628\u0637\u0647 \u0647\u0627\u06cc \u0628\u0631\u0627\u062f\u0631 \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0645\u062b\u0644 u<\/span> \u0628\u0627\u06cc\u062f f_{A,B,baradar}<\/span> \u0631\u0627 \u0627\u062c\u0631\u0627 \u06a9\u0646\u06cc\u0645:<\/p>\n\n\nA=B=sons_u<\/span>\n\n\n\n

\u0628\u0631\u0627\u06cc \u0633\u0627\u062e\u062a\u0646 \u0631\u0627\u0628\u0637\u0647 \u0647\u0627\u06cc \u0639\u0645\u0648 \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0645\u062b\u0644 u<\/span> \u0628\u0627\u06cc\u062f f_{A,B,amoo}<\/span> \u0631\u0627 \u0627\u062c\u0631\u0627 \u06a9\u0646\u06cc\u0645:<\/p>\n\n\nB={sons_u}<\/span>\n\n\n\n

A={sons_{sons_u}}<\/span> <\/p>\n\n\n\n

\u062a\u0639\u062f\u0627\u062f \u0631\u0627\u0633 \u0647\u0627\u06cc \u06af\u0631\u0627\u0641 O(n)<\/span> \u0627\u0633\u062a.\u0628\u0627 \u062a\u0648\u062c\u0647 \u0628\u0647 \u0627\u06cc\u0646\u06a9\u0647 \\sum_{u}^{} sons_u<\/span> \u062a\u0639\u062f\u0627\u062f \u0631\u0627\u0628\u0637\u0647 \u0647\u0627\u06cc \u067e\u062f\u0631 \u0648 \u067e\u0633\u0631\u06cc \u0631\u0627 \u0645\u06cc \u0634\u0645\u0627\u0631\u062f \u0648 \\sum_{u}^{} sons_{sons_u} <\/span> \u062a\u0639\u062f\u0627\u062f \u0631\u0627\u0628\u0637\u0647 \u0647\u0627\u06cc \u067e\u062f\u0631 \u0648 \u067e\u062f\u0631\u0628\u0632\u0631\u06af\u06cc \u0631\u0627 \u0645\u06cc \u0634\u0645\u0627\u0631\u062f \u0648 \u0647\u0631 \u06a9\u0633 \u062d\u062f\u0627\u06a9\u062b\u0631 \u06f2 \u067e\u062f\u0631 \u0648 \u06f4 \u067e\u062f\u0631 \u0628\u0632\u0631\u06af \u062f\u0627\u0631\u062f \u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u0646\u062a\u06cc\u062c\u0647 \u06af\u0631\u0641\u062a \u062a\u0639\u062f\u0627\u062f \u06cc\u0627\u0644\u200c\u0647\u0627\u06cc \u06af\u0631\u0627\u0641 \u0633\u0627\u062e\u062a\u0647 \u0634\u062f\u0647 \u0647\u0645 O(n) <\/span> \u0627\u0633\u062a.<\/p>\n\n\n\n

\u062d\u0627\u0644\u0627 \u062a\u0646\u0647\u0627 \u06a9\u0627\u0641\u06cc \u0627\u0633\u062a \u0628\u062a\u0648\u0627\u0646\u06cc\u0645 \u06cc\u06a9 \u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u062f\u0631 \u0627\u06cc\u0646 \u06af\u0631\u0627\u0641 \u067e\u06cc\u062f\u0627 \u06a9\u0646\u06cc\u0645 (\u200c\u0686\u0648\u0646 \u0647\u0631 \u0631\u0627\u0628\u0637\u0647 \u0627\u0632 \u0637\u06cc \u06a9\u0631\u062f\u0646 \u062f\u0648 \u06cc\u0627\u0644 \u0634\u06a9\u0644 \u0645\u06cc \u06af\u06cc\u0631\u062f \u0637\u0648\u0644 \u0627\u06cc\u0646 \u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u06f2 \u0628\u0631\u0627\u0628\u0631 \u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0631\u0627\u0628\u0637\u0647 \u0627\u0633\u062a) \u06a9\u0647 \u0631\u0634\u062a\u0647 \u0645\u062a\u0646\u0627\u0638\u0631 \u0622\u0646 (\u06a9\u0647 \u0631\u0648\u06cc \u0631\u0627\u0633 \u0647\u0627 \u0631\u0634\u062a\u0647 \u0646\u0648\u0634\u062a\u06cc\u0645 \u0648 \u0631\u0634\u062a\u0647 \u0645\u062a\u0646\u0627\u0638\u0631 \u0628\u0647 \u0631\u0627\u0633 \u0647\u0627\u06cc \u0627\u0635\u0644\u06cc \u067e\u0648\u0686 \u0627\u0633\u062a) \u0627\u0632 \u0644\u062d\u0627\u0638 \u062a\u0631\u062a\u06cc\u0628 \u0644\u063a\u062a \u0646\u0627\u0645\u0647 \u0627\u06cc \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0628\u0627\u0634\u062f! \u0647\u0645\u0686\u0646\u06cc\u0646 \u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u06cc\u0627\u0644 \u0647\u0627 \u0628\u0631\u0639\u06a9\u0633 \u0634\u062f\u0647 \u0627\u0646\u062f \u0648 \u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0627\u0632 b<\/span> \u0631\u0627 \u0645\u06cc \u062e\u0648\u0627\u0647\u06cc\u0645.<\/p>\n\n\n\n

\u0627\u06cc\u0646 \u06a9\u0627\u0631 \u0631\u0627 \u0628\u0627 \u06a9\u0645\u06a9 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 bfs<\/span> \u0628\u0627 \u06a9\u0645\u06cc \u062a\u063a\u06cc\u06cc\u0631 \u0627\u0646\u062c\u0627\u0645 \u0645\u06cc\u200c\u062f\u0647\u06cc\u0645. \u0628\u062f\u0648\u0646 \u062a\u0648\u062c\u0647 \u0628\u0647 \u0631\u0634\u062a\u0647 \u0631\u0648\u06cc \u0631\u0627\u0633 \u0647\u0627 bfs<\/span> \u0631\u0627 \u0628\u0627 \u0634\u0631\u0648\u0639 \u0627\u0632 \u0631\u0627\u0633 b<\/span> \u0627\u062c\u0631\u0627 \u0645\u06cc \u06a9\u0646\u06cc\u0645.\u062d\u0627\u0644\u0627 \u06af\u0631\u0627\u0641 \u0645\u0627 \u0644\u0627\u06cc\u0647 \u0628\u0646\u062f\u06cc \u0634\u062f\u0647 \u0627\u0633\u062a.\u062a\u0646\u0647\u0627 \u06cc\u0627\u0644 \u0647\u0627\u06cc\u06cc \u06a9\u0647 \u0628\u06cc\u0646 \u0644\u0627\u06cc\u0647 \u0647\u0627\u06cc \u0645\u062a\u0648\u0627\u0644\u06cc \u0647\u0633\u062a\u0646\u062f \u0631\u0627 \u0646\u06af\u0647 \u062f\u0627\u0631\u06cc\u062f \u0648 \u0628\u0642\u06cc\u0647 \u0631\u0627 \u062f\u0648\u0631 \u0628\u0631\u06cc\u0632\u06cc\u062f \u0632\u06cc\u0631\u0627 \u0628\u0631\u0627\u06cc \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u062f\u0646 \u06a9\u0648\u062a\u0627\u0647 \u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0644\u0627\u0632\u0645 \u0648 \u06a9\u0627\u0641\u06cc \u0627\u0633\u062a \u06a9\u0647 \u062a\u0646\u0647\u0627 \u0627\u0632 \u0627\u06cc\u0646 \u06cc\u0627\u0644 \u0647\u0627 \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u06a9\u0646\u06cc\u0645.\u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0645\u062b\u0644 u<\/span> \u0631\u0634\u062a\u0647 \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645\u06cc \u06a9\u0647 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0627 \u0637\u06cc \u06a9\u0631\u062f\u0646 \u0645\u0633\u06cc\u0631\u06cc \u0627\u0632 \u0631\u06cc\u0634\u0647 \u0628\u0647 \u0622\u0646 \u0631\u0627\u0633 \u0633\u0627\u062e\u062a \u0631\u0627 S_u<\/span> \u0628\u0646\u0627\u0645\u06cc\u062f.\u0647\u062f\u0641 \u0627\u06cc\u0646 \u0646\u06cc\u0633\u062a \u06a9\u0647 S_u<\/span> \u0647\u0627 \u0631\u0627 \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u06cc\u0645 \u0628\u0644\u06a9\u0647 \u0627\u06cc\u0646 \u0627\u0633\u062a \u06a9\u0647 \u0628\u0641\u0647\u0645\u06cc\u0645 \u0628\u0631\u0627\u06cc \u0633\u0627\u062e\u062a\u0646 S_u<\/span> \u0631\u0627\u0633 \u0642\u0628\u0644 \u0627\u0632 u<\/span> \u062f\u0631 \u0645\u0633\u06cc\u0631 \u06a9\u0647 \u0628\u0648\u062f\u0647 \u0627\u0633\u062a.( \u06a9\u0647 \u062f\u0631 \u0644\u0627\u06cc\u0647 \u0642\u0628\u0644\u06cc \u0627\u0633\u062a) \u0632\u06cc\u0631\u0627 \u0627\u06af\u0631 \u0627\u06cc\u0646 \u0631\u0627 \u0628\u0641\u0647\u0645\u06cc\u0645 \u0645\u06cc \u062a\u0648\u0627\u0646\u06cc\u0645 \u0645\u0633\u06cc\u0631 \u0645\u0648\u0631\u062f \u0646\u0638\u0631 \u0631\u0627 \u0628\u0633\u0627\u0632\u06cc\u0645.<\/p>\n\n\n\n

\u0628\u0631\u0627\u06cc \u0627\u06cc\u0646 \u06a9\u0627\u0631 \u062a\u0646\u0647\u0627 \u0644\u0627\u0632\u0645 \u0627\u0633\u062a \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0645\u062b\u0644 u<\/span> \u0639\u062f\u062f\u06cc \u0645\u062b\u0644 rank<\/span> \u0645\u062d\u0627\u0633\u0628\u0647 \u06a9\u0646\u06cc\u0645 \u06a9\u0647 \u0646\u0634\u0627\u0646 \u0645\u06cc \u062f\u0647\u062f \u0627\u06af\u0631 \u0644\u0627\u06cc\u0647 \u0645\u0631\u0628\u0648\u0637 \u0628\u0647 u<\/span> \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u0645 \u0631\u0634\u062a\u0647 S_u<\/span> \u0627\u0632 \u0644\u062d\u0627\u0638 \u0628\u0632\u0631\u06af\u06cc \u0686\u0646\u062f\u0645\u06cc\u0646 \u0631\u0634\u062a\u0647 \u062f\u0631 \u0627\u06cc\u0646 \u0644\u0627\u06cc\u0647 \u0627\u0633\u062a.(\u200c\u0648 \u0627\u06af\u0631 S_i=S_j<\/span> \u0628\u0648\u062f \u0622\u0646\u06af\u0627\u0647 rank_i=rank_j<\/span>). \u062d\u0627\u0644\u0627 \u0627\u06af\u0631 rank<\/span> \u0631\u0627\u0633 \u0647\u0627\u06cc \u0644\u0627\u06cc\u0647 \u0642\u0628\u0644\u06cc \u0631\u0627 \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u06cc\u0645 \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0645\u062b\u0644 u<\/span> \u062f\u0631 \u0644\u0627\u06cc\u0647 \u0641\u0639\u0644\u06cc \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u062f \u06a9\u0647 \u0631\u0627\u0633 \u0642\u0628\u0644 \u0627\u0632 \u0622\u0646 \u0628\u0627\u06cc\u062f \u0686\u0647 \u06a9\u0633\u06cc \u0628\u0627\u0634\u062f.( \u06cc\u06a9\u06cc \u0631\u0627\u0633\u06cc \u06a9\u0647 rank<\/span> \u0622\u0646 \u0628\u06cc\u0634\u06cc\u0646\u0647 \u0627\u0633\u062a).\u067e\u0633 \u062a\u0646\u0647\u0627 \u06a9\u0627\u0641\u06cc \u0627\u0633\u062a \u0628\u062a\u0648\u0627\u0646\u06cc\u0645 \u0628\u0627 \u062f\u0627\u0634\u062a\u0646 rank<\/span> \u0647\u0627\u06cc \u0644\u0627\u06cc\u0647 \u0642\u0628\u0644\u06cc rank<\/span> \u0647\u0627\u06cc \u0644\u0627\u06cc\u0647 \u062c\u062f\u06cc\u062f \u0631\u0627 \u0628\u0633\u0627\u0632\u06cc\u0645!\u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0631\u0627\u0633 \u0645\u062b\u0644 u<\/span> \u062f\u0631 \u0644\u0627\u06cc\u0647 \u0641\u0639\u0644\u06cc \u0628\u06cc\u0646 \u062a\u0645\u0627\u0645 \u0631\u0627\u0633 \u0647\u0627\u06cc\u06cc \u0644\u0627\u06cc\u0647 \u0642\u0628\u0644\u06cc \u06a9\u0647 \u0628\u0647 u<\/span> \u06cc\u0627\u0644 \u062f\u0627\u0631\u0646\u062f \u0631\u0627\u0633\u06cc \u0645\u062b\u0644 y<\/span> \u0631\u0627 \u0628\u06cc\u0627\u0628\u06cc\u062f \u06a9\u0647 rank_y<\/span> \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0628\u0627\u0634\u062f.\u062d\u0627\u0644\u0627 \u0628\u0647 \u0627\u0632\u0627\u06cc \u062a\u0645\u0627\u0645 \u0631\u0627\u0633 \u0647\u0627\u06cc \u0644\u0627\u06cc\u0647 \u062c\u062f\u06cc\u062f \u0645\u062b\u0644 u<\/span> \u0642\u0631\u0627\u0631 \u062f\u0647\u06cc\u062f:<\/p>\n\n\nval_u = pair<rank_y,string_u><\/span>\n\n\n\n

\u0627\u06af\u0631 val<\/span> \u0645\u0631\u0628\u0648\u0637 \u0628\u0647 \u062a\u0645\u0627\u0645 \u0631\u0627\u0633 \u0647\u0627\u06cc \u0644\u0627\u06cc\u0647 \u062c\u062f\u06cc\u062f \u0631\u0627 \u0645\u0631\u062a\u0628 \u06a9\u0646\u06cc\u062f \u0645\u06cc \u062a\u0648\u0627\u0646 \u0627\u0632 \u0631\u0648\u06cc \u0622\u0646 rank<\/span> \u0647\u0627\u06cc \u0644\u0627\u06cc\u0647 \u062c\u062f\u06cc\u062f \u0631\u0627 \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u062f. \u067e\u0633 \u0631\u0627\u0647 \u062d\u0644 \u0645\u0627 O(n*log(n))<\/span> \u0645\u06cc \u0628\u0627\u0634\u062f.\u0642\u0627\u0628\u0644 \u0630\u06a9\u0631 \u0627\u0633\u062a \u06a9\u0647 \u0628\u0647 \u0631\u0627\u062d\u062a\u06cc \u0645\u06cc \u062a\u0648\u0627\u0646 \u062d\u0644 \u0628\u0627\u0644\u0627 \u0631\u0627 O(n)<\/span> \u06a9\u0631\u062f<\/p>\n\n\n\n

\u0631\u0645\u0632 \u062c\u0627\u06cc\u06af\u0634\u062a<\/a><\/p>\n\n\n\n


\u0627\u0628\u062a\u062f\u0627 \u0635\u0648\u0631\u062a \u0633\u0648\u0627\u0644 \u0631\u0627 \u062f\u0642\u06cc\u0642 \u062a\u0631 \u0628\u06cc\u0627\u0646 \u0645\u06cc \u06a9\u0646\u06cc\u0645.\u06cc\u06a9 \u062c\u0627\u06cc\u06af\u0634\u062a n <\/span> \u062a\u0627\u06cc\u06cc \u062f\u0627\u0631\u06cc\u0645. m <\/span> \u062a\u0627 \u062c\u0627\u06cc\u06af\u0634\u062a \u062f\u06cc\u06af\u0631 \u0647\u0645 \u062f\u0627\u0631\u06cc\u0645 \u06a9\u0647 \u0645\u062c\u0645\u0648\u0639 \u0627\u0646\u062f\u0627\u0632\u0647 \u0647\u0627\u06cc \u0622\u0646\u0647\u0627 \u0631\u0627 \u0628\u0627 \\sigma <\/span> ( \u0628\u062e\u0648\u0627\u0646\u06cc\u062f \u0633\u06cc\u06af\u0645\u0627) \u0646\u0634\u0627\u0646 \u0645\u06cc \u062f\u0647\u06cc\u0645.\u06cc\u0647 \u06cc\u06a9 \u0628\u0627\u0632\u0647 \u0627\u0632 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0635\u0644\u06cc \u062e\u0648\u0628 \u0645\u06cc \u06af\u0648\u06cc\u06cc\u0645 \u0627\u06af\u0631 \u0641\u0634\u0631\u062f\u0647 \u0634\u062f\u0647 \u0627\u0639\u062f\u0627\u062f \u0622\u0646 \u0628\u0631\u0627\u0628\u0631 \u0628\u0627 \u06cc\u06a9\u06cc \u0627\u0632 m <\/span> \u062c\u0627\u06cc\u06af\u0634\u062a \u0628\u0627\u0634\u062f.\u062d\u0627\u0644\u0627 \u0645\u0627 \u0628\u0627\u06cc\u062f \u062a\u0639\u062f\u0627\u062f \u0631\u0627\u0647 \u0647\u0627\u06cc \u0627\u0641\u0631\u0627\u0632 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0635\u0644\u06cc \u0628\u0647 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628 \u0631\u0627 \u0628\u06af\u0648\u06cc\u06cc\u0645.
\u0627\u062f\u0639\u0627 \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u062a\u0639\u062f\u0627\u062f \u0637\u0648\u0644 \u0647\u0627\u06cc \u0645\u062e\u062a\u0644\u0641 \u062f\u0631 m<\/span> \u062c\u0627\u06cc\u06af\u0634\u062a\u0645\u0627\u0646 \u0627\u0632 O(\\sqrt{\\sigma})<\/span> \u0627\u0633\u062a.\u06a9\u0647 \u062f\u0631 \u0627\u06cc\u0646\u0635\u0648\u0631\u062a \u0645\u06cc \u062a\u0648\u0627\u0646 \u0646\u062a\u06cc\u062c\u0647 \u06af\u0631\u0641\u062a \u062a\u0639\u062f\u0627\u062f \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628 \u0627\u0632 O(n \\sqrt{\\sigma}) <\/span> \u0627\u0633\u062a.\u062d\u0627\u0644\u0627 \u0627\u06af\u0631 \u0628\u062a\u0648\u0627\u0646\u06cc\u0645 \u062a\u0645\u0627\u0645 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628 \u0631\u0627 \u0634\u0646\u0627\u0633\u0627\u06cc\u06cc \u06a9\u0646\u06cc\u0645 \u0645\u06cc \u062a\u0648\u0627\u0646\u06cc\u0645 \u0628\u0647 \u0631\u0627\u062d\u062a\u06cc \u062c\u0648\u0627\u0628 \u0631\u0627 \u0628\u0647 \u062f\u0633\u062a \u0628\u06cc\u0627\u0631\u06cc\u0645.(\u06a9\u0627\u0641\u06cc\u0633\u062a <\/em> dp_i <\/span> \u0631\u0627 \u062a\u0639\u062f\u0627\u062f \u0627\u0641\u0631\u0627\u0632 i \u0639\u0636\u0648 \u0627\u0648\u0644 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0635\u0644\u06cc \u0628\u0647 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628 \u062a\u0639\u0631\u06cc\u0641 \u06a9\u0646\u06cc\u0645 \u0648 \u062c\u0648\u0627\u0628 <\/em> dp_n <\/span> \u0627\u0633\u062a\u200c). \u0628\u0631\u0627\u06cc \u0634\u0646\u0627\u0633\u0627\u06cc\u06cc \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628 \u062f\u0648 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0645\u06cc \u062f\u0647\u06cc\u0645. \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0627\u0648\u0644 \u0627\u0632 <\/em> O(n\\ MaxLen\\ lg(n))<\/span> \u06a9\u0627\u0631 \u0645\u06cc \u06a9\u0646\u062f(MaxLen<\/span> \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0637\u0648\u0644 \u062f\u0631 \u0622\u0646 m<\/span> \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0633\u062a) \u0648 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u062f\u0648\u0645 \u0627\u0632 O((\\sigma+(nm))\\times lg(n)) <\/span>\u06a9\u0627\u0631 \u0645\u06cc \u06a9\u0646\u062f.\u0633\u067e\u0633 \u0628\u0627 \u062a\u0631\u06a9\u06cc\u0628 \u0627\u06cc\u0646 \u062f\u0648 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0645\u0633\u0627\u0644\u0647 \u0627\u0632 O(n \\sqrt{\\sigma} lg(n) ) <\/span> \u062d\u0644 \u0645\u06cc \u0634\u0648\u062f.(\u06a9\u0627\u0641\u06cc\u0633\u062a \u0622\u0646 m<\/span> \u062c\u0627\u06cc\u06af\u0634\u062a \u0631\u0627 \u0628\u0647 \u062f\u0648 \u062f\u0633\u062a\u0647 \u0628\u0627 \u0637\u0648\u0644 \u06a9\u0645\u062a\u0631 \u0627\u0632 \\sqrt{\\sigma} <\/span>\u0648 \u0628\u06cc\u0634\u062a\u0631 \u0627\u0632 \u0622\u0646 \u062a\u0642\u0633\u06cc\u0645 \u06a9\u0646\u06cc\u062f \u0648 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628\u06cc \u06a9\u0647 \u0647\u0631 \u062f\u0633\u062a\u0647 \u0645\u06cc \u0633\u0627\u0632\u062f \u0631\u0627 \u0645\u062d\u0627\u0633\u0628\u0647 \u06a9\u0646\u06cc\u0645).<\/p>\n\n\n\n

\u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0627\u0648\u0644:<\/p>\n\n\n\n

\u0642\u0628\u0644 \u0627\u0632 \u0634\u0631\u0648\u0639 \u0628\u0647 \u0627\u06cc\u0646 \u062a\u0628\u062f\u06cc\u0644 \u062c\u0627\u06cc\u06af\u0634\u062a\u06cc \u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f:
\u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f \u062c\u0627\u06cc\u06af\u0634\u062a k<\/span> \u0639\u0636\u0648\u06cc p<\/span> \u0631\u0627 \u062f\u0627\u0631\u06cc\u0645 \u0648 \u0627\u06cc\u0646 \u062a\u0628\u062f\u06cc\u0644 \u0628\u0647 \u0645\u0627 \u0622\u0631\u0627\u06cc\u0647 k<\/span> \u062a\u0627\u06cc\u06cc a<\/span> \u0631\u0627 \u0645\u06cc\u062f\u0647\u062f \u06a9\u0647 :<\/p>\n\n\n\n

a_i<\/span> \u062a\u0639\u062f\u0627\u062f \u0627\u0646\u062f\u06cc\u0633 \u0647\u0627\u06cc j \\leq\\ i<\/span> \u06a9\u0647 a_j \\leq\\ a_i <\/span>
\u0628\u0647 \u0627\u06cc\u0646 \u0641\u0631\u0645 \u0627\u0632 \u0646\u0645\u0627\u06cc\u0634 \u062c\u0627\u06cc\u06af\u0634\u062a \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u0645\u06cc \u06af\u0648\u06cc\u06cc\u0645.\u0645\u06cc \u062a\u0648\u0627\u0646 \u062b\u0627\u0628\u062a \u06a9\u0631\u062f \u0628\u06cc\u0646 \u062c\u0627\u06cc\u06af\u0634\u062a \u0647\u0627\u06cc k<\/span> \u062a\u0627\u06cc\u06cc p<\/span> \u0628\u0647 \u0622\u0631\u0627\u06cc\u0647 \u0647\u0627\u06cc k<\/span> \u062a\u0627\u06cc\u06cc a<\/span> \u06a9\u0647 ( 1 \\leq\\ a_i \\leq\\ i <\/span>) \u062a\u0646\u0627\u0638\u0631 \u06cc\u06a9 \u0628\u0647 \u06cc\u06a9 \u0628\u0631\u0642\u0631\u0627\u0631 \u0627\u0633\u062a \u067e\u0633 \u0647\u0631 \u062c\u0627\u06cc\u06af\u0634\u062a \u06cc\u06a9 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u062f\u0627\u0631\u062f \u0648 \u0647\u0631 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u0645\u0639\u0627\u062f\u0644 \u06cc\u06a9 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0633\u062a!<\/p>\n\n\n\n

\u062d\u0627\u0644\u0627 \u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0647\u0631 \u0622\u0631\u0627\u06cc\u0647 \u0628\u0627 \u0627\u0639\u062f\u0627\u062f \u0645\u062a\u0645\u0627\u06cc\u0632 \u0647\u0645 \u06cc\u06a9 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u062f\u0627\u0631\u062f.(\u062f\u0642\u06cc\u0642\u0627 \u0645\u0634\u0627\u0628\u0647 \u0628\u0627\u0644\u0627 \u062a\u0639\u0631\u06cc\u0641 \u0645\u06cc \u0634\u0648\u062f).
\u062d\u0627\u0644\u0627 \u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0641\u0634\u0631\u062f\u0647 \u0622\u0631\u0627\u06cc\u0647 a<\/span> \u0628\u0631\u0627\u0628\u0631 \u0628\u0627 \u062c\u0627\u06cc\u06af\u0634\u062a p<\/span> \u0645\u06cc \u0634\u0648\u062f \u0627\u06af\u0631 \u0648 \u0641\u0642\u0637 \u0627\u06af\u0631 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u0622\u0646 \u062f\u0648 \u0628\u0631\u0627\u0628\u0631 \u0628\u0627\u0634\u062f.
\u062d\u0627\u0644\u0627 \u06a9\u0644 m<\/span> \u062c\u0627\u06cc\u06af\u0634\u062a \u0631\u0627 \u0628\u0647 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u062f\u0631 \u0628\u06cc\u0627\u0648\u0631\u06cc\u062f(\u0627\u06cc\u0646 \u06a9\u0627\u0631 \u0627\u0632 O(\\sigma lg(n)) <\/span> \u0628\u0627 \u062f\u0627\u062f\u0647 \u0633\u0627\u062e\u062a\u0627\u0631\u06cc \u0645\u062b\u0644 \u062f\u0631\u062e\u062a \u0641\u0646\u0648\u06cc\u06a9 \u0645\u0645\u06a9\u0646 \u0627\u0633\u062a).\u0633\u067e\u0633 \u0622\u0646\u0647\u0627 \u0631\u0627 \u062f\u0631 \u062a\u0631\u0627\u06cc \u0628\u0631\u06cc\u0632\u06cc\u062f.\u062d\u0627\u0644\u0627 \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0646\u0642\u0637\u0647 \u0634\u0631\u0648\u0639 \u0627\u0632 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0635\u0644\u06cc \u0645\u06cc \u062e\u0648\u0627\u0647\u06cc\u0645 \u0686\u06a9 \u06a9\u0646\u06cc\u0645 \u06a9\u0647 \u0647\u0631 \u06a9\u062f\u0627\u0645 \u0627\u0632 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc [i,i+MaxLen) <\/span> \u062e\u0648\u0628 \u0647\u0633\u062a\u0646\u062f \u06cc\u0627 \u0646\u0647.\u0628\u0631\u0627\u06cc \u0627\u06cc\u0646\u06a9\u0627\u0631 \u0627\u0632 i<\/span> \u0634\u0631\u0648\u0639 \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u0648 \u067e\u06cc\u0645\u0627\u06cc\u0634 \u0631\u0627 \u0634\u0631\u0648\u0639 \u0645\u06cc \u06a9\u0646\u06cc\u0645.\u0641\u0631\u0636 \u0645\u0631\u062d\u0644\u0647 \u0642\u0628\u0644 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u0628\u0627\u0632\u0647 [i,i+k) <\/span> \u0631\u0627 \u0633\u0627\u062e\u062a\u0647 \u0627\u06cc\u0645 \u0648 \u0645\u06a9\u0627\u0646 \u0622\u0646 \u0631\u0634\u062a\u0647 \u0631\u0627 \u062f\u0631 \u062a\u0631\u0627\u06cc \u067e\u06cc\u062f\u0627 \u06a9\u0631\u062f\u0647 \u0627\u06cc\u0645.\u062f\u0631 \u0627\u06cc\u0646 \u0645\u0631\u062d\u0644\u0647 \u0628\u0627\u06cc\u062f \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u0631\u0627 \u06af\u0633\u062a\u0631\u0634 \u062f\u0647\u06cc\u0645 \u0648 \u0622\u0646\u0631\u0627 \u0628\u0631\u0627\u06cc \u0628\u0627\u0632\u0647 [i,i+k+1) <\/span> \u0628\u0633\u0627\u0632\u06cc\u0645(\u0627\u0632 \u0648\u06cc\u0698\u06af\u06cc \u0647\u0627\u06cc \u062e\u0648\u0628 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u0627\u06cc\u0646 \u0627\u0633\u062a \u06a9\u0647 \u0627\u06af\u0631 \u0628\u062e\u0648\u0627\u0647\u06cc\u0645 \u0628\u0647 \u062a\u0647 \u0622\u0631\u0627\u06cc\u0647 k<\/span> \u0639\u0636\u0648\u06cc \u0639\u062f\u062f \u0627\u0636\u0627\u0641\u0647 \u06a9\u0646\u06cc\u0645 \u062f\u06cc\u06af\u0631 k<\/span> \u0639\u0636\u0648 \u0627\u0648\u0644 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u062a\u063a\u06cc\u06cc\u0631\u06cc \u0646\u0645\u06cc \u06a9\u0646\u0646\u062f). \u0648 \u0645\u06a9\u0627\u0646 \u0631\u0634\u062a\u0647 \u062c\u062f\u06cc\u062f \u0631\u0627 \u062f\u0631 \u062a\u0631\u0627\u06cc \u067e\u06cc\u062f\u0627 \u06a9\u0646\u06cc\u0645(\u06a9\u0627\u0641\u06cc\u0633\u062a \u0627\u0632 \u0645\u06a9\u0627\u0646 \u0642\u0628\u0644\u06cc \u06cc\u0627\u0644\u06cc \u0631\u0627 \u0637\u06cc \u06a9\u0646\u06cc\u0645 \u06a9\u0647 \u0639\u062f\u062f \u0631\u0648\u06cc \u0622\u0646 \u0647\u0645\u0627\u0646 \u0639\u062f\u062f\u06cc \u0627\u0633\u062a \u06a9\u0647 \u0628\u0647 \u062a\u0647 \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628 \u0627\u0636\u0627\u0641\u0647 \u06a9\u0631\u062f\u06cc\u0645).
\u0627\u06af\u0631 \u0631\u0648\u06cc \u0631\u0627\u0633 \u0647\u0627\u06cc \u0645\u0631\u0628\u0648\u0637 \u0628\u0647 m<\/span> \u0641\u0631\u0645 \u0639\u062c\u06cc\u0628(\u0628\u0647 \u0635\u0648\u0631\u062a \u06a9\u0627\u0645\u0644 \u0646\u0647 \u06cc\u06a9 \u067e\u0631\u06cc\u0641\u06cc\u06a9\u0633 \u0627\u0632 \u0622\u0646\u0647\u0627)\u0639\u0644\u0627\u0645\u062a \u0628\u06af\u0630\u0627\u0631\u06cc\u0645 \u0645\u06cc \u062a\u0648\u0627\u0646\u06cc\u0645 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628 \u0628\u0627 \u0634\u0631\u0648\u0639 \u0627\u0632 i<\/span> \u0631\u0627 \u062a\u0634\u062e\u06cc\u0635 \u062f\u0647\u06cc\u0645(\u0647\u0631 \u0648\u0642\u062a \u0628\u0647 \u06cc\u06a9 \u0631\u0627\u0633 \u0639\u0644\u0627\u0645\u062a \u062f\u0627\u0631 \u0631\u0633\u06cc\u062f\u06cc\u0645 \u06cc\u0639\u0646\u06cc \u0628\u0627\u0632\u0647 \u0645\u0627\u0646 \u062e\u0648\u0628 \u0627\u0633\u062a).
\u0627\u0632 \u0622\u0646\u062c\u0627\u06cc\u06cc \u06a9\u0647 \u0627\u0632 \u0647\u0631 \u0646\u0642\u0637\u0647 \u0634\u0631\u0648\u0639 \u06a9\u0627\u0641\u06cc\u0633\u062a MaxLen<\/span> \u062a\u0627 \u062c\u0644\u0648 \u0628\u0631\u0648\u06cc\u0645 \u0648 \u0647\u0631 \u0645\u0631\u062d\u0644\u0647 \u062c\u0644\u0648 \u0631\u0641\u062a\u0646 \u0628\u0647 \u0627\u0646\u062f\u0627\u0632\u0647 O(lg(n)) <\/span>\u0628\u0631\u0627\u06cc\u0645\u0627\u0646 \u0647\u0632\u06cc\u0646\u0647 \u062f\u0627\u0631\u062f(\u06a9\u0627\u0631 \u06a9\u0631\u062f\u0646 \u0628\u0627 \u0641\u0646\u0648\u06cc\u06a9) \u067e\u0633 \u0628\u0627 \u0627\u06cc\u0646 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc \u062e\u0648\u0628 \u0631\u0627 \u0627\u0632 O(n\\ MaxLen\\ lg(n))<\/span> \u067e\u06cc\u062f\u0627 \u06a9\u0631\u062f.<\/p>\n\n\n\n

\u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u062f\u0648\u0645:<\/p>\n\n\n\n

\u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u06a9\u062f\u0627\u0645 \u0627\u0632 m<\/span> \u062c\u0627\u06cc\u06af\u0634\u062a \u0686\u06a9 \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u06a9\u0647 \u0628\u0627 \u0686\u0647 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc\u06cc \u0627\u0632 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0635\u0644\u06cc \u0645\u0637\u0627\u0628\u0642\u062a \u062f\u0627\u0631\u062f.
\u0628\u0647 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0635\u0644\u06cc A<\/span> \u0648 \u0628\u0647 \u062c\u0627\u06cc\u06af\u0634\u062a\u06cc \u06a9\u0647 \u0645\u06cc \u062e\u0648\u0627\u0647\u06cc\u0645 \u0645\u06a9\u0627\u0646 \u0647\u0627\u06cc \u0645\u0646\u0637\u0628\u0642 \u0634\u062f\u0646\u0634 \u0628\u0631 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0635\u0644\u06cc \u0631\u0627 \u0628\u06cc\u0627\u0628\u06cc\u0645 B<\/span> \u0645\u06cc \u06af\u0648\u06cc\u06cc\u0645.
\u0645\u0634\u0627\u0628\u0647 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 KMP<\/span> \u0628\u0631\u0627\u06cc \u062a\u0637\u0627\u0628\u0642 \u0631\u0634\u062a\u0647 \u0647\u0627 \u06a9\u0627\u0631 \u0645\u06cc \u06a9\u0646\u06cc\u0645.\u062a\u0639\u0631\u06cc\u0641 \u06a9\u0646\u06cc\u062f f_i <\/span> \u0628\u0632\u0631\u06af\u062a\u0631\u06cc\u0646 \u0637\u0648\u0644 \u06a9\u0645\u062a\u0631 \u0627\u0632 i<\/span> \u0628\u0627\u0634\u062f \u06a9\u0647 \u0641\u0634\u0631\u062f\u0647 B_{1...f_i} <\/span> \u0647\u0645\u0627\u0646 \u0641\u0634\u0631\u062f\u0647 B_{i-f_i+1...i} <\/span> \u0628\u0627\u0634\u062f.\u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0628\u0631\u0627\u06cc \u0627\u06cc\u0646\u06a9\u0647 \u0627\u06cc\u0646 \u0628\u0631\u0642\u0631\u0627\u0631 \u0628\u0627\u0634\u062f \u0628\u0627\u06cc\u062f \u0641\u0634\u0631\u062f\u0647 B_{1...f_i-1} <\/span> \u0647\u0645\u0627\u0646 \u0641\u0634\u0631\u062f\u0647 B_{i-f_i+1...i-1} <\/span> \u0628\u0627\u0634\u062f \u0648 \u0647\u0645\u0686\u0646\u06cc\u0646 \u062a\u0639\u062f\u0627\u062f \u0627\u0639\u062f\u0627\u062f \u06a9\u0645\u062a\u0631 \u0645\u0633\u0627\u0648\u06cc B_i <\/span> \u062f\u0631 [i -f_i+1,i) <\/span> \u0628\u0631\u0627\u0628\u0631 \u0628\u0627 \u062a\u0639\u062f\u0627\u062f \u0627\u0639\u062f\u0627\u062f \u06a9\u0645\u062a\u0631 \u0645\u0633\u0627\u0648\u06cc B_{f_i} <\/span> \u062f\u0631 [1,f_i) <\/span>\u0628\u0627\u0634\u062f(\u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0627 \u06a9\u0645\u06a9 \u0641\u0646\u0648\u06cc\u06a9 \u0627\u06cc\u0646 \u0631\u0627 \u0686\u06a9 \u06a9\u0631\u062f).
\u067e\u0633 \u0645\u06cc \u062a\u0648\u0627\u0646 f<\/span> \u0647\u0627 \u0631\u0627 \u0628\u0647 \u0634\u06cc\u0648\u0647 KMP<\/span> \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u062f.
\u0647\u0645\u0686\u0646\u06cc\u0646 match_i<\/span> \u0631\u0627 \u062a\u0639\u0631\u06cc\u0641 \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0645\u0642\u062f\u0627\u0631\u06cc \u06a9\u0647 \u0641\u0634\u0631\u062f\u0647 A_{i-match_i+1...i}<\/span> \u0647\u0645\u0627\u0646 \u0641\u0634\u0631\u062f\u0647 B_{1...match_i}<\/span> \u0628\u0627\u0634\u062f.\u0645\u0634\u0627\u0628\u0647 \u0628\u0627\u0644\u0627 \u0648 \u0628\u0627 \u062a\u0648\u062c\u0647 \u0628\u0647 \u0634\u06cc\u0648\u0647 \u06a9\u0627\u0631 KMP<\/span> \u0645\u06cc \u062a\u0648\u0627\u0646 match<\/span> \u0647\u0627 \u0631\u0627 \u0647\u0645 \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u062f \u06a9\u0647 \u0627\u06cc\u0646\u06a9\u0627\u0631 \u0627\u0632 O((|A|+|B|)lg(|A|+|B|)) <\/span> \u0627\u0646\u062c\u0627\u0645 \u0645\u06cc \u0634\u0648\u062f(\u0648 \u062f\u0631 \u0646\u0647\u0627\u06cc\u062a \u0645\u06a9\u0627\u0646 \u0647\u0627\u06cc\u06cc \u06a9\u0647 match_i = |B| <\/span> \u0627\u0633\u062a \u0631\u0627 \u0645\u06cc \u062e\u0648\u0627\u0647\u06cc\u0645).<\/p>\n\n\n\n

\u0633\u0648\u0627\u0644\u0627\u062a \u062a\u0631\u06a9\u06cc\u0628\u06cc:<\/a><\/p>\n\n\n\n


\u0627\u062f\u0639\u0627 \u0645\u06cc \u06a9\u0646\u06cc\u0645<\/a> \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0639\u062f\u062f \u0627\u0648\u0644 p<\/span> \u0639\u062f\u062f\u06cc \u0645\u062b\u0644 g<\/span> \u0648\u062c\u0648\u062f \u062f\u0627\u0631\u062f \u06a9\u0647 g^1...g^{p-1} <\/span> \u062a\u0645\u0627\u0645 \u0628\u0627\u0642\u06cc \u0645\u0627\u0646\u062f\u0647 \u0647\u0627\u06cc \u0645\u0645\u06a9\u0646 \u0628\u0647 \u067e\u06cc\u0645\u0627\u0646\u0647 p<\/span> \u0631\u0627 \u062a\u0648\u0644\u06cc\u062f \u0645\u06cc \u06a9\u0646\u0646\u062f.
\u0628\u0647 \u0686\u0646\u06cc\u0646 g<\/span> \u0647\u0627\u06cc\u06cc \u0631\u06cc\u0634\u0647 \u0627\u0648\u0644\u06cc\u0647 p<\/span> \u0645\u06cc \u06af\u0648\u06cc\u06cc\u0645(\u062f\u0631 \u0627\u0646\u062a\u0647\u0627 \u0631\u0648\u0634 \u0628\u0647 \u062f\u0633\u062a \u0627\u0648\u0631\u062f\u0646 \u0631\u06cc\u0634\u0647 \u0627\u0648\u0644\u06cc\u0647 \u0631\u0627 \u062a\u0648\u0636\u06cc\u062d \u0645\u06cc \u062f\u0647\u06cc\u0645).
\u062d\u0627\u0644\u0627 \u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f g<\/span> \u0631\u0627 \u06cc\u0627\u0641\u062a\u0647 \u0627\u06cc\u0645.\u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0639\u062f\u062f \u0628\u06cc\u0646 1<\/span> \u062a\u0627 p-1<\/span> \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u06cc\u062f \u06a9\u0647 \u0645\u0639\u0627\u062f\u0644 \u0686\u0647 \u062a\u0648\u0627\u0646\u06cc \u0627\u0632 g<\/span> \u0627\u0633\u062a \u0627\u06cc\u0646 \u0645\u0642\u062f\u0627\u0631 \u0631\u0627 \u0628\u0631\u0627\u06cc \u0639\u062f\u062f x<\/span> \u0628\u0627 log_x<\/span> \u0646\u0634\u0627\u0646 \u0645\u06cc\u200c\u062f\u0647\u06cc\u0645.
\u062d\u0627\u0644\u0627 \u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647
log_{x*y} \\equiv log_x+log_y \\mod p-1 <\/span><\/p>\n\n\n\n

\u062d\u0627\u0644\u0627 \u0627\u06af\u0631 \u0628\u0647 \u062c\u0627\u06cc \u0647\u0631 \u0639\u062f\u062f log<\/span> \u0627\u0634 \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u0645 \u0639\u0645\u0644\u06cc\u0627\u062a \u0636\u0631\u0628 \u062f\u0631 \u067e\u06cc\u0645\u0627\u0646\u0647 p<\/span> \u0628\u0647 \u062c\u0645\u0639 \u062f\u0631 \u067e\u06cc\u0645\u0627\u0646\u0647 p-1<\/span> \u062a\u0628\u062f\u06cc\u0644 \u0645\u06cc \u0634\u0648\u062f!
\u067e\u0633 \u0627\u06af\u0631 \u062c\u0645\u0639 \u062a\u0645\u0627\u0645 \u0632\u06cc\u0631 \u0645\u062c\u0645\u0648\u0639\u0647 \u0647\u0627\u06cc \u0645\u0645\u06a9\u0646 \u0627\u0632 log_{a_i} <\/span> \u0647\u0627 \u062f\u0631 \u067e\u06cc\u0645\u0627\u0646\u0647 p-1<\/span> \u0631\u0627 \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u06cc\u0645 \u0622\u0646\u06af\u0627\u0647 \u062a\u0645\u0627\u0645 log_{ans} <\/span> \u0647\u0627 \u0631\u0627 \u0628\u0647 \u062f\u0633\u062a \u0627\u0648\u0631\u062f\u06cc\u0645 \u06a9\u0647 ans<\/span> \u0647\u0627 \u062c\u0648\u0627\u0628 \u0647\u0627\u06cc \u0645\u0645\u06a9\u0646 \u0647\u0633\u062a\u0646\u062f.
\u0628\u0631\u0627\u06cc \u062d\u0633\u0627\u0628 \u06a9\u0631\u062f\u0646 \u062c\u0645\u0639 \u062a\u0645\u0627\u0645 \u0632\u06cc\u0631\u0645\u062c\u0645\u0648\u0639\u0647 \u0647\u0627\u06cc \u0645\u0645\u06a9\u0646 \u0627\u0632 \u06a9\u0627\u0641\u06cc\u0633\u062a \u0628\u0647 \u0634\u06cc\u0648\u0647 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u06a9\u0648\u0644\u0647 \u067e\u0634\u062a\u06cc \u06a9\u0627\u0631 \u06a9\u0646\u06cc\u0645 \u0627\u0645\u0627 \u0628\u0627 \u0627\u06cc\u0646 \u062a\u0641\u0627\u0648\u062a \u06a9\u0647 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0627\u06cc\u0646 \u06a9\u0627\u0631 \u0631\u0627 \u0628\u0627 \u0628\u06cc\u062a \u0633\u062a \u0647\u0645 \u0627\u0646\u062c\u0627\u0645 \u062f\u0627\u062f! \u06cc\u0639\u0646\u06cc \u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f dp<\/span> \u0628\u06cc\u062a \u0633\u062a\u06cc \u0628\u0627\u0634\u062f \u06a9\u0647 \u0628\u06cc\u062a i<\/span> \u0627\u0645 \u0622\u0646 \u06f1 \u0627\u0633\u062a \u0627\u06af\u0631 \u0628\u062a\u0648\u0627\u0646 \u0645\u062c\u0645\u0648\u0639\u0647 \u0627\u06cc \u0628\u0627 \u062c\u0645\u0639 i<\/span> \u062f\u0627\u0634\u062a.(\u0627\u0648\u0644 \u06a9\u0627\u0631 dp_0=1<\/span>) \u062d\u0627\u0644\u0627 \u0628\u0639\u062f \u0627\u0632 \u0627\u0636\u0627\u0641\u0647 \u06a9\u0631\u062f\u0646 \u0639\u062f\u062f x<\/span> \u0628\u0647 \u0622\u0631\u0627\u06cc\u0647 \u0645\u0642\u062f\u0627\u0631 \u062c\u062f\u06cc\u062f dp<\/span> \u0628\u0631\u0627\u0628\u0631 \u0628\u0627 dp | (dp << (p-1-x) )<\/span> \u0645\u06cc \u0634\u0648\u062f \u067e\u0633 \u062f\u0631 \u0646\u0647\u0627\u06cc\u062a \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0645\u0627 \u0627\u0632 O(\\frac{np}{32}) <\/span> \u06a9\u0627\u0631 \u0645\u06cc \u06a9\u0646\u062f.
\u0631\u0648\u0634 \u0628\u0647 \u062f\u0633\u062a \u0627\u0648\u0631\u062f\u0646 \u0631\u06cc\u0634\u0647 \u0627\u0648\u0644\u06cc\u0647:
\u0627\u0628\u062a\u062f\u0627 \u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0627\u06af\u0631 d<\/span> \u06a9\u0648\u0686\u06a9\u062a\u0631\u06cc\u0646 \u0639\u062f\u062f\u06cc \u0628\u0627\u0634\u062f \u06a9\u0647 x^d \\equiv 1\\ mod p <\/span> \u0622\u0646\u06af\u0627\u0647 \u062a\u0645\u0627\u0645 \u0627\u0639\u062f\u0627\u062f x^0 ... x^{d-1}<\/span> \u0645\u062a\u0645\u0627\u06cc\u0632\u0646\u062f(\u062f\u0631 \u063a\u06cc\u0631 \u0627\u06cc\u0646\u0635\u0648\u0631\u062a d<\/span> \u0645\u0627 \u0645\u06cc\u0646\u06cc\u0645\u0645 \u0646\u06cc\u0633\u062a).\u0627\u0632 \u0627\u06cc\u0646 \u0645\u0648\u0636\u0648\u0639 \u0646\u062a\u06cc\u062c\u0647 \u0645\u06cc \u0634\u0648\u062f \u06a9\u0647 x^y = x^{y\\ mod\\ d} <\/span> \u067e\u0633 \u0627\u06af\u0631 \u0642\u0631\u0627\u0631 \u0628\u0627\u0634\u062f \u06a9\u0647 x^y \\equiv 1 \\mod p <\/span> \u0622\u0646\u06af\u0627\u0647 \u0628\u0627\u06cc\u062f d|y<\/span>.
\u0627\u0632 \u0637\u0631\u0641\u06cc \u0637\u0628\u0642 \u0642\u0636\u06cc\u0647 \u0641\u0631\u0645\u0627 \u0645\u06cc \u062f\u0627\u0646\u06cc\u0645 \u06a9\u0647 x^{p-1} \\equiv 1 \\mod p <\/span> \u0647\u0645\u0686\u0646\u06cc\u0646 \u0637\u0628\u0642 \u062a\u0639\u0631\u06cc\u0641 \u0648 \u0645\u0637\u0627\u0644\u0628 \u0628\u0627\u0644\u0627 \u0639\u062f\u062f x<\/span> \u0631\u06cc\u0634\u0647 \u0627\u0648\u0644\u06cc\u0647 \u0627\u0633\u062a \u0627\u06af\u0631 \u0648 \u0641\u0642\u0637 \u0627\u06af\u0631 d=p-1<\/span>.
\u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 d|p-1<\/span>.\u062d\u0627\u0644\u0627 \u0627\u06af\u0631 d\\neq p-1<\/span> \u0628\u0627\u06cc\u062f \u0639\u0627\u0645\u0644 \u0627\u0648\u0644\u06cc \u062f\u0631 p-1<\/span> \u0645\u062b\u0644 q<\/span> \u0648\u062c\u0648\u062f \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f \u06a9\u0647 d \\mid \\frac{p-1}{q} <\/span> \u0648 \u062f\u0631 \u0646\u062a\u06cc\u062c\u0647 x^{\\frac{p-1}{q}} \\equiv 1 \\mod p <\/span> .
\u067e\u0633 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0631\u0627\u06cc \u062a\u0645\u0627\u0645 \u0639\u062f\u0627\u062f \u06f1 \u062a\u0627 p-1<\/span> \u0631\u0627 \u0686\u06a9 \u06a9\u0631\u062f \u06a9\u0647 \u0645\u06cc \u062a\u0648\u0627\u0646\u0646\u062f \u0631\u06cc\u0634\u0647 \u0627\u0648\u0644\u06cc\u0647 \u0628\u0627\u0634\u0646\u062f \u06cc\u0627 \u0646\u0647(\u0648 \u0627\u06cc\u0646 \u0641\u0631\u0627\u06cc\u0646\u062f \u0686\u06a9 \u06a9\u0631\u062f\u0646 \u0628\u0627 O(lg(p))<\/span> \u0628\u0627\u0631 \u0628\u0647 \u062a\u0648\u0627\u0646 \u0631\u0633\u0627\u0646\u062f\u0646 \u0647\u0645\u0631\u0627\u0647 \u0627\u0633\u062a). \u067e\u0633 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0627\u06cc\u0646 \u06a9\u0627\u0631 \u0631\u0627 \u0627\u0632 O(g\\times lg(p)^2) <\/span> \u0627\u0646\u062c\u0627\u0645 \u062f\u0627\u062f. <\/p>\n\n\n\n

\u06a9\u067e\u06cc \u067e\u06cc\u0633\u062a:<\/a><\/p>\n\n\n\n

\u0622\u0631\u0627\u06cc\u0647 \u0631\u0627 \u062f\u0631 \u06cc\u06a9 \u062f\u0631\u062e\u062a \u062f\u0648\u062f\u0648\u06cc\u06cc \u0645\u062a\u0648\u0627\u0632\u0646 \u0645\u06cc\u0631\u06cc\u0632\u06cc\u0645 . ( \u0645\u0627\u0646\u0646\u062f AVL\\ Tree<\/span> ) . \u06cc\u06a9 \u06a9\u067e\u06cc \u0627\u0632 \u062f\u0631\u062e\u062a \u0645\u06cc \u06af\u06cc\u0631\u06cc\u0645 \u0648 \u0628\u0627\u0632\u0647 [l,r] <\/span> \u06a9\u067e\u06cc \u0631\u0627 \u0627\u0632 \u062f\u0631\u062e\u062a \u062c\u062f\u0627 \u0645\u06cc \u06a9\u0646\u06cc\u0645 (\u200c\u0627\u06cc\u0646 \u06a9\u0627\u0631 \u0627\u0632 O(h)<\/span> \u0642\u0627\u0628\u0644 \u0627\u0646\u062c\u0627\u0645 \u0627\u0633\u062a). \u0633\u067e\u0633 \u062f\u0631\u062e\u062a \u0627\u0635\u0644\u06cc \u0631\u0627 \u0627\u0632 \u0645\u06a9\u0627\u0646 k<\/span> \u0628\u0647 \u062f\u0648 \u0642\u0633\u0645\u062a \u062a\u0642\u0633\u06cc\u0645 \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u0648 \u0642\u0633\u0645\u062a [l,r]<\/span> \u062f\u0631\u062e\u062a \u0642\u0628\u0644\u06cc \u0631\u0627 \u062f\u0631 \u0641\u0627\u0635\u0644\u0647 k<\/span> \u0648 k+1<\/span> \u0627\u0636\u0627\u0641\u0647 \u0645\u06cc \u06a9\u0646\u06cc\u0645.\u0641\u0642\u0637 \u0646\u0628\u0627\u06cc\u062f \u062f\u0631\u062e\u062a \u0631\u0627 \u0648\u0627\u0642\u0639\u0627 \u06a9\u067e\u06cc \u0628\u06af\u06cc\u0631\u06cc\u0645 \u0632\u06cc\u0631\u0627 \u0632\u0645\u0627\u0646 \u0627\u062c\u0631\u0627\u06cc\u06cc \u06a9\u062f \u0628\u0647 \u0635\u0648\u0631\u062a \u0646\u0645\u0627\u06cc\u06cc \u0632\u06cc\u0627\u062f \u0645\u06cc\u0634\u0648\u062f.\u0635\u0631\u0641\u0627 \u0628\u0627\u06cc\u062f \u062f\u0631 \u0647\u0631 \u0645\u0631\u062d\u0644\u0647 \u062a\u063a\u06cc\u06cc\u0631\u0627\u062a \u062f\u0631\u062e\u062a \u0642\u0628\u0644\u06cc \u0646\u0633\u0628\u062a \u0628\u0647 \u062f\u0631\u062e\u062a \u0647\u0627\u06cc \u062c\u062f\u06cc\u062f \u0631\u0627 \u0630\u062e\u06cc\u0631\u0647 \u06a9\u0646\u06cc\u0645 \u0648 \u0647\u06cc\u0686\u0648\u0642\u062a \u0628\u0647 \u062f\u0627\u062f\u0647\u200c\u0647\u0627\u06cc \u062f\u0631\u062e\u062a\u200c\u0647\u0627\u06cc \u0642\u0628\u0644\u06cc \u062f\u0633\u062a \u0646\u0632\u0646\u06cc\u0645. \u0627\u06af\u0631 \u0627\u06cc\u0646 \u06a9\u0627\u0631 \u0631\u0627 \u06a9\u0646\u06cc\u0645 \u0642\u0633\u0645\u062a \u0647\u0627\u06cc \u062a\u06a9\u0631\u0627\u0631\u06cc \u062f\u0631\u062e\u062a \u062d\u0627\u0641\u0638\u0647 \u0627\u0636\u0627\u0641\u0647 \u0646\u0645\u06cc\u200c\u06af\u06cc\u0631\u0646\u062f.<\/p>\n\n\n\n

\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc O(q\\times lg(N_q)) <\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

\u062e\u0628 \u0628\u062f\u0648\u0646 \u0645\u0642\u062f\u0645\u0647 \u0645\u06cc\u0631\u06cc\u0645 \u0633\u0631\u0627\u063a \u0633\u0648\u0627\u0644 \u0647\u0627 : \u0633\u0648\u0627\u0644 \u0646\u0641\u0633\u200c\u06af\u06cc\u0631:\u200c \u0628\u0631\u0627\u06cc \u0633\u0648\u0627\u0644 \u0627\u0645 \u060c \u0628\u0627\u0631 \u0646\u0641\u0633 \u0647\u0627 \u06af\u0631\u0641\u062a\u0647 \u0645\u06cc \u0634\u0648\u062f….<\/p>\n","protected":false},"author":6,"featured_media":32293,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[141,46,50],"tags":[],"class_list":["post-3404","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-contests-and-events","category-developer","category-quera-developer"],"_links":{"self":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts\/3404","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/comments?post=3404"}],"version-history":[{"count":1,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts\/3404\/revisions"}],"predecessor-version":[{"id":32294,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts\/3404\/revisions\/32294"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/media\/32293"}],"wp:attachment":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/media?parent=3404"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/categories?post=3404"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/tags?post=3404"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}