题目名称	604. 方程
输入输出	`equationz.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	cqw 于2011-11-04加入
开放分组	全部用户
提交状态
分类标签	动态规划快速幂排列组合
	分享题解

通过：60，提交：240，通过率：25%
苏轼	100	0.002 s	0.17 MiB	Pascal
正确率超低的渣渣	100	0.002 s	13.88 MiB	Pascal
Ezoi_XY	100	0.003 s	0.15 MiB	Pascal
mildark	100	0.003 s	0.32 MiB	C++
cstdio	100	0.003 s	0.32 MiB	C++
阿狸	100	0.014 s	0.33 MiB	C++
lingyixiaoyao	100	0.015 s	0.25 MiB	C++
旋转华尔兹	100	0.025 s	0.37 MiB	C++
绕着指尖	100	0.031 s	0.31 MiB	C++
筽邝	100	0.051 s	0.32 MiB	Pascal

本题关联比赛
20111104
20111104

关于方程的近10条评论(全部评论)
不用压位也能水过.. nancheng58 2016-11-17 18:35 8楼
就是C(k-1，g(x)-1)。。马克之 HouJikan 2014-08-22 21:35 7楼
@zjmfrank2012 怎么这么快就过了 , 2013-11-03 20:31 6楼
@zjmfrank2012 一开始没想到，蛤蛤 cstdio 2013-11-02 21:49 5楼
可以滚动数组啊@神马之云cstdio zjmfrank2012 2013-11-02 19:50 4楼
原来以为n^2递推会爆M，现在发现也可以，亿进制这样的高精度写错了……写错的原因是前一段用一个有相同错误的高精过了一道题…… 这都啥世道(╯‵□′)╯︵┻━┻ cstdio 2013-11-02 18:28 3楼
我去算法被压制了@1846834 zjmfrank2012 2013-11-02 18:11 2楼
提供一个小发现：（本题用此方法全部正确） pow(x,x)%moder==pow(x%moder,x%moder) 其实正规的算法应该是快速幂。（自己也不会） n^m=n^(2^x1)n^(2^x2)...n^(2^xn) 其中m=2^x1+2^x2+...+2^xn 例： 5^9=5^85^05^05^1 然后一个高精度加法，数值递推（推出来后是一个杨辉三角），我用的是十亿进制搞定。 Truth.Cirno 2011-11-08 17:50 1楼

604. 方程

★☆ 输入文件：equationz.in 输出文件：equationz.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

hyc 碰到了一个难题，请你来帮忙解决。

对于不定方程a1+a2+a3+……+ak=g(x) ，其中K.>=2,k是正整数 , x 是正整数 ,

g(x)=x^x mod 1000 , x,k 是给定的数 . 我们要求的是这个不定方程的正整数解组数 .

举例来说 , 当 k=3,x=2 时 ,g(x)=4, 原方程即 A1+A2+A3=4 .

这个方程的正整数解有 3 组 . 分别为 (A1,A2,A3) = （2，1，1），（1，2，1），（1，1，2）.

【输入文件】

有且只有一行 . 为用空格隔开的两个正整数 , 依次为 k,x.

【输出文件】

有且只有一行 , 为方程的正整数解组数 .

【样例输入】

3 2

【样例输出】

3

【数据范围】

对于 40% 的数据 , ans<= 10^16 ;

对于 100% 的数据 , k<=100 , x<= 2^31-1 ,k<=g(x)。