给定x,求\(a_1+a_2+...+a_k=x^x\ mod\ 1000\)的正整数解解的组数,对于100%的数据,k≤100,x≤2^31-1。
解
显然x是可以快速幂得到答案的,而该问题显然是组合计数的问题,换一种解释即\(b=x^x\)个相同的数能怎样放进k个有标号盒子。
思路一
而无法解决无标号放入有标号。于是逆向思维,把有标号盒子放入无标号\(b\)个数,有标号盒子可以重复放,无标号$b数个只能被放一次,因为是正整数的缘故,所以盒子必须保证放过,故事先构造放满,再套用可重组合公式,有
\[C_{k+b-k-1}^{k-1}=C_{b-1}^{k-1}\]思路二
注意到组合问题很难解决,故考虑排列,而这又是划分问题,故考虑全排列划分模型,即有k-1个0与b个1进行全排列,0去划分1,但是注意到要的是正整数解,于是0之间必须有1,于是事先填好1,有
\[\frac{(k-1+b-k)!}{(k-1)!(b-k)!}=C_{b-1}^{k-1}\]得到公式后根据所得条件按质因数分解型的阶乘高精处理即可。
参考代码:
#include#include #include #define il inline#define ri register#define yyb 1000using namespace std;struct lll{ short num[5000]; il lll(){num[0]=1;} il void clear(){memset(num,0,sizeof(num)),num[0]|=true;} template il void operator=(free x){ num[0]=0; while(x)num[++num[0]]=x%10,x/=10; } il lll operator*(lll x){ lll y;y.clear(); for(ri int i(1),j,k;i<=num[0];++i){ k=0; for(j=1;j<=x.num[0];++j) y.num[i+j-1]+=num[i]*x.num[j]+k, k=y.num[i+j-1]/10,y.num[i+j-1]%=10; y.num[i+x.num[0]]+=k; }y.num[0]=num[0]+x.num[0]; while(!(y.num[y.num[0]])&&y.num[0]>1)--y.num[0]; return y; }template il lll operator^(free y){ lll x(*this),ans;ans=1; while(y){ if(y&1)ans=ans*x; x=x*x,y>>=1; }return ans; } il void print(){ for(ri int i(num[0]);i;--i)putchar(num[i]+48); }};lll xdk[250];bool check[1100];int prime[250],sp[250],tot;il int pow(int,int);il void c(int,int),sieve(int);int main(){ int k,x; scanf("%d%d",&k,&x),x=pow(x%yyb,x); sieve(x-1),c(x-1,k-1); return 0;}il void sieve(int n){ for(ri int i(2),j;i<=n;++i){ if(!check[i])prime[++tot]=i,xdk[tot]=i; for(j=1;j<=tot&&prime[j]*i<=n;++j){ check[i*prime[j]]|=true; if(!(i%prime[j]))break; } }}il void c(int n,int r){ if(n >=1; }return ans;}