\u7b2c\u4e8c\u7c7b\u65af\u7279\u6797\u6570\uff0c\u6307\u7684\u662f\u4e00\u7ec4\u8868\u793a\u300c\u5c06n\u4e2a\u4e0d\u540c\u7684\u5143\u7d20\u5212\u5206\u4e3am\u4e2a\u975e\u7a7a\u4e0d\u76f8\u4ea4\u96c6\u7684\u65b9\u6848\u6570\u300d\u7684\u7ec4\u5408\u6570\u3002\u6709\u65f6\u5199\u4f5c\\(S(n,m)\\)\u6216\\(\\left\\{\\begin{matrix}n\\\\m\\end{matrix}\\right\\}\\)
\u4ece\u9898\u610f\u6765\u770b\uff0c\u6211\u4eec\u53ef\u4ee5\u5bb9\u6613\u5730\u60f3\u5230\u4e00\u4e2a\u9012\u63a8\u65b9\u6848\uff1a\u6bcf\u4e2a\u65b0\u7684\u5143\u7d20\uff0c\u53ef\u4ee5\u4e3a\u5b83\u65b0\u5f00\u4e00\u4e2a\u96c6\u5408\uff0c\u6216\u8005\u653e\u5230\u5df2\u6709\u7684\u4efb\u4f55\u4e00\u4e2a\u96c6\u5408\u91cc\u9762\u3002\u6240\u4ee5\u6211\u4eec\u5f97\u5230\u4e00\u4e2a\u9012\u63a8\u5f0f\uff1a
$$S(n,m)=S(n-1,m-1)+m*S(n-1,m)$$
\u7136\u540e\u95ee\u9898\u662f\u600e\u4e48\u6c42\u503c\u3002<\/p>\n\n\n\n
\u9996\u5148\u6211\u4eec\u6709\u4e00\u4e2a\u5f0f\u5b50\uff0c\u6211\u4eec\u79f0\u4e4b\u4e3a\u4e8c\u9879\u5f0f\u53cd\u6f14\u7684\u901a\u9879\u5f0f\u3002
$$ f(n)=\\sum_{i=0}^nC_{n}^{i}g(n) \\Leftrightarrow g(n)=\\sum_{i=0}^n(-1)^{n-i}C_{i}{n}f(n)$$
\u4e3e\u4e2a\u4f8b\u5b50\uff1a
$$\\begin{matrix} f_{1}&=&g_{1}\\\\f_{2}&=&g_{1}&+&g_{2}\\\\f_{3}&=&g_{1}&+&2*g_{2}&+&g_{3}\\\\f_{4}&=&g_{1}&+&3*g_{2}&+&3*g_{3}&+&g_{4} \\end{matrix}$$<\/p>\n\n\n\n
\u7531\u6b64\u53ef\u5f97\uff1a <\/p>\n\n\n\n
$$\\begin{matrix} g_{1}&=&f_{1}\\\\g_{2}&=&f_{2}&-&f_{1}\\\\g_{3}&=&f_{3}&-&2*g_{2}&-&g_{1}\\\\&=&f_{3}&-&2*f_{2}&+&f_{1}\\\\g_{4}&=&f_{4}&-&3*g_{3}&-&3*g_{2}&-&g_{1}\\\\&=&f_{4}&-&3*f_{3}&-&3*g_{2}&-&4*g_{1}\\\\&=&f_{4}&-&3*f_{3}&+&3*f_{2}&-&f_{1} \\end{matrix}$$<\/p>\n\n\n\n
\u7136\u540e\u6211\u4eec\u8003\u8651\\(m^n\\)\u7684\u7ec4\u5408\u610f\u4e49\uff0c\u4e5f\u5c31\u662f\uff0c\u5c06\\(n\\)\u4e2a\u4e0d\u540c\u7684\u7403\uff0c\u653e\u5230\\(m\\)\u4e2a\u4e0d\u540c\u7684\u76d2\u5b50\uff08\u53ef\u4ee5\u6709\u7a7a\u76d2\uff09\u7684\u65b9\u6848\u6570\u3002 \u7b2c\u4e8c\u7c7b\u65af\u7279\u6797\u6570\uff0c\u6307\u7684\u662f\u4e00\u7ec4\u8868\u793a\u300c\u5c06n\u4e2a\u4e0d\u540c\u7684\u5143\u7d20\u5212\u5206\u4e3am\u4e2a\u975e\u7a7a\u4e0d\u76f8\u4ea4\u96c6\u7684\u65b9\u6848\u6570\u300d\u7684\u7ec4\u5408\u6570\u3002\u6709\u65f6\u5199\u4f5c\\(S(n, … <\/p>\n
\u6211\u4eec\u4e0d\u59a8\u679a\u4e3e\u6709\u88c5\u4e1c\u897f\u7684\u76d2\u5b50\u7684\u4e2a\u6570\u3002\u4ee4\u5b83\u4e3a\\(i\\)\uff0c\u90a3\u4e48\u9009\u53d6\u8fd9\u4e9b\u76d2\u5b50\u7684\u65b9\u6848\u6570\u5373\u662f\\(C_{m}^{i}\\)\u3002
\u9009\u53d6\u4e86\u76d2\u5b50\u4e4b\u540e\uff0c\u95ee\u9898\u5c31\u8f6c\u5316\u4e3a\u4e86\u5c06\\(n\\)\u4e2a\u4e0d\u540c\u7269\u54c1\u88c5\u5230\\(m\\)\u4e2a\u4e0d\u540c\u76d2\u5b50\u91cc\uff0c\u4f7f\u5f97\u6bcf\u4e2a\u76d2\u5b50\u975e\u7a7a\u3002\u8fd9\u5c31\u76f8\u5f53\u4e8e\uff0c\u5c06\\(n\\)\u4e2a\u4e0d\u540c\u7269\u54c1\u88c5\u5230\\(m\\)\u4e2a\u76f8\u540c\u76d2\u5b50\u91cc\uff0c\u4f7f\u5f97\u6bcf\u4e2a\u76d2\u5b50\u975e\u7a7a\u7684\u65b9\u5f0f\u2014\u2014\u4e5f\u5c31\u662f\\(S(n,m)\\)\uff0c\u4e58\u4e0a\u76d2\u5b50\u7684\u6392\u5217\u987a\u5e8f\u2014\u2014\u4e5f\u5c31\u662f\\(m!\\)\u3002
\u5f62\u5f0f\u5316\u7684\u8bf4\uff0c\u5c31\u662f\uff1a
$$m^n=\\sum_{i=0}^{m}S(n,i)i!C_{m}^{i}$$
\u6211\u4eec\u53d1\u73b0\u8fd9\u4e2a\u5f0f\u5b50\u7684\u5f62\u5f0f\u7b26\u5408\u4e8c\u9879\u5f0f\u53cd\u6f14\u7684\u901a\u9879\u5f0f\u3002
\u56e0\u800c\u6211\u4eec\u5c06\\(m^n\\)\u4f5c\u4e3a\\(f\\)\uff0c\u5c06\\(S(n,i)i!\\)\u4f5c\u4e3a\\(g\\)\u3002
\u90a3\u4e48\u53cd\u6f14\u5f97\u5230\uff1a
$$S(n,m)=\\frac{1}{m!}\\sum_{i=0}^{m}(-1)^{m-i}i^nC_{m}^{i}$$
\u8003\u8651\\(C_{m}^{i}=\\frac{m!}{i!(m-i)!}\\)\uff0c\u6211\u4eec\u53ef\u4ee5\u5c06\u4e0a\u5f0f\u5316\u7b80\u5f97\u5230\uff1a
$$S(n,m)=\\sum_{i=0}^{m}\\frac{(-1)^{m-i}i^n}{i!(m-i)!}$$
\u4e8e\u662f\u6211\u4eec\u6709\uff1a
$$\\left\\{\\begin{matrix}n\\\\m\\end{matrix}\\right\\}=\\sum_{i=0}^{m}\\frac{(-1)^{m-i}i^n}{i!(m-i)!}$$
\u8003\u8651\u51fd\u6570\u5377\u79ef\u7684\u672c\u8d28\uff0c\u5bf9\u4e8e\u5377\u79ef\\(f=gu\\)\uff0c\u5176\u672c\u8d28\u662f\uff1a <\/em>$$f(n)=\\sum_{i=0}^{n}g(i)u(n-i)$$ \u56e0\u800c\uff0c\u6211\u4eec\u53d1\u73b0\uff0c\u4e0a\u5f0f\u672c\u8d28\u4e0a\u5c31\u662f\uff1a $$\\left\\{\\begin{matrix}n\\\\m\\end{matrix}\\right\\}=\\sum_{i=0}^{m}\\frac{(-1)^{m-i}}{(m-i)!}*\\frac{i^n}{i!}$$
\u4e0a\u4e00\u4e2aNTT\u5377\u79ef\u4e00\u4e0b\u5c31\u597d\u4e86\u3002<\/p>\n\n\n\n#include<iostream>\n#include<cstdio>\n\n#define Swap(A,B) (A^=B^=A^=B)\nconst long long P=167772161;\nconst long long g0=3,gi=55924054;\nint L=1,R[1<<21|1];\nlong long invL;\ninline int pw(int A,int X){\n\tlong long BS=A,RT=1;\n\twhile(X){\n\t\tif(X&1){\n\t\t\tRT=RT*BS%P;\n\t\t}\n\t\tBS=BS*BS%P;\n\t\tX>>=1;\n\t}\n\treturn RT;\n}\ninline void prpr(int LEN){\n\tint B=0;\n\twhile(L<=LEN){\n\t\tL<<=1;\n\t\t++B;\n\t}\n\tinvL=P-(P-1)\/L;\n\tfor(int i=0;i<L;++i){\n\t\tR[i]=R[i>>1]>>1|(i&1)<<(B-1);\n\t}\n}\ninline void FNTT(int *A,int typ){\n\tfor(int i=0;i<L;++i){\n\t\tif(R[i]<i){\n\t\t\tSwap(A[R[i]],A[i]);\n\t\t}\n\t}\n\tint gn,g,X,Y,M;\n\tfor(int i=2;i<=L;i<<=1){\n\t\tM=i>>1;\n\t\tgn=pw(~typ?g0:gi,(P-1)\/i);\n\t\tfor(int j=0;j<L;j+=i){\n\t\t\tg=1;\n\t\t\tfor(int k=0;k<M;++k,g=1ll*g*gn%P){\n\t\t\t\tX=A[j+k],Y=1ll*g*A[M+j+k]%P;\n\t\t\t\tA[j+k]=(X+Y)%P,A[M+j+k]=(X-Y)%P;\n\t\t\t}\n\t\t}\n\t}\n}\nint n,a[1<<21|1],b[1<<21|1],inv[1<<21|1];\nvoid init(){\n\tscanf(\"%d\",&n);\n\tprpr(n+1<<1);\n\tinv[0]=inv[1]=1;\n\tfor(int i=2;i<=n;++i){\n\t\tinv[i]=1ll*(P-P\/i)*inv[P%i]%P;\n\t}\n\tfor(int i=1;i<=n;++i){\n\t\tinv[i]=1ll*inv[i-1]*inv[i]%P;\n\t}\n\tfor(int i=0;i<=n;++i){\n\t\ta[i]=1ll*pw(-1,i)*inv[i]%P;\n\t\tb[i]=1ll*pw(i,n)*inv[i]%P;\n\t}\n\tFNTT(a,1);\n\tFNTT(b,1);\n\tfor(int i=0;i<L;++i){\n\t\ta[i]=1ll*a[i]*b[i]%P;\n\t}\n\tFNTT(a,-1);\n\tfor(int i=0;i<=n;++i){\n\t\tprintf(\"%d \",1ll*(a[i]+P)*invL%P);\n\t}\n}\n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"