[洛谷P1771] 方程的解

题目

题目描述

佳佳碰到了一个难题,请你来帮忙解决。

对于不定方程a1+a2+…+ak-1+ak=g(x),其中k≥2且k∈N,x是正整数,g(x)=x^x mod 1000(即x^x除以1000的余数),x,k是给定的数。我们要求的是这个不定方程的正整数解组数。

举例来说,当k=3,x=2时,分别为(a1,a2,a3)=(2,1,1)'(1,2,1),(1,1,2)。

输入格式

输入文件equation.in有且只有一行,为用空格隔开的两个正整数,依次为k,x。

输出格式

输出文件equation.out有且只有一行,为方程的正整数解组数。

输入样例

输出样例

说明

对于40%的数据,ans≤10^16;对于100%的数据,k≤100,x≤2^31-1,k≤g(x)。

题解

首先呢,\(g(x)\)我们是可以求解的,我们设\(n=g(x)\)
我们可以先写出\(n\)个1,我们发现它们之间有\(n-1\)个空隙,而我们的任务是寻找k个数,使k个数的和等于\(n\),于是我们就可以将问题转化成在\(n-1\)个空隙中选出\(k-1\)个空隙放挡板,形成的\(k\)个数的和正好就是\(n\)。
换句话说,我们要求\(C_{n-1}^{k-1}\)
对于样例的画图辅助理解

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注