\u9996\u5148\u7ed9\u51fa\u5173\u4e8eLucas\u5b9a\u7406\u7684\u7b80\u8981\u8bc1\u660e\uff1a
\n\u5b9a\u4e49\uff1a
\n$$ a=a_{k}*p^{k}+a_{k-1}*p^{k-1}+…+a_{1}*p+a_{0}=\\sum_{i=1}^{k}a_{i}^p{i} $$
\n$$ b=b_{k}*p^{k}+b_{k-1}*b^{k-1}+…+b_{1}*p+b_{0}=\\sum_{i=1}^{k}b_{i}^p{i} $$
\n\u6c42\u8bc1\uff1a
\n$$ C_{a}^{b}=C_{a_{k}}^{b_{k}}*C_{a_{k-1}}^{b_{k-1}}…C_{a_{0}}^{b_{0}} $$<\/p>\n
\u9996\u5148\u6211\u4eec\u8bc1\u660e\u5f15\u7406\u4e00\uff1a
\n$$ (1+x)^p\u22611+x^p\\ (mod\\ p) $$
\n\u6839\u636e\u7ec4\u5408\u6570\u57fa\u672c\u6027\u8d28\uff0c\u6211\u4eec\u6709\uff1a
\n$$\\forall j\\in [1,p-1],C_{p}^{j}=\\frac{p}{j}*C_{p-1}^{j-1}\u22610(mod\\ p) $$<\/p>\n
$$\u2234(1+x)^p\u2261\\sum_{i=1}^{p}C_{p}^{i}*x^i\u22611+x^p(mod\\ p) $$
\n\u4e8e\u662f\u6211\u4eec\u5f97\u5230\u7ed3\u8bba\uff1a
\n$$(1+x)^a\u2261\\prod_{i=1}^{k}(1+x)^{p^k*a_{k}}\u2261\\prod_{i=1}^{k}(1+x^{p^{k}})^{a_{k}}(mod\\ p)\\ (1)$$
\n\u6839\u636e\u8fdb\u5236\u7684\u57fa\u672c\u6027\u8d28\u548c\u5e42\u7684\u57fa\u672c\u6027\u8d28\uff0c\u6211\u4eec\u6709\uff1a
\n$$b=\\sum_{i=1}^{k}b_{i}^p{i},x^b=\\prod_{i=1}^{k}x^{p^k*b_{i}}$$
\n\u5e76\u4e14\u6211\u4eec\u77e5\u9053\uff0c\u7528\u4e0a\u8ff0\u65b9\u6cd5\u8868\u793a\\(p\\)\u8fdb\u5236\u6570\uff0c\u662f\u5b8c\u5168\u7b49\u4ef7\u7684\u3002\u5373\uff0c\u4e24\u8005\u7684\u96c6\u5408\u6784\u6210\u53cc\u5c04\u3002<\/p>\n
\u6545\u800c\u6211\u4eec\u6bd4\u8f83\\((1)\\)\u5f0f\u5c55\u5f00\u540e\u5de6\u53f3\u5404\u9879\uff0c\u53ef\u4ee5\u5f97\u5230\uff1a
\n$$\\forall b\\in [1,a],C_{a}^{b}\u2261\\prod_{i=1}^{k}C_{a_{i}}^{b_{i}}(mod\\ p)$$<\/p>\n
\u8bc1\u6bd5\u3002<\/p>\n
\u6545\u800c\u5bf9\u4e8e\u5b9e\u9645\u5904\u7406\u95ee\u9898\uff0c\u53ea\u9700\u8981\u9006\u5411\u79e6\u4e5d\u97f6\u5373\u53ef\u3002<\/p>\n
<\/p>\n
#include<iostream>\r\n#include<cstdio>\r\nusing namespace std;\r\nlong long n,m,p,inv[100005],fac[100005];\r\n#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))\r\n#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))\r\n\r\n\/\/y\u53d6x \r\ninline long long C0(long long x,long long y){\r\n return ((x>y)?0:(x?fac[y]*inv[x]*inv[y-x]%p:1))%p;\r\n}\r\n\/\/\u6a21p\u610f\u4e49\u4e0b\u7684y\u53d6x \r\ninline long long C(long long x,long long y){\r\n return ((x>y)?0:((y>=p)?C(x\/p,y\/p)*C0(x%p,y%p):C0(x%p,y%p)))%p;\r\n}\r\nvoid init(){\r\n scanf(\"%lld%lld%lld\",&n,&m,&p);\r\n fac[0]=fac[1]=inv[0]=inv[1]=1;\r\n for(int i=2;i<=p;++i){\r\n fac[i]=fac[i-1]*i%p;\r\n inv[i]=(p-p\/i)*inv[p%i]%p;\r\n }\r\n for(int i=2;i<=p;++i){\r\n inv[i]*=inv[i-1];\r\n inv[i]%=p;\r\n }\r\n printf(\"%lld\\n\",C(n,n+m)%p);\r\n} \r\nint main(){\r\n int T;\r\n scanf(\"%d\",&T);\r\n while(T--){\r\n init();\r\n }\r\n return 0;\r\n}<\/code><\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
\u9996\u5148\u7ed9\u51fa\u5173\u4e8eLucas\u5b9a\u7406\u7684\u7b80\u8981\u8bc1\u660e\uff1a \u5b9a\u4e49\uff1a $$ a=a_{k}*p^{k}+a_{k-1}*p^{k-1 … <\/p>\n