S ( n , m ) S(n,m) S(n,m)记为将 n n n个元素划分为 m m m个圆排列的方案数
递推式: S ( n , m ) = S ( n − 1 , m − 1 ) + ( n − 1 ) ∗ S ( n − 1 , m ) S(n,m) = S(n-1,m-1) + (n - 1) * S(n-1,m) S(n,m)=S(n−1,m−1)+(n−1)∗S(n−1,m) $ ,$ n > m n > m n>m
边界: S ( n , 0 ) = 0 S(n,0) = 0 S(n,0)=0 S ( n , n ) = 1 S(n,n) = 1 S(n,n)=1
可以测试 2 63 2^{63} 263(甚至更高)以下的数是否为素数(但可能是伪素数)
#define ull unsigned long long const int S = 4; // 测试次数,一般4~8次 ull mulit_mod(ull n, ull a, ull MOD) { a %= MOD, n %= MOD; ull ans = 0; for(; n; n >>= 1, a = (a + a) % MOD) if(n & 1) ans = (ans + a) % MOD; return ans; } ull pow_mod(ull n, ull a, ull MOD) { ull ans = 1; for(; n; n >>= 1, a = mulit_mod(a, a, MOD)) if(n & 1) ans = mulit_mod(ans, a, MOD); return ans; } bool Miller_Rabin(ull n, ull a) { ull d = n-1, s = 0, t; while(!(d&1)) d >>= 1, ++s; t = pow_mod(d, a, n); if(t == 1 || t == -1) return true; for(int i = 0; i < s; ++i) { if(t == n-1) return true; t = mulit_mod(t, t, n); } return false; } bool is_prime(ull n) { if(n < 2) return false; if(n == 2) return true; if((n&1) == 0) return false; srand(time(NULL)); for(int i = 0; i < S; ++i) { ull a = rand() % (n-1) + 1; if(a != 1 && n % a == 0) return false; if(!Miller_Rabin(n, a)) return false; } return true; }