#P2629. binomial

    ID: 1684 传统题 1000ms 512MiB 尝试: 128 已通过: 33 难度: 8 上传者: 标签>CF2500提高+/省选-Lucas 定理阶乘逆元预处理原根卷积转化NTT补集计数进位制转换高精度除法

binomial

题目描述

对于给定的 nn 和 pp,求对于所有的0≤i<p0 \leq i < p ,满足 (nk) mod p=i\dbinom n k\bmod p = i 的 kk 的个数。

输入格式

仅一行包含两个正整数 nn 和 pp。

输出格式

仅一行,为一个长度为 pp 的字符串 ss,sis_i 表示满足 (nk) mod p=i\dbinom n k\bmod p = i 的 kk 的个数除以 2929 后的余数,sis_i 视为一个 2929 进制的数字。

20 4
D440

数据规模与约定

对于 100%100\% 的数据,n<p10n < p^{10},p=51061p=51061。