1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/*
Copyright (C) 2011, 2021 Fredrik Johansson
This file is part of FLINT.
FLINT is free software: you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License (LGPL) as published
by the Free Software Foundation; either version 3 of the License, or
(at your option) any later version. See <https://www.gnu.org/licenses/>.
*/
#include "nmod.h"
#include "nmod_vec.h"
#include "nmod_poly.h"
#include "arith.h"
#include "arith/impl.h"
ulong nmod_inv_check(ulong x, nmod_t mod)
{
ulong r, g;
g = n_gcdinv(&r, x, mod.n);
if (g != 1)
return mod.n;
return r;
}
int
arith_bell_number_nmod_vec_series(nn_ptr res, slong n, nmod_t mod)
{
ulong c;
nn_ptr tmp;
slong k;
int success;
if (n <= 0)
return 1;
if (mod.n == 1)
return 0;
tmp = flint_malloc(sizeof(ulong) * n);
/* Compute inverse factorials */
c = 1;
if (NMOD_BITS(mod) == FLINT_BITS)
{
for (k = n - 1; k > 0; k--)
{
tmp[k] = c;
c = _nmod_mul_fullword(c, k, mod);
}
}
else
{
for (k = n - 1; k > 0; k--)
{
tmp[k] = c;
c = nmod_ui_mul_ui(c, k, mod);
}
}
c = nmod_inv_check(c, mod);
success = (c != mod.n);
if (success)
{
tmp[0] = 0;
_nmod_vec_scalar_mul_nmod(tmp + 1, tmp + 1, n - 1, c, mod);
_nmod_poly_exp_series(res, tmp, n, n, mod);
/* Multiply by factorials */
c = 1;
if (NMOD_BITS(mod) == FLINT_BITS)
{
for (k = 1; k < n; k++)
{
c = _nmod_mul_fullword(c, k, mod);
res[k] = _nmod_mul_fullword(res[k], c, mod);
}
}
else
{
for (k = 1; k < n; k++)
{
c = nmod_mul(c, k, mod);
res[k] = nmod_mul(res[k], c, mod);
}
}
}
flint_free(tmp);
return success;
}