?組合數取模? 1 - 1e18

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; typedef long long LL;LL n,m,p;LL quick_mod(LL a, LL b) {LL ans = 1;a %= p;while(b){if(b & 1){ans = ans * a % p;b--;}b >>= 1;a = a * a % p;}return ans; }LL C(LL n, LL m) {if(m > n) return 0;LL ans = 1;for(int i=1; i<=m; i++){LL a = (n + i - m) % p;LL b = i % p;ans = ans * (a * quick_mod(b, p-2) % p) % p;}return ans; }LL Lucas(LL n, LL m) {if(m == 0) return 1;return C(n % p, m % p) * Lucas(n / p, m / p) % p; }int main() {int T;scanf("%d", &T);while(T--){scanf("%I64d%I64d%I64d", &n, &m, &p);printf("%I64d\n", Lucas(n,m));}return 0; }

斯特林公式

void init(){//組合數遞推，第一類斯特林數c[0][0]=1;stir[0][0]=1;for(int i=1;i<=2000;i++){c[i][0]=c[i][i]=1;stir[i][0]=0;stir[i][i]=1;for(int j=1;j<i;j++){c[i][j] = (c[i-1][j] + c[i-1][j-1])%mod; stir[i][j]=(stir[i-1][j-1]+stir[i-1][j]*(i-1))%mod;}} }

第二類斯特林就是把（n-1）變成m

?錯排公式

?D（n）=（n-1）[D（n-1）+D（n-2）]；?? D（1）=0； D（2）=1

卡特蘭數公式

?快速傅里葉變換模板 待更

#include<bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e6 + 1000; const double PI = acos(-1.0);struct Complex{double r, i;Complex(){ r = 0, i = 0; }Complex(double real,double imag): r(real), i(imag){} }F[maxn], G[maxn]; Complex operator + (Complex a,Complex b){ return Complex( a.r + b.r , a.i + b.i ); } Complex operator - (Complex a,Complex b){ return Complex( a.r - b.r , a.i - b.i ); } Complex operator * (Complex a,Complex b){ return Complex( a.r * b.r - a.i * b.i, a.i * b.r + b.i * a.r ); }int rev[maxn], len, lim = 1;void FFT(Complex* a,int opt) {for(int i = 0; i < lim; ++i) if(i < rev[i]) swap(a[i], a[rev[i]]);for(int dep = 1; dep <= log2(lim); ++dep){int m = 1 << dep;Complex wn = Complex(cos(2.0 * PI / m), opt * sin(2.0 * PI / m));for(int k = 0; k < lim; k += m){Complex w = Complex(1, 0);for(int j = 0; j < m / 2; j++){Complex t = w * a[k + j + m / 2];Complex u = a[k + j];a[k + j] = u + t;a[k + j + m / 2] = u - t;w = w * wn;}}}if(opt == -1)for(int i = 0;i < lim; ++i) a[i].r /= lim; } signed main() {int n,m;scanf("%lld %lld", &n, &m);for(int i = 0; i <= n; i++) scanf("%lf", &F[i].r);for(int i = 0; i <= m; i++) scanf("%lf", &G[i].r);while(lim <= n+m) lim <<= 1,len++;for(int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));FFT(F,1); FFT(G,1);for(int i = 0; i <= lim; i++) F[i] = F[i] * G[i];FFT(F,-1);for(int i = 0; i <= n+m; i++)printf("%lld ",(int)(F[i].r + 0.5)); return 0; } #include <cstdio> #include <cmath> #include <algorithm>const int MAXN = 262144 + 1; const double PI = std::acos(-1.0);struct Complex {double r, i;Complex(double r = 0, double i = 0) : r(r), i(i) {}Complex conj() const { return Complex(r, -i); }Complex operator+(const Complex &rhs) const { return Complex(r + rhs.r, i + rhs.i); }Complex operator-(const Complex &rhs) const { return Complex(r - rhs.r, i - rhs.i); }Complex operator*(const Complex &rhs) const { return Complex(r * rhs.r - i * rhs.i, r * rhs.i + i * rhs.r); }Complex operator/(double rhs) const { return Complex(r / rhs, i / rhs); } };class FFT { private:static const int N = 262144;Complex omega[N + 1], omegaInv[N + 1];void init() {for (int i = 0; i < N; i++) {omega[i] = Complex(std::cos(2 * PI / N * i), std::sin(2 * PI / N * i));omegaInv[i] = omega[i].conj();}}void reverse(Complex *a, int n) {for (int i = 0, j = 0; i < n; i++) {if (i < j) std::swap(a[i], a[j]);for (int l = n >> 1; (j ^= l) < l; l >>= 1) {}}}void transform(Complex *a, int n, Complex *omega) {reverse(a, n);for (int l = 2; l <= n; l <<= 1) {int hl = l >> 1;for (Complex *x = a; x != a + n; x += l) {for (int i = 0; i < hl; i++) {Complex t = omega[N / l * i] * x[i + hl];x[i + hl] = x[i] - t;x[i] = x[i] + t;}}}}public:FFT() { init(); }int extend(int n) {int res = 1;while (res < n) res <<= 1;return res;}void dft(Complex *a, int n) {transform(a, n, omega);}void idft(Complex *a, int n) {transform(a, n, omegaInv);for (int i = 0; i < n; i++) a[i] = a[i] / n;} } fft;int main() {int n, m;scanf("%d %d", &n, &m);static Complex a[MAXN], b[MAXN];for (int i = 0; i <= n; i++) scanf("%lf", &a[i].r);for (int i = 0; i <= m; i++) scanf("%lf", &b[i].r);int N = fft.extend(n + m + 1);fft.dft(a, N);fft.dft(b, N);for (int i = 0; i < N; i++) a[i] = a[i] * b[i];fft.idft(a, N);for (int i = 0; i < n + m + 1; i++)printf("%.0lf%c", a[i].r + 0.001, " \n"[i == n + m]);return 0; }

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的数论公式笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。