…\u3002n \u4e2a\u70b9\u3002\u6bcf\u4e2a\u70b9\u968f\u673a\u5411\u67d0\u4e2a\u81ea\u5df1\u4ee5\u5916\u7684\u70b9\u8fde\u4e00\u6761\u8fb9\u3002\u3002
\n\u3002\u3002\u95ee\u5b58\u5728\u4e00\u4e2a k \u5143\u73af\u7684\u6982\u7387\u3002\u3002
\n\u3002\u3002(n, k = 10^7 \u3002\u3002\u3002\u3002
\n<\/p>\n
… \u6211\u662f\u50bb\u903c\u3002<\/p>\n
\u9996\u5148\u3002\u3002\u5982\u679c\u53ea\u6709\u4e00\u4e2a\u73af\u3002\uff08\u5f53 $$k >\\lfloor n\/2\\rfloor$$ \u65f6\u3002\u3002\u3002
\n\u3002\u3002\u7684\u65f6\u5019\u5f88\u597d\u89e3\u51b3\u3002\u3002\u5c31\u662f\u3002\u3002<\/p>\n
$$!\\binom{n}{k}(k-1)!(n-1)^{n-k}$$<\/p>\n
\u3002\u3002\u5982\u679c\u4e0d\u6b62\u6709\u4e00\u4e2a\u73af\u3002\u3002\u90a3\u4e48\u5bf9\u4efb\u610f\u4e00\u4e2a\u542b\u6709 $$i$$ \u4e2a\u73af\u7684\u89e3\u3002\u3002\u4e0a\u9762\u7684\u516c\u5f0f\u4f1a\u8ba1\u6570 $$\\binom{i}{1}$$ \u6b21\u3002
\n\u3002\u3002\u81f3\u6b64\u5bb9\u65a5\u539f\u7406\u5c31\u5f88\u660e\u663e\u4e86\u3002<\/p>\n
\u3002\u518d\u8003\u8651\u4e24\u4e2a\u73af\u7684\u60c5\u51b5\u3002\u3002\u3002<\/p>\n
$$!\\binom{n}{k}\\binom{n-k}{k}\\frac{(k-1)!^2}{2!}(n-1)^{n-2k}$$
\n\u3002\u3002\u6ce8\u610f\u9664\u4ee5 $$2! $$ \u56e0\u4e3a\u4e00\u7ec4\u542b\u6709 $$i$$ \u4e2a\u73af\u7684\u65b9\u6848\u4f1a\u88ab\u8ba1\u6570 $$i! $$ \u3002\u3002\uff08\u6211\u4e00\u5f00\u59cb\u5c11\u4e86\u8fd9\u4e2a WA \u6210\u72d7\u3002\u3002\u3001\u3001\u3002<\/p>\n
\u3002\u3002\u6211\u4eec\u987a\u4fbf\u628a\u603b\u7684\u65b9\u6848\u6570 $$(n-1)^n$$ \u8003\u8651\u8fdb\u53bb\u3002\u3002\u4e00\u822c\u7684\u3002\u3002\u6709\u3002\u3002\u3002\u3002<\/p>\n
$$!\\frac{n!(k-1)!^i(n-1)^{n-ik}}{(n-ik)!i!k!^i(n-1)^n}$$<\/p>\n
\u3002\u3002\u5316\u7b80\u4ee5\u540e\u5f97\u3002\u3002\u3002<\/p>\n
$$!\\frac{n!}{(n-ik)!i!k^i(n-1)^{ik}}$$<\/p>\n
\u3002\u3002\u4f46\u662f\u8fd9\u6837\u76f4\u63a5\u7b97\u9636\u4e58\u7cbe\u5ea6\u4e0a\u4f1a\u8dea\u3002\u3002\u3002(\u4ef0\u6155\u6838\u6b66\uff01\u3002
\n\u3002\u3002\u3002\u8bbe $$A_i$$ \u8868\u793a\u6709 $$i $$ \u4e2a\u73af\u65f6\u7684\u542b\u91cd\u65b9\u6848\u6570\u3002\u3002\u3002
\n\u3002\u3002\u3002\u3002\u518d\u628a\u9012\u63a8\u5f0f\u641e\u51fa\u6765\u5c31\u884c\u4e86\u3002\u3002\u3002\u3002<\/p>\n
$$!A_n=\\begin{cases}\\qquad\\qquad 1 &n=0\\\\ \\\\ \\\\ \\frac{\\prod_{t=n-ik+1}^{n-(i-1)k}A_{n-1}}{ik(n-1)^k} &n \\geq 1\\end{cases}$$<\/p>\n
\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 10000009;\r\n\r\nDB f(){\r\n int n, k; RD(n, k); DB res = 0, cur = 1; int t = n; REP_1_C(i, n\/k){\r\n cur \/= i*k; DWN_1_C_N(t, t, t-k+1) cur *= (DB)t\/(n-1);\r\n if (i&1) res += cur; else res -= cur;\r\n }\r\n return res;\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n \/\/freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n Rush OT(f());\r\n}\r\n<\/pre>\n