前言

不知道为什么 \(Yang Hui\) 会变成 \(Yang Yui\)？就很棒

Description

洛谷翻译

Solution

我们设：

\[n = a[k]*p^k + a[k-1]*p^{k-1} + … + a[1]*p + a[0]
\]

\[m = b[k]*p^k + b[k-1]*p^{k-1} + … + b[1]*p + b[0]
\]

所以，

\[C(n,m)\%p=\prod_{i=0}^kC(a[i],b[i])\%p
\]

由于 a，b 数组是 \(p^i\) 前的系数，所以对于任意 i，都有 \(a[i]。

又因为 p 是质数，所以无论 \(a[i]!\)，\(b[i]!\)，\((a[i]-b[i])!\) 都不能被 p 整除，所以 \(C(a[i],b[i])\) 不会被 p 整除。（后面讲反例）

\(a[i]\) 是已知的，而 \(b[i]\) 唯一的范围就是 \(b[i]<=a[i]\)，不然结果就是 0。

Code

#include
typedef long long ll;
ll p = 10000, mod;
int read() {
int x = 0, f = 1; char s;
while((s = getchar()) > ‘9‘ || s <‘0‘) if(s == ‘-‘) f = -1;
while(s <= ‘9‘ && s >= ‘0‘) {
x = (x <<1) + (x <<3) + (s ^ 48);
s = getchar();
}
return x * f;
}
int main() {
int ans, n;
for(int T = 1; ; ++ T) {
mod = read(), n = read();
if(! n && (! mod)) break;
ans = 1;
while(n) {
ans = (ans * (n % mod + 1)) % p;
n /= mod;
}
printf("Case %d: %04d\n", T, ans);
}
return 0;
}