{"id":2408,"date":"2018-02-27T00:24:39","date_gmt":"2018-02-26T20:54:39","guid":{"rendered":"https:\/\/blog.quera.ir\/?p=2408"},"modified":"2025-03-02T13:55:25","modified_gmt":"2025-03-02T10:25:25","slug":"%d8%b1%d8%a7%d9%87-%d8%ad%d9%84-%d9%87%d8%a7%db%8c-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%d8%b4%d9%85%d8%a7%d8%b1%d9%87-%db%b2%db%b3","status":"publish","type":"post","link":"https:\/\/quera.org\/blog\/%d8%b1%d8%a7%d9%87-%d8%ad%d9%84-%d9%87%d8%a7%db%8c-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%d8%b4%d9%85%d8%a7%d8%b1%d9%87-%db%b2%db%b3\/","title":{"rendered":"\u0631\u0627\u0647 \u062d\u0644 \u0647\u0627\u06cc \u0645\u0633\u0627\u0628\u0642\u0647 \u0634\u0645\u0627\u0631\u0647 \u06f2\u06f3"},"content":{"rendered":"\n

\u0633\u0644\u0627\u0645!
\u062f\u0631 \u0627\u06cc\u0646 \u0628\u0644\u0627\u06af \u0631\u0627\u0647\u200c\u062d\u0644 \u0633\u0648\u0627\u0644\u0627\u062a \u0645\u0633\u0627\u0628\u0642\u0647 \u0634\u0645\u0627\u0631\u0647 \u06f2\u06f3 \u0631\u0648 \u0628\u0647\u200c \u0635\u0648\u0631\u062a \u0641\u0634\u0631\u062f\u0647 \u0628\u06cc\u0627\u0646 \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645!<\/p>\n\n\n\n\n\n\n\n

\u0633\u0648\u0627\u0644 \u062e\u0648\u0627\u0628 \u067e\u0648\u067e\u06a9:<\/b><\/p>\n\n\n\n

\u06a9\u0627\u0641\u06cc \u0627\u0633\u062a \u0645\u0642\u0633\u0648\u0645 \u0639\u0644\u06cc\u0647\u200c\u0647\u0627\u06cc \u062f\u0648 \u0639\u062f\u062f a <\/span> \u0648 b <\/span> \u0631\u0627 \u0641\u06cc\u06a9\u0633 \u06a9\u0631\u062f\u0647 \u0648 \u0627\u06af\u0631 \u0645\u062c\u0645\u0648\u0639\u0634\u0627\u0646 \u0627\u0632 x <\/span> \u06a9\u0645\u062a\u0631 \u0628\u0648\u062f \u0622\u0646 \u062d\u0627\u0644\u062a \u0631\u0627 \u0628\u0647 \u062c\u0648\u0627\u0628 \u0627\u0636\u0627\u0641\u0647 \u06a9\u0646\u06cc\u0645.<\/p>\n\n\n\n

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

\u06a9\u062f \u0631\u0627\u0647 \u062d\u0644<\/a><\/p>\n\n\n\n

\u0633\u0648\u0627\u0644 \u06a9\u0627\u062f\u0648\u06cc \u067e\u0648\u067e\u06a9\u200c\u067e\u0633\u0646\u062f:<\/b><\/p>\n\n\n\n

\u062f\u0631 \u0627\u06cc\u0646 \u0633\u0648\u0627\u0644 \u062c\u0648\u0627\u0628 \u0628\u0647\u06cc\u0646\u0647 \u062f\u0631 \u0635\u0648\u0631\u062a\u06cc \u0627\u0633\u062a \u06a9\u0647 a=1 <\/span> \u0628\u0627\u0634\u062f \u067e\u0633 \u06a9\u0627\u0641\u06cc\u200c\u0627\u0633\u062a \u0635\u0641\u0631\u200c\u0647\u0627\u06cc \u067e\u0634\u062a \u0639\u062f\u062f \u0631\u0627 \u062d\u0630\u0641 \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

\u06a9\u062f \u0631\u0627\u0647 \u062d\u0644<\/a><\/p>\n\n\n\n

\u0633\u0648\u0627\u0644 \u062f\u0646\u0628\u0627\u0644\u0647 \u062a\u0648\u0631\u062c \u067e\u0633\u0646\u062f:<\/b><\/p>\n\n\n\n

\u0628\u0627 \u062a\u0648\u062c\u0647 \u0628\u0647 \u0627\u06cc\u0646\u06a9\u0647 \u0627\u062e\u062a\u0644\u0627\u0641 \u0647\u0631 \u062f\u0648 \u0639\u0636\u0648 \u0645\u062c\u0627\u0648\u0631 \u062f\u0631 \u062f\u0646\u0628\u0627\u0644\u0647 \u06a9\u0645\u062a\u0631\u200c \u0645\u0633\u0627\u0648\u06cc d <\/span> \u0627\u0633\u062a \u0648 \u0639\u0648\u0636 \u0627\u0648\u0644 \u062f\u0646\u0628\u0627\u0644\u0647 \u0646\u06cc\u0632 \u06a9\u0645\u062a\u0631 \u0645\u0633\u0627\u0648\u06cc d <\/span> \u0627\u0633\u062a\u060c \u067e\u0633 \u0639\u0636\u0648 i <\/span> \u0627\u0645 \u062f\u0646\u0628\u0627\u0644\u0647 \u0646\u06cc\u0632 \u06a9\u0645\u062a\u0631 \u0645\u0633\u0627\u0648\u06cc i*d <\/span> \u0645\u06cc\u200c\u0628\u0627\u0634\u062f!<\/p>\n\n\n\n

dp[i][j]<\/span> \u0631\u0627 \u0628\u0647 \u0627\u06cc\u0646 \u0635\u0648\u0631\u062a \u062a\u0639\u0631\u06cc\u0641 \u0645\u06cc\u06a9\u0646\u06cc\u0645: \u062a\u0639\u062f\u0627\u062f \u062f\u0646\u0628\u0627\u0644\u0647\u200c\u0647\u0627\u06cc \u0628\u0647 \u0637\u0648\u0644 i<\/span> \u06a9\u0647 \u0622\u062e\u0631\u06cc\u0646 \u0639\u0636\u0648 \u0622\u0646 \u0628\u0631\u0627\u0628\u0631 j <\/span> \u0628\u0627\u0634\u062f.
\u0628\u0646\u0627\u0628\u0631\u0627\u06cc\u0646 \u062d\u062f\u0627\u06a9\u062b\u0631 \u0645\u0642\u062f\u0627\u0631 j <\/span> \u062f\u0631 \u062f\u0627\u0645\u0646\u0647 dp <\/span> \u0647\u0627\u060c d*k<\/span> \u0627\u0633\u062a\u060c \u0628\u0646\u0627\u0628\u0631\u0627\u06cc\u0646 \u062a\u0639\u062f\u0627\u062f \u062d\u0627\u0644\u0627\u062a dp<\/span> \u0628\u0631\u0627\u0628\u0631 \u0628\u0627 k^2*d<\/span> \u0627\u0633\u062a .<\/p>\n\n\n\n

\u0628\u0631\u0627\u06cc \u0645\u062d\u0627\u0633\u0628\u0647 \u0647\u0631 \u062d\u0627\u0644\u062a \u0627\u0632 dp <\/span> \u060c \u062f\u0631 O(1) <\/span> \u060c \u06a9\u0627\u0641\u06cc \u0627\u0633\u062a Partial Sum <\/span> \u0627\u0632 dp<\/span> \u0647\u0627\u06cc \u0633\u0637\u0631 \u0642\u0628\u0644\u06cc \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u06cc\u0645 .<\/p>\n\n\n\n

\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc: O(k^2d) <\/span><\/p>\n\n\n\n

\u06a9\u062f \u0631\u0627\u0647 \u062d\u0644<\/a><\/p>\n\n\n\n

\u0633\u0648\u0627\u0644 \u0627\u0646\u062a\u0642\u0627\u0645 \u062a\u0648\u06a9:<\/b><\/p>\n\n\n\n

\u06cc\u06a9 dsu<\/span> \u0646\u06af\u0647 \u0645\u06cc\u200c\u062f\u0627\u0631\u06cc\u0645 \u0628\u0647 \u0637\u0648\u0631\u06cc \u06a9\u0647 \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0646\u0641\u0631 xor<\/span> \u062e\u0648\u062f\u0634 \u0628\u0627 \u067e\u062f\u0631\u0634 \u062f\u0631 dsu<\/span> \u0631\u0627 \u062f\u0627\u0631\u06cc\u0645 \u062f\u0631 \u0627\u0628\u062a\u062f\u0627 \u067e\u062f\u0631 \u0647\u0631 \u06a9\u0633 \u062e\u0648\u062f\u0634 \u0627\u0633\u062a \u0648 xor<\/span> \u0647\u0631 \u06a9\u0633 \u0628\u0627 \u062e\u0648\u062f\u0634 0 \u0627\u0633\u062a.<\/p>\n\n\n\n

\u062f\u0631 \u0627\u06cc\u0646\u0635\u0648\u0631\u062a \u0645\u06cc\u200c\u062a\u0648\u0627\u0646 xor<\/span> \u0647\u0631 \u06a9\u0633 \u062a\u0627 \u0631\u06cc\u0634\u0647 \u0631\u0627 \u062f\u0627\u0634\u062a \u0686\u0648\u0646 xor<\/span> \u0647\u0631 \u06a9\u0633 \u0628\u0627 \u067e\u062f\u0631\u0634 \u0631\u0627 \u062f\u0627\u0631\u06cc\u0645 \u0631\u0648\u06cc \u0645\u0633\u06cc\u0631 \u0622\u0646 \u0631\u0627\u0633 \u062a\u0627 \u0631\u06cc\u0634\u0647 \u0627\u0634 \u062d\u0631\u06a9\u062a \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645 \u0648 \u0647\u0645\u0647 \u0627\u06cc\u0646 \u0627\u0639\u062f\u0627\u062f \u0631\u0627 ( xor<\/span> \u0647\u0631 \u06a9\u0633 \u0628\u0627 \u067e\u062f\u0631\u0634) \u0628\u0627 \u0647\u0645 xor<\/span> \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645 \u0648 \u0622\u0646 \u0631\u0627 w<\/span> \u0628\u0646\u0627\u0645\u06cc\u0645\u060c w<\/span> \u0628\u0631\u0627\u0628\u0631 xor<\/span> \u0622\u0646 \u0631\u0627\u0633 \u0648 \u0631\u06cc\u0634\u0647\u200c\u0627\u0634 \u0627\u0633\u062a \u0686\u0648\u0646:<\/p>\n\n\n\n

\u0627\u06af\u0631 \u0645\u0633\u06cc\u0631 v_0,v_1,...,v_k<\/span> \u0628\u0627\u0634\u062f:<\/p>\n\n\n w=(a_{v_0}\\oplus a_{v_1})\\oplus (a_{v_1}\\oplus a_{v_2})\\oplus...\\oplus (a_{v_{k-1}}\\oplus a_{v_k})=a_{v_0}\\oplus a_{v_1}<\/span>\n\n\n\n

\u0648 xor<\/span> \u0647\u0631 \u062f\u0648 \u0631\u0627\u0633 \u0647\u0645 \u06a9\u0647 \u0628\u0627 \u0647\u0645 \u062f\u0631 \u06cc\u06a9 \u0645\u0648\u0644\u0641\u0647 \u0628\u0627\u0634\u0646\u062f \u0645\u062b\u0644 u,v<\/span> \u0631\u0627 \u06a9\u0647 \u0631\u06cc\u0634\u0647 \u0627\u0634\u0627\u0646 s<\/span> \u0627\u0633\u062a \u0631\u0627 \u0628\u0647 \u0635\u0648\u0631\u062a \u0632\u06cc\u0631 \u062f\u0627\u0631\u06cc\u0645:<\/p>\n\n\n a_u\\oplus a_v=(a_u\\oplus a_s)+(a_v\\oplus a_s)<\/span>\n\n\n\n

\u067e\u0633 \u0627\u06af\u0631 \u0627\u0632 \u0647\u0631 \u0645\u0648\u0644\u0641\u0647 \u06cc\u06a9 \u0639\u062f\u062f \u0631\u0627 \u0641\u06cc\u06a9\u0633 \u06a9\u0646\u06cc\u0645 \u0628\u0642\u06cc\u0647 \u0628\u0647 \u0635\u0648\u0631\u062a \u06cc\u06a9\u062a\u0627 \u062f\u0631 \u0645\u06cc\u200c\u0622\u06cc\u0646\u062f\u060c \u067e\u0633 \u0627\u06af\u0631 \u062a\u0639\u062f\u0627\u062f \u0645\u0648\u0644\u0641\u0647 \u0647\u0627 f<\/span> \u0628\u0627\u0634\u062f (\u06a9\u0647 f<\/span> \u0631\u0627 \u0628\u0627 dsu<\/span> \u062f\u0627\u0631\u06cc\u0645) \u062c\u0648\u0627\u0628 \u0628\u0631\u0627\u0628\u0631 \u0627\u0633\u062a \u0628\u0627: ans=(2^{31})^f<\/span><\/p>\n\n\n\n

\u0647\u0631 \u0634\u0631\u0637 \u06a9\u0647 \u0627\u0636\u0627\u0641\u0647 \u0645\u06cc \u0634\u0648\u062f \u0628\u0647 \u0634\u06a9\u0644 u,v,k<\/span> \u0627\u0633\u062a:<\/p>\n\n\n\n

\u0627\u06af\u0631 u,v<\/span> \u062f\u0631 \u06cc\u06a9 \u0645\u0648\u0644\u0641\u0647 \u0628\u0648\u062f\u0646\u062f: \u062f\u0631 \u0627\u06cc\u0646 \u0635\u0648\u0631\u062a a_u\\oplus a_v <\/span> \u0631\u0627 \u062f\u0627\u0631\u06cc\u0645 \u0627\u06af\u0631 \u0628\u0631\u0627\u0628\u0631 k<\/span> \u0646\u0628\u0648\u062f \u0627\u06cc\u0646 \u0634\u0631\u0637 \u06cc\u06a9 \u062a\u0646\u0627\u0642\u0636 \u0627\u0633\u062a \u067e\u0633 \u0627\u0632 \u0627\u06cc\u0646 \u0628\u0647 \u0628\u0639\u062f \u062a\u0639\u062f\u0627\u062f \u062d\u0627\u0644\u062a\u200c\u0647\u0627 \u0628\u0631\u0627\u0628\u0631 0 \u0627\u0633\u062a.<\/p>\n\n\n\n

\u0627\u06af\u0631 u,v<\/span> \u062f\u0631 \u06cc\u06a9 \u0645\u0648\u0644\u0641\u0647 \u0646\u0628\u0648\u062f\u0646\u062f: \u062f\u0631 \u0627\u06cc\u0646\u0635\u0648\u0631\u062a \u0647\u06cc\u0686 \u0648\u0642\u062a \u0628\u0647 \u062a\u0646\u0627\u0642\u0636 \u0646\u0645\u06cc \u0631\u0633\u06cc\u0645 \u0686\u0648\u0646 \u062a\u0627 \u0642\u0628\u0644 \u0627\u0632 \u0627\u06cc\u0646 \u0647\u06cc\u0686 \u0634\u0631\u0637\u06cc \u0628\u06cc\u0646 \u0627\u06cc\u0646 \u062f\u0648 \u0645\u0648\u0644\u0641\u0647 \u0646\u0628\u0648\u062f\u0647 \u0648 \u062d\u062f\u0627\u0642\u0644 \u06cc\u06a9 \u062d\u0627\u0644\u062a \u0647\u0633\u062a \u0628\u0647 \u0627\u06cc\u0646 \u0635\u0648\u0631\u062a \u06a9\u0647 a_u=0 , a_v=k<\/span> \u0628\u0627\u0634\u062f \u0648 \u0628\u0642\u06cc\u0647 \u06cc\u06a9\u062a\u0627 \u0637\u0628\u0642 \u0686\u06cc\u0632\u06cc \u06a9\u0647 \u0642\u0628\u0644\u0627 \u06af\u0641\u062a\u0647 \u0634\u062f \u062f\u0631 \u0645\u06cc\u200c\u0622\u06cc\u0646\u062f \u0648 \u0634\u0631\u0637 \u062c\u062f\u06cc\u062f \u0646\u06cc\u0632 \u0628\u0631\u0642\u0631\u0627\u0631 \u0627\u0633\u062a \u067e\u0633 \u06a9\u0627\u0641\u06cc\u0633\u062a \u0627\u06cc\u0646 \u062f\u0648 \u0645\u0648\u0644\u0641\u0647 \u0631\u0627 \u062f\u0631 dsu<\/span> \u0645\u0631\u062c \u06a9\u0646\u06cc\u0645.
\u0627\u06af\u0631 \u0631\u06cc\u0634\u0647\u200c\u0647\u0627\u06cc\u0634\u0627\u0646 \u0628\u0647 \u062a\u0631\u062a\u06cc\u0628 s,t <\/span> \u0628\u0648\u062f\u0646\u062f \u062f\u0631 \u0627\u06cc\u0646\u0635\u0648\u0631\u062a :<\/p>\n\n\n a_s\\oplus a_t=(a_u\\oplus a_v)+(a_u\\oplus a_s)+(a_v\\oplus a_t)<\/span>\n\n\n\n

\u067e\u0633 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u0645 \u062f\u0631 dsu<\/span> \u0628\u06cc\u0646 \u062f\u0648 \u0631\u0627\u0633  s,t<\/span> \u06cc\u0627\u0644 \u0628\u06af\u0630\u0627\u0631\u06cc\u0645.<\/p>\n\n\n\n

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

\u0633\u0648\u0627\u0644 \u062a\u0648\u06a9 \u0648 \u0635\u0645\u062f :\u200c<\/b>
\u06af\u0631\u0627\u0641\u06cc \u062c\u062f\u06cc\u062f \u0628\u0633\u0627\u0632\u06cc\u062f \u0648 \u0628\u06cc\u0646 \u0631\u0627\u0633 \u0647\u0627\u06cc i,j<\/span> \u060c \u06cc\u0627\u0644\u06cc \u0628\u0627 \u0648\u0632\u0646 A_{i,j}<\/span> \u0642\u0631\u0627\u0631 \u062f\u0647\u06cc\u062f\u060c \u0627\u06a9\u0646\u0648\u0646 \u062f\u0631 \u0627\u06cc\u0646 \u06af\u0631\u0627\u0641 \u0628\u0647 \u06a9\u0645\u06a9 Floyd<\/span> \u0637\u0648\u0644 \u06a9\u0648\u062a\u0627\u0647\u200c\u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0627\u0632 i<\/span> \u0628\u0647 j<\/span> \u0631\u0627\u062d\u0633\u0627\u0628 \u06a9\u0631\u062f\u0647 \u0648 B_{i,j}<\/span> \u0628\u0646\u0627\u0645\u06cc\u062f\u060c \u0686\u0646\u0627\u0646\u0686\u0647 \u0645\u0627\u062a\u0631\u06cc\u0633 \u0647\u0627\u06cc A,B<\/span> \u0645\u0633\u0627\u0648\u06cc \u0646\u0628\u0627\u0634\u0646\u062f\u060c \u0646\u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u0637\u0648\u0631\u06cc \u062a\u0648\u0646\u0644\u200c\u0647\u0627 \u0631\u0627 \u0633\u0627\u062e\u062a \u06a9\u0647 \u0634\u0631\u0627\u06cc\u0637 \u0628\u0631\u0642\u0631\u0627\u0631 \u0628\u0627\u0634\u062f \u060c \u0627\u062b\u0628\u0627\u062a \u0627\u0645\u0631 \u0646\u06cc\u0632 \u0648\u0627\u0636\u062d \u0627\u0633\u062a \u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f \u0628\u0631\u0627\u06cc \u06cc\u06a9 i,j<\/span> \u062e\u0627\u0635 B_{i,j}<A_{i,j}<\/span> \u0628\u0627\u0634\u062f\u060c \u0645\u0633\u06cc\u0631\u06cc \u06a9\u0647 \u0637\u06cc \u06a9\u0631\u062f\u06cc\u0645 \u062f\u0631 \u06af\u0631\u0627\u0641 \u062c\u062f\u06cc\u062f \u06a9\u0647 \u0637\u0648\u0644\u0634 B_{i,j}<\/span> \u0634\u062f\u0647 \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631\u0628\u06af\u06cc\u0631\u06cc\u062f\u060c \u062f\u0631 \u06af\u0631\u0627\u0641 \u0627\u0635\u0644\u06cc \u0646\u06cc\u0632 \u062f\u0642\u06cc\u0642\u0627 \u0628\u0627 \u0637\u06cc \u06a9\u0631\u062f\u0646 \u0647\u0645\u0627\u0646 \u06a9\u0648\u062a\u0627\u0647\u200c\u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631\u200c\u0647\u0627 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u0645 \u0628\u0627 \u0645\u0633\u06cc\u0631\u06cc \u0628\u0647 \u0637\u0648\u0644 B_{i,j}<\/span> \u0627\u0632 i<\/span> \u0628\u0647 j<\/span> \u0628\u0631\u0633\u06cc\u0645\u060c \u067e\u0633 A_{i,j}<\/span> \u0646\u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u062f \u0637\u0648\u0644 \u06a9\u0648\u062a\u0627\u0647\u200c\u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0628\u0627\u0634\u062f! \u0628\u0631\u0627\u06cc \u0634\u0645\u0631\u062f\u0646 \u062a\u0639\u062f\u0627\u062f \u06cc\u0627\u0644\u200c\u0647\u0627\u06cc \u06a9\u0645\u06cc\u0646\u0647 \u0644\u0627\u0632\u0645 \u0628\u0631\u0627\u06cc \u0633\u0627\u062e\u062a \u0686\u0646\u06cc\u0646 \u06af\u0631\u0627\u0641\u06cc \u0646\u06cc\u0632 \u0628\u0647 \u0627\u06cc\u0646 \u0634\u06a9\u0644 \u0639\u0645\u0644 \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645\u060c \u0628\u0631\u0627\u06cc \u0647\u0631 \u062c\u0641\u062a i,j<\/span> :
\u06cc\u0627\u0644 i,j<\/span> \u0631\u0627 \u0645\u06cc\u200c\u06af\u0630\u0627\u0631\u06cc\u0645 \u0627\u06af\u0631 \u0648 \u062a\u0646\u0647\u0627 \u0627\u06af\u0631 \u0647\u06cc\u0686 k<\/span> \u0627\u06cc \u0646\u0627\u0645\u0633\u0627\u0648\u06cc i,j<\/span> \u0648\u062c\u0648\u062f \u0646\u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f \u06a9\u0647 A_{i,j}=A_{i,k}+A_{k,j}<\/span> \u060c \u0648\u0627\u0636\u062d \u0627\u0633\u062a \u06a9\u0647 \u06cc\u0627\u0644\u200c\u0647\u0627\u06cc\u06cc \u06a9\u0647 \u0645\u06cc\u200c\u0633\u0627\u0632\u06cc\u0645 \u0642\u0637\u0639\u0627 \u0644\u0627\u0632\u0645 \u0647\u0633\u062a\u0646\u062f \u0686\u0631\u0627 \u06a9\u0647 \u0628\u062f\u0648\u0646 \u0622\u0646\u0647\u0627 \u0646\u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u0645\u0633\u06cc\u0631\u06cc \u0628\u06cc\u0646 i,j<\/span> \u0628\u0627 \u0648\u0632\u0646 A_{i,j}<\/span> \u0637\u06cc \u06a9\u0631\u062f!<\/p>\n\n\n\n

\u0627\u06a9\u0646\u0648\u0646 \u0646\u0634\u0627\u0646 \u0645\u06cc\u200c\u062f\u0647\u06cc\u0645 \u0628\u0627 \u0647\u0645\u06cc\u0646 \u06cc\u0627\u0644\u200c\u0647\u0627 \u06a9\u0647 \u0633\u0627\u062e\u062a\u0647\u200c\u0627\u06cc\u0645 \u0646\u06cc\u0632 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u0628\u06cc\u0646 \u0647\u0631 \u062f\u0648 \u0631\u0627\u0633\u06cc \u0628\u0627 \u0645\u0633\u06cc\u0631\u06cc \u0628\u0647 \u0637\u0648\u0644  A_{i,j}<\/span> \u0631\u0633\u06cc\u062f\u060c \u06cc\u0647 \u0634\u06a9\u0644 \u0627\u0633\u062a\u0642\u0631\u0627\u06cc\u06cc \u0631\u0648\u06cc \u0637\u0648\u0644 \u0645\u0633\u06cc\u0631\u200c\u0647\u0627 \u062d\u06a9\u0645 \u0631\u0627 \u0646\u0634\u0627\u0646 \u0645\u06cc\u200c\u062f\u0647\u06cc\u0645\u060c \u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f \u0628\u06cc\u0646 i,j<\/span> \u06cc\u0627\u0644\u06cc \u0646\u0645\u06cc\u200c\u06af\u0630\u0627\u0631\u06cc\u0645 \u067e\u0633 k<\/span> \u0627\u06cc \u0648\u062c\u0648\u062f \u062f\u0627\u0634\u062a\u0647 \u0627\u0633\u062a \u06a9\u0647 A_{i,j}=A_{i,k}+A_{k,j}<\/span> \u060c \u067e\u0633 \u0686\u0648\u0646 A_{i,j}>A_{i,k},A_{k,j}<\/span> \u067e\u0633 \u0637\u0628\u0642 \u0627\u0633\u062a\u0642\u0631\u0627\u060c \u06a9\u0648\u062a\u0627\u0647\u200c\u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u0628\u06cc\u0646 i,k<\/span> \u0648 k,j<\/span> \u0628\u0627 \u0637\u0648\u0644\u200c\u0647\u0627\u06cc \u062f\u0644\u062e\u0648\u0627\u0647 \u0648\u062c\u0648\u062f \u062f\u0627\u0631\u062f\u060c \u067e\u0633 \u06a9\u0648\u062a\u0627\u0647\u200c\u062a\u0631\u06cc\u0646 \u0645\u0633\u06cc\u0631\u06cc \u0628\u06cc\u0646 i,j<\/span> \u0628\u0627 \u0637\u0648\u0644 \u0645\u0648\u0631\u062f\u0646\u0638\u0631 \u06cc\u0627\u0641\u062a \u0645\u06cc\u200c\u0634\u0648\u062f!<\/p>\n\n\n\n

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

\u06a9\u062f \u0631\u0627\u0647 \u062d\u0644<\/a><\/p>\n\n\n\n

\u0633\u0648\u0627\u0644 \u0646\u0642\u0634\u0647 \u062d\u0645\u0644\u0647:<\/b><\/p>\n\n\n\n

\u06a9\u0645\u062a\u0631\u06cc\u0646 \u0636\u0639\u0641 \u06cc\u06a9 \u0646\u0642\u0634\u0647 [sqrt(n-1)]<\/span> \u0627\u0633\u062a.(\u0645\u0646\u0638\u0648\u0631 \u0627\u0632  [x]<\/span> \u0628\u0632\u0631\u06af\u062a\u0631\u06cc\u0646 \u0639\u062f\u062f \u0635\u062d\u06cc\u062d \u06a9\u0648\u0686\u06a9\u062a\u0631 \u06cc\u0627 \u0645\u0633\u0627\u0648\u06cc  \u0627\u0632 x <\/span> \u0627\u0633\u062a.)<\/p>\n\n\n\n

\u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f \u0628\u062e\u0648\u0627\u0647\u06cc\u0645 \u0636\u0639\u0641 \u0646\u0642\u0634\u0647 \u06a9\u0645\u062a\u0631 \u0627\u0632 d<\/span> \u0628\u0627\u0634\u062f\u060c \u06cc\u06a9 \u0645\u0633\u062a\u0637\u06cc\u0644 d*n<\/span> \u0627\u0632 \u0628\u0627\u0644\u0627\u06cc \u0645\u0631\u0628\u0639\u200c\u0645\u0627\u0646 \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f \u0642\u0631\u0627\u0631 \u062f\u0647\u06cc\u062f a=[n\/d]<\/span> \u060c \u0648\u0627\u0636\u062d \u0627\u0633\u062a \u06a9\u0647 \u0628\u0627\u06cc\u062f \u062f\u0631 a<\/span> \u0645\u0631\u0628\u0639 d*d<\/span> \u062f\u0631 \u0647\u0631 \u06a9\u062f\u0627\u0645 \u0627\u0642\u0644\u0627 \u06cc\u06a9 \u0633\u0631\u0628\u0627\u0632 \u0642\u0631\u0627\u0631 \u062f\u0647\u06cc\u0645.
\u067e\u0633 \u0686\u0648\u0646 \u06a9\u0644\u0627 \u0627\u06cc\u0646 \u0633\u0631\u0628\u0627\u0632\u200c\u0647\u0627 \u0631\u0627 \u0628\u0627\u06cc\u062f \u062f\u0631 d<\/span> \u0633\u0637\u0631 \u0642\u0631\u0627\u0631 \u062f\u0647\u06cc\u0645 \u0648 \u0647\u06cc\u0686 \u062f\u0648 \u0633\u0631\u0628\u0627\u0632\u06cc \u062f\u0631 \u06cc\u06a9 \u0633\u0637\u0631 \u0646\u06cc\u0633\u062a\u0646\u062f\u060c \u067e\u0633 \u0628\u0627\u06cc\u062f a<=d<\/span> \u0628\u0627\u0634\u062f.<\/p>\n\n\n\n

n = a * d + r (0 <= r < d) <\/span><\/p>\n\n\n\n

a <= d <\/span><\/p>\n\n\n\n

n <= d * d + r < d * (d + 1) <\/span><\/p>\n\n\n\n

d >= sqrt(n - 1) <\/span><\/p>\n\n\n\n

\u0645\u062d\u0627\u0633\u0628\u0627\u062a \u0627\u0646\u062c\u0627\u0645 \u0634\u062f\u0647 \u0646\u0634\u0627\u0646 \u0645\u06cc\u200c\u062f\u0647\u062f \u06a9\u0647 \u0636\u0639\u0641 \u0646\u0642\u0634\u0647 \u0646\u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u062f \u06a9\u0645\u062a\u0631 [sqrt(n-1)-1]<\/span> \u0628\u0627\u0634\u062f \u060c \u0627\u06a9\u0646\u0648\u0646 \u0628\u0627\u06cc\u062f \u0646\u0634\u0627\u0646 \u062f\u0647\u06cc\u0645 \u06a9\u0647 \u062e\u0648\u062f [sqrt(n-1)-1]<\/span> \u0646\u06cc\u0632 \u0646\u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u062f \u0628\u0627\u0634\u062f .<\/p>\n\n\n\n

\u0645\u0642\u062f\u0627\u0631 A=[sqrt(n-1)]<\/span> \u062a\u0639\u0631\u06cc\u0641 \u06a9\u0646\u06cc\u062f\u060c \u0642\u0631\u0627\u0631 \u062f\u0647\u06cc\u062f A<\/span>% r=n<\/span> \u060c \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0647 \u0648\u0636\u0648\u062d \u062f\u06cc\u062f \u06a9\u0647 \u0628\u0627 \u0635\u062f\u0642 \u06a9\u0631\u062f\u0646 \u0634\u0631\u0627\u06cc\u0637 \u0628\u0627\u0644\u0627 \u060c \u0642\u0637\u0639\u0627 r!=0<\/span> \u0627\u0633\u062a! \u0645\u0631\u0628\u0639 n*n<\/span> \u0631\u0627 \u0628\u0647 \u0645\u0631\u0628\u0639 \u0647\u0627\u06cc A*A<\/span> \u062a\u0642\u0633\u06cc\u0645 \u06a9\u0646\u06cc\u062f (\u062f\u0631 \u0646\u0647\u0627\u06cc\u062a \u0628\u062e\u0634\u06cc \u0627\u0632 \u0645\u0631\u0628\u0639 \u06a9\u0647 \u062a\u0642\u0633\u06cc\u0645 \u0646\u0645\u06cc\u200c\u0634\u0648\u062f \u0631\u0627 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0627 \u0633\u0647 \u0634\u06a9\u0644 r*r,(n-r)*r,r*(n-r)<\/span> \u0646\u0634\u0627\u0646 \u062f\u0627\u062f! \u062f\u0631 \u0647\u0631 \u06cc\u06a9 \u0627\u0632 \u0645\u0631\u0628\u0639 \u0647\u0627\u06cc A*A<\/span> \u0628\u0627\u06cc\u062f \u0627\u0642\u0644\u0627 \u06cc\u06a9 \u0633\u0631\u0628\u0627\u0632 \u0642\u0631\u0627\u0631 \u062f\u0647\u06cc\u0645\u060c \u0628\u0627\u0644\u0627\u062a\u0631\u06cc\u0646 \u0645\u0631\u0628\u0639 \u0647\u0627\u06cc A*A<\/span> \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f\u060c \u0642\u0637\u0639\u0627 \u062f\u0631 \u06cc\u06a9\u06cc \u0627\u0632\u200c\u0622\u0646\u200c\u0647\u0627 \u0645\u062c\u0628\u0648\u0631\u06cc\u0645 \u0633\u0631\u0628\u0627\u0632\u06cc \u062f\u0631 \u0633\u0637\u0631 \u0627\u0648\u0644\u0634 \u0642\u0631\u0627\u0631 \u062f\u0647\u06cc\u0645\u060c A*A<\/span> \u0647\u0627\u06cc \u067e\u0627\u06cc\u06cc\u0646 \u0627\u06cc\u0646 \u0645\u0631\u0628\u0639 \u0631\u0627 \u0646\u06cc\u0632 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f\u060c \u062f\u0631 \u0627\u06cc\u0646 A*A<\/span> \u0647\u0627 \u0647\u0645\u060c \u0628\u0627\u06cc\u062f \u0633\u0631\u0628\u0627\u0632 \u0631\u0627 \u062f\u0631 \u0633\u0637\u0631 \u0627\u0648\u0644 \u0642\u0631\u0627\u0631 \u062f\u0647\u06cc\u062f (\u0648\u06af\u0631\u0646\u0647 \u0645\u0631\u0628\u0639 A*A<\/span> \u0633\u0627\u062e\u062a\u0647 \u0645\u06cc\u200c\u0634\u0648\u062f)\u060c \u0627\u06a9\u0646\u0648\u0646 \u067e\u0627\u06cc\u06cc\u0646 \u062a\u0631\u06cc\u0646 \u0627\u06cc\u0646 \u0645\u0631\u0628\u0639\u0627\u062a \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f\u060c \u062f\u0631 \u0632\u06cc\u0631 \u0627\u06cc\u0646 \u0645\u0631\u0628\u0639 \u060c \u06cc\u06a9 \u0634\u06a9\u0644 r*A<\/span> \u062f\u0627\u0631\u06cc\u0645 \u06a9\u0647 \u0628\u0647 \u0648\u0636\u0648\u062d \u062f\u0631 \u0622\u0646 \u0646\u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u0645 \u0633\u0631\u0628\u0627\u0632\u06cc \u0642\u0631\u0627\u0631 \u062f\u0647\u06cc\u0645(\u0686\u0648\u0646 \u062f\u0631 \u0647\u0645\u06af\u06cc \u0633\u062a\u0648\u0646\u200c\u0647\u0627\u06cc\u0634 \u0633\u0631\u0628\u0627\u0632 \u062f\u0627\u0631\u06cc\u0645) \u060c \u062f\u0631 \u0646\u062a\u06cc\u062c\u0647 \u0645\u0631\u0628\u0639\u06cc A*A<\/span> \u062f\u0631 \u0634\u06a9\u0644 \u0627\u06cc\u062c\u0627\u062f \u0645\u06cc\u200c\u0634\u0648\u062f! \u067e\u0633 \u0627\u06cc\u0646 \u062d\u0627\u0644\u062a \u0646\u06cc\u0632 \u0628\u0647 \u0646\u062a\u06cc\u062c\u0647 \u0646\u0645\u06cc\u200c\u0631\u0633\u062f!<\/p>\n\n\n\n

\u0628\u0631\u0627\u06cc \u0633\u0627\u062e\u062a \u0645\u062b\u0627\u0644\u06cc \u06a9\u0647 \u0633\u0627\u06cc\u0632 \u0628\u06cc\u0634\u062a\u0631\u06cc\u0646 \u0645\u0631\u0628\u0639 A<\/span> \u0628\u0627\u0634\u062f\u060c \u0647\u0645 \u0628\u0647 \u0627\u06cc\u0646 \u0634\u06a9\u0644 \u0639\u0645\u0644 \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645\u060c<\/p>\n\n\n\n

t=A+1;<\/p>\n\n\n\n

for(int i=1; i<=t; i++){<\/p>\n\n\n\n

int j = i;<\/p>\n\n\n\n

while(j <= n){<\/p>\n\n\n\n

ans.pb(j); \/\/be tartib satr ha ra misazim!<\/p>\n\n\n\n

j += t;<\/p>\n\n\n\n

}<\/p>\n\n\n\n

}<\/p>\n\n\n\n

\u0627\u06a9\u0646\u0648\u0646 \u0642\u0633\u0645\u062a \u0627\u0648\u0644 \u0645\u0633\u0627\u0644\u0647 \u0631\u0627 \u062d\u0644 \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645!<\/p>\n\n\n\n

\u0631\u0648\u06cc \u062c\u0648\u0627\u0628 \u0628\u0627\u06cc\u0646\u0631\u06cc \u0633\u0631\u0686 \u0645\u06cc\u200c\u0632\u0646\u06cc\u0645 \u062d\u0627\u0644\u0627 \u0628\u0627\u06cc\u062f \u0686\u06a9 \u06a9\u0646\u06cc\u0645 \u0622\u06cc\u0627 \u0645\u0631\u0628\u0639\u06cc \u0628\u0647 \u0636\u0644\u0639 x<\/span> \u062f\u0627\u0631\u06cc\u0645 \u06a9\u0647 \u062f\u0631\u0648\u0646\u0634 \u0633\u0631\u0628\u0627\u0632\u06cc \u0646\u0628\u0627\u0634\u062f.
\u0627\u06af\u0631 \u0647\u0645\u0686\u06cc\u0646 \u0645\u0631\u0628\u0639\u06cc \u0648\u062c\u0648\u062f \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f \u062d\u062a\u0645\u0627 \u0645\u0631\u0628\u0639\u06cc \u0628\u0647 \u0636\u0644\u0639 x<\/span> \u0648\u062c\u0648\u062f \u062f\u0627\u0631\u062f \u06a9\u0647 \u06cc\u0627 \u0633\u0645\u062a \u0631\u0627\u0633\u062a\u0634 \u06cc\u06a9 \u0633\u0631\u0628\u0627\u0632 \u0628\u0627\u0634\u062f \u06cc\u0627 \u0633\u0645\u062a \u0686\u0628 \u0622\u0646 \u0686\u0648\u0646:<\/p>\n\n\n\n

\u0622\u0646 \u0631\u0627 \u062a\u0627 \u062c\u0627\u06cc\u06cc \u06a9\u0647 \u0647\u0646\u0648\u0632 \u0647\u06cc\u0686 \u0633\u0631\u0628\u0627\u0632\u06cc \u0633\u0645\u062a \u0631\u0627\u0633\u062a\u0634 \u0646\u0628\u0627\u0634\u062f \u0628\u0647 \u0633\u0645\u062a \u0631\u0627\u0633\u062a \u0628\u06cc\u0627\u0648\u0631\u06cc\u062f \u0627\u06af\u0631 \u0628\u0647 \u06a9\u0646\u0627\u0631\u0647 \u0646\u0642\u0634\u0647 \u0628\u0631\u062e\u0648\u0631\u062f \u06a9\u0631\u062f \u0622\u0646 \u0631\u0627 \u062a\u0627 \u062c\u0627\u06cc \u0645\u0645\u06a9\u0646 \u0628\u0647 \u0633\u0645\u062a \u0686\u067e \u0628\u06cc\u0627\u0648\u0631\u06cc\u062f \u062f\u0631 \u062c\u0627\u06cc\u06cc \u0627\u06cc\u0646 \u0628\u06cc\u0646 \u062d\u062a\u0645\u0627 \u0628\u0647 \u06cc\u06a9 \u0633\u0631\u0628\u0627\u0632 \u0627\u0632 \u0633\u0645\u062a \u0686\u067e \u06cc\u0627 \u0631\u0627\u0633\u062a \u0628\u0631\u062e\u0648\u0631\u062f \u0645\u06cc \u06a9\u0646\u062f \u0648\u06af\u0631\u0646\u0647 \u062f\u0631 \u0633\u0637\u0631\u0647\u0627\u06cc\u06cc \u06a9\u0647 \u0645\u0631\u0628\u0639 \u0631\u0627 \u062d\u0631\u06a9\u062a \u0645\u06cc \u062f\u0627\u062f\u06cc\u0645 \u0647\u06cc\u0686 \u0633\u0631\u0628\u0627\u0632\u06cc \u0642\u0631\u0627\u0631 \u0646\u062f\u0627\u0634\u062a\u0647 \u0648 \u0627\u06cc\u0646 \u0628\u0627 \u0641\u0631\u0636 \u0645\u0633\u0627\u0644\u0647 \u062f\u0631 \u062a\u0646\u0627\u0642\u0636 \u0627\u0633\u062a.<\/p>\n\n\n\n

\u0627\u0628\u062a\u062f\u0627 \u0645\u0631\u0628\u0639\u200c\u0647\u0627\u06cc\u06cc \u0631\u0627 \u0686\u06a9 \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u06a9\u0647 \u0633\u0645\u062a \u0631\u0627\u0633\u062a \u0622\u0646 \u0647\u0627 \u0633\u0631\u0628\u0627\u0632\u06cc \u0628\u0627\u0634\u062f \u0648 \u0628\u0631\u0627\u06cc \u0633\u0645\u062a \u0686\u0628 \u0647\u0645 \u0645\u0634\u0627\u0628\u0647 \u0647\u0645\u06cc\u0646 \u06a9\u0627\u0631 \u0631\u0627 \u0627\u0646\u062c\u0627\u0645 \u0645\u06cc \u062f\u0647\u06cc\u0645.<\/p>\n\n\n\n

\u0627\u0632 \u0633\u0645\u062a \u0686\u0628 \u0628\u0647 \u0631\u0627\u0633\u062a \u0631\u0648\u06cc \u0633\u062a\u0648\u0646\u200c\u0647\u0627 \u062d\u0631\u06a9\u062a \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u0648 \u062f\u0631 \u0645\u0631\u062d\u0644\u0647 i \u0627\u0645 \u06cc\u06a9 set<\/span> \u062f\u0627\u0631\u06cc\u0645 \u06a9\u0647 \u062f\u0631 \u0622\u0646 p_{i-1},p_{i-2},...,p_{i-x}<\/span> \u0648\u062c\u0648\u062f \u062f\u0627\u0631\u062f. \u0645\u0633\u062a\u0637\u06cc\u0644\u06cc \u06a9\u0647 \u0639\u0631\u0636 \u0622\u0646 x<\/span> \u0627\u0633\u062a \u0648 \u0627\u0632 \u0633\u0645\u062a \u0631\u0627\u0633\u062a \u0628\u0647 \u0633\u0631\u0628\u0627\u0632 i<\/span> \u0627\u0645 \u0686\u0633\u0628\u06cc\u062f\u0647 \u062d\u062f\u0627\u06a9\u062b\u0631 \u0637\u0648\u0644\u06cc \u06a9\u0647 \u0645\u06cc \u062a\u0648\u0627\u0646\u062f \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f \u0628\u0631\u0627\u0628\u0631 A-B-1<\/span> \u0627\u0633\u062a \u06a9\u0647 A<\/span> \u06a9\u0648\u0686\u06a9\u062a\u0631\u06cc\u0646 \u0639\u0636\u0648 set<\/span> \u0627\u0633\u062a \u06a9\u0647 \u0627\u0632 p_i<\/span> \u0628\u0632\u0631\u06af\u062a\u0631 \u0627\u0633\u062a \u0648 B<\/span> \u0628\u0632\u0631\u06af\u062a\u0631\u06cc\u0646 \u0639\u0636\u0648 set<\/span> \u0627\u0633\u062a \u06a9\u0647 \u0627\u0632 p_i<\/span> \u06a9\u0648\u0686\u06a9\u062a\u0631 \u0627\u0633\u062a \u06a9\u0647 \u0627\u06cc\u0646 \u0627\u0639\u062f\u0627\u062f \u0631\u0627 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0627 O(nlog n)<\/span> \u0628\u0647 \u0648\u0633\u06cc\u0644\u0647 set<\/span> \u0628\u062f\u0633\u062a \u0622\u0648\u0631\u062f.\u0645\u0631\u0628\u0639\u06cc \u0628\u0647 \u0636\u0644\u0639 x<\/span> \u062f\u0627\u0631\u06cc\u0645 \u06a9\u0647 \u0627\u0632 \u0637\u0631\u0641 \u0631\u0627\u0633\u062a \u0628\u0647 \u0627\u06cc\u0646 \u0633\u0631\u0628\u0627\u0632 \u0686\u0633\u0628\u06cc\u062f\u0647 \u0627\u06af\u0631 \u0648 \u062a\u0646\u0647\u0627 \u0627\u06af\u0631 \u062d\u062f\u0627\u06a9\u062b\u0631 \u0637\u0648\u0644 \u0645\u0633\u062a\u0637\u06cc\u0644 \u0628\u06cc\u0634\u062a\u0631 \u0645\u0633\u0627\u0648\u06cc x<\/span> \u0628\u0627\u0634\u062f.<\/p>\n\n\n\n

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

\u06a9\u062f \u0631\u0627\u0647 \u062d\u0644<\/a><\/p>\n\n\n\n

\u0633\u0648\u0627\u0644 \u0641\u0631\u0627\u0631 \u0627\u0632 \u0632\u0646\u062f\u0627\u0646 :<\/b>
\u0628\u0631\u0627\u06cc \u0633\u0647\u0648\u0644\u062a \u062f\u0631 \u06a9\u0627\u0631 \u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f\u060c \u06af\u0631\u0627\u0641 \u0648\u0631\u0648\u062f\u06cc \u0647\u0645\u0628\u0646\u062f \u0627\u0633\u062a!<\/p>\n\n\n\n

\u0686\u0646\u0627\u0646\u0686\u0647 n<=20<\/span> \u0628\u0627\u0634\u062f\u060c \u062a\u0639\u062f\u0627\u062f \u062f\u0648\u0631\u200c\u0647\u0627\u06cc \u06af\u0631\u0627\u0641 \u0631\u0627 \u0628\u0627 \u0645\u062d\u0627\u0633\u0628\u0647 \u0627\u06cc\u0646 dp<\/span> \u0645\u06cc\u200c\u0634\u0645\u0627\u0631\u06cc\u0645.<\/p>\n\n\n\n

dp[i][mask]<\/span> : \u062a\u0639\u062f\u0627\u062f \u0645\u0633\u06cc\u0631\u200c\u0647\u0627\u06cc \u062f\u0631\u0648\u0646 \u06af\u0631\u0627\u0641\u060c \u06a9\u0647 \u0627\u0632 \u0645\u062c\u0645\u0648\u0639\u0647 \u0631\u0627\u0633\u200c\u0647\u0627\u06cc mask<\/span> \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u06a9\u0646\u062f\u060c \u0627\u0632 \u0631\u0627\u0633 i<\/span> \u0634\u0631\u0648\u0639 \u0634\u0648\u062f \u0648 \u0628\u0647 \u0631\u0627\u0633 lowbit(mask)<\/span> \u0645\u0646\u062a\u0647\u06cc \u0634\u0648\u062f .
\u0628\u0631\u0627\u06cc \u0622\u067e\u062f\u06cc\u062a \u06a9\u0631\u062f\u0646 \u0627\u06cc\u0646 dp<\/span> \u0645\u06cc \u062a\u0648\u0627\u0646 \u0631\u0627\u0633\u06cc \u06a9\u0647 \u062f\u0631\u0648\u0646 \u0645\u0633\u06cc\u0631 i<\/span> \u0628\u0647 \u0622\u0646 \u0648\u0635\u0644 \u0645\u06cc\u200c\u0634\u0648\u062f \u0631\u0627 \u0641\u06cc\u06a9\u0633 \u06a9\u0631\u062f \u0648 \u0645\u0642\u0627\u062f\u06cc\u0631 dp<\/span> \u0631\u0627 \u0645\u062d\u0627\u0633\u0628\u0647 \u06a9\u0631\u062f .
\u067e\u0633 \u0647\u0632\u06cc\u0646\u0647 \u0645\u062d\u0627\u0633\u0628\u0647 dp<\/span> \u0627\u0632 O(2^n*n)<\/span> \u0627\u0633\u062a .<\/p>\n\n\n\n

\u0633\u067e\u0633 \u0628\u0631\u0627\u06cc \u0634\u0645\u0631\u062f\u0646 \u062a\u0639\u062f\u0627\u062f \u062f\u0648\u0631\u0647\u200c\u0647\u0627 \u06a9\u0627\u0641\u06cc \u0627\u0633\u062a \u0628\u0631\u0627\u06cc \u0647\u0631 dp[i][mask]<\/span> \u060c \u0686\u0646\u0627\u0646\u0686\u0647 size(mask)<\/span> \u0628\u06cc\u0634\u062a\u0631 \u0645\u0633\u0627\u0648\u06cc \u06f3 \u0628\u0627\u0634\u062f \u0648 \u0631\u0627\u0633 \u0647\u0627\u06cc i<\/span> \u0648 lowbit(mask)<\/span> \u0628\u0647 \u06cc\u06a9\u062f\u06cc\u06af\u0631 \u06cc\u0627\u0644 \u062f\u0627\u0634\u062a\u0646\u062f \u062c\u0648\u0627\u0628 \u0631\u0627 \u0628\u0647 \u0627\u0646\u062f\u0627\u0632\u0647 dp<\/span> \u0627\u0636\u0627\u0641\u0647 \u06a9\u0646\u06cc\u0645.
\u062f\u0642\u062a \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u062f\u0631 \u0627\u06cc\u0646 \u0648\u0636\u0639\u06cc\u062a \u0647\u0631 \u062f\u0648\u0631 \u062f\u0631 \u06af\u0631\u0627\u0641 \u062f\u0642\u06cc\u0642\u0627 2 \u0628\u0627\u0631 \u0634\u0645\u0631\u062f\u0647 \u0645\u06cc\u200c\u0634\u0648\u062f ( \u0627\u0632 \u0637\u0631\u0641 \u06f2 \u06cc\u0627\u0644\u06cc \u06a9\u0647 \u0628\u0647 \u0631\u0627\u0633 \u0628\u0627 \u0627\u0646\u062f\u06cc\u0633 \u0645\u06cc\u0646\u06cc\u0645\u0645 \u0645\u062a\u0635\u0644 \u0645\u06cc\u200c\u0634\u0648\u0646\u062f) .<\/p>\n\n\n\n

\u0686\u0646\u0627\u0646\u0686\u0647 n>20<\/span> \u0628\u0627\u0634\u062f\u060c \u0628\u0627 \u0641\u0631\u0636 \u0647\u0645\u0628\u0646\u062f \u0628\u0648\u062f\u0646 \u06af\u0631\u0627\u0641\u060c \u06cc\u06a9 \u062f\u0631\u062e\u062a dfs<\/span> \u062f\u0644\u062e\u0648\u0627\u0647 \u0645\u062b\u0644 T<\/span> \u0627\u0632 \u06af\u0631\u0627\u0641 \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631\u0645\u06cc\u200c\u06af\u06cc\u0631\u06cc\u0645\u060c \u062a\u0639\u062f\u0627\u062f backedge<\/span> \u0647\u0627\u060c m-n+1<=20<\/span> \u0627\u0633\u062a. \u0645\u06cc\u200c\u062f\u0627\u0646\u06cc\u0645 \u0647\u0631 \u062f\u0648\u0631 \u062f\u0631 \u06af\u0631\u0627\u0641 \u0628\u0627\u06cc\u062f \u062a\u0639\u062f\u0627\u062f\u06cc \u0627\u0632 backedge<\/span> \u0647\u0627 \u0631\u0627 \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f.  \u0627\u06a9\u0646\u0648\u0646 \u0647\u0631 \u0632\u06cc\u0631\u0645\u062c\u0645\u0648\u0639\u0647 \u0627\u0632 backedge<\/span> \u0647\u0627 \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f\u060c \u06cc\u0627\u0644\u200c\u0647\u0627\u06cc\u06cc \u0627\u0632 \u062f\u0631\u062e\u062a \u06a9\u0647 \u0628\u0627\u06cc\u062f \u062f\u0631 \u062f\u0648\u0631\u06cc \u06a9\u0647 \u0634\u0627\u0645\u0644 \u0627\u06cc\u0646 backedge<\/span> \u0647\u0627\u0633\u062a \u0628\u06cc\u0627\u06cc\u0646\u062f \u0628\u0647 \u0635\u0648\u0631\u062a \u06cc\u06a9\u062a\u0627 \u0645\u0639\u06cc\u0646 \u0645\u06cc\u200c\u0634\u0648\u0646\u062f. \u0627\u06af\u0631 \u06cc\u0627\u0644\u06cc \u0645\u062b\u0644 e<\/span> \u0632\u06cc\u0631 \u0641\u0631\u062f \u062a\u0627 backedge<\/span> \u0628\u0627\u0634\u062f\u060c \u0628\u0627\u06cc\u062f \u0628\u06cc\u0627\u06cc\u062f \u0648 \u062f\u0631 \u063a\u06cc\u0631\u0627\u06cc\u0646\u200c\u0635\u0648\u0631\u062a \u0646\u0628\u0627\u06cc\u062f \u0628\u06cc\u0627\u06cc\u062f.<\/p>\n\n\n\n

\u0628\u0631\u0627\u06cc \u0627\u062b\u0628\u0627\u062a \u0627\u06cc\u0646 \u0645\u0648\u0636\u0648\u0639 \u06a9\u0627\u0641\u06cc \u0627\u0633\u062a T-e<\/span> \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f\u060c \u0686\u0648\u0646 \u0627\u06cc\u0646 \u06af\u0631\u0627\u0641 \u06f2 \u0645\u0648\u0644\u0641\u0647 \u0627\u0633\u062a\u060c \u0648 \u0645\u06cc \u0645\u06cc\u200c\u062e\u0648\u0627\u0647\u06cc\u0645 \u062f\u0648\u0631 \u0627\u0646\u062a\u062e\u0627\u0628 \u06a9\u0646\u06cc\u0645\u060c \u067e\u0633 \u0628\u0627\u06cc\u062f \u0632\u0648\u062c \u06cc\u0627\u0644 \u0628\u06cc\u0646 \u062f\u0648 \u0645\u0648\u0644\u0641\u0647 \u0628\u0627\u0634\u062f . \u067e\u0633 \u0648\u0636\u0639\u06cc\u062a \u06cc\u0627\u0644 e<\/span> \u0628\u0647 \u0634\u06a9\u0644 \u06cc\u06a9\u062a\u0627 \u0645\u0639\u06cc\u0646 \u0645\u06cc\u200c\u0634\u0648\u062f .
\u0627\u06a9\u0646\u0648\u0646 \u0628\u0631\u0627\u06cc \u0647\u0631 \u0632\u06cc\u0632\u0645\u062c\u0645\u0648\u0639\u0647 \u0648\u0636\u0639\u06cc\u062a \u0647\u0631 \u06cc\u0627\u0644 \u0631\u0627 \u062a\u0639\u06cc\u06cc\u0646 \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645 \u060c\u200c\u06a9\u0627\u0641\u06cc \u0627\u0633\u062a \u062f\u0631 \u0646\u0647\u0627\u06cc\u062a \u06cc\u0627\u0644\u200c\u0647\u0627\u06cc\u06cc \u06a9\u0647 \u062f\u0631 \u062f\u0648\u0631 \u0645\u06cc\u200c\u0622\u06cc\u0646\u062f \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u0645 \u0648 \u0628\u0628\u06cc\u0646\u06cc\u0645 \u0627\u06cc\u0646 \u06cc\u0627\u0644\u200c\u0647\u0627 \u062a\u0634\u06a9\u06cc\u0644 \u062f\u0648\u0631 \u0645\u06cc\u200c\u062f\u0647\u0646\u062f \u0648 \u062c\u0648\u0627\u0628 \u0631\u0627 \u0645\u062d\u0627\u0633\u0628\u0647 \u06a9\u0646\u06cc\u0645!
\u0627\u0631\u062f\u0631 \u0627\u06cc\u0646 \u0628\u062e\u0634 \u0627\u0632 \u0631\u0627\u0647\u200c\u062d\u0644 \u0646\u06cc\u0632 O(2^{m-n}*n)<\/span> \u0627\u0633\u062a!<\/p>\n\n\n\n

\u062f\u0631 \u0646\u0647\u0627\u06cc\u062a \u062a\u0648\u06a9 \u0627\u0632 \u0645\u0627 \u062e\u0648\u0627\u0633\u062a \u062f\u0631 \u062b\u0646\u0627\u06cc \u067e\u0648\u067e\u06a9 \u0627\u06cc\u0646 \u062a\u06a9\u0647 \u0634\u0639\u0631 \u0631\u0627 \u0627\u0636\u0627\u0641\u0647 \u06a9\u0646\u06cc\u0645!<\/p>\n\n\n\n

\u0633\u062d\u0631 \u0646\u062f\u0627\u0631\u062f \u0627\u06cc\u0646 \u0634\u0628\u200c\u062a\u0627\u0631…  \u0645\u0631\u0627 \u0628\u0647 \u062e\u0627\u0637\u0631\u062a \u0646\u06af\u0647 \u062f\u0627\u0631!<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"

\u0633\u0644\u0627\u0645!\u062f\u0631 \u0627\u06cc\u0646 \u0628\u0644\u0627\u06af \u0631\u0627\u0647\u200c\u062d\u0644 \u0633\u0648\u0627\u0644\u0627\u062a \u0645\u0633\u0627\u0628\u0642\u0647 \u0634\u0645\u0627\u0631\u0647 \u06f2\u06f3 \u0631\u0648 \u0628\u0647\u200c \u0635\u0648\u0631\u062a \u0641\u0634\u0631\u062f\u0647 \u0628\u06cc\u0627\u0646 \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645!<\/p>\n","protected":false},"author":6,"featured_media":32291,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[141,46,50],"tags":[],"class_list":["post-2408","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\/2408","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=2408"}],"version-history":[{"count":1,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts\/2408\/revisions"}],"predecessor-version":[{"id":32439,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts\/2408\/revisions\/32439"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/media\/32291"}],"wp:attachment":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/media?parent=2408"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/categories?post=2408"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/tags?post=2408"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}