- #include#define EXint __uint128_t
- EXint n,
- k,
- p,
- tmp[3001],
- ans;
- inline EXint READ() {
- char ch = getchar();
- EXint ret = 0;
- while (ch < '0' || ch > '9') ch = getchar();
- while (ch >= '0' && ch <= '9') {
- ret *= 10;
- ret += ch - '0';
- ch = getchar();
- }
- return (ret);
- }
- inline void WRITE(EXint a) {
- int cnt = 0,
- typ[101];
- while (a) typ[++cnt] = a % 10,
- a /= 10;
- for (int i = cnt; i >= 1; i--) putchar(typ[i] + '0');
- }
- struct poly {
- EXint a[3001];
- void mul(poly & b) {
- for (int i = 0; i <= 2 * k - 2; i++) tmp[i] = 0;
- for (int i = 0; i <= k - 1; i++) for (int j = 0; j <= k - 1; j++) tmp[i + j] += a[i] * b.a[j];
- //对特征多项式取模
- for (int i = 2 * k - 2; i >= k; i--) {
- tmp[i - k] += tmp[i];
- tmp[i - k + 1] += tmp[i];
- }
- for (int i = k - 1; i >= 0; i--) a[i] = tmp[i];
- }
- }
- bas,
- res;
- int main() {
- n = READ();
- k = READ();
- p = READ();
- bas.a[1] = 1;
- res.a[0] = 1;
- while (n) {
- if (n & (EXint) 1) res.mul(bas);
- bas.mul(bas);
- n = n >> 1;
- }
- for (int i = 0; ires.a[i]; //若0-k-1的初始值不为1则乘权值
- if (p != 128) ans &= ((((EXint) 1) < 1); WRITE(ans);
- }
来源: http://www.bubuko.com/infodetail-1985940.html