数学基础问题
Again Prime? No time.
对 n ! n! n ! 进行阶乘分解,对某个素因子 p p p , 其分解为 p res p^{\text{res}} p res
对 m m m 进行素因子分解,并且求出和阶乘素因子的交集
( p e ) k = res a n s ← min ⌊ res e ⌋ \left(p^e\right)^k = \text{res} \quad ans \leftarrow \min \left\lfloor \frac{\text{res}}{e} \right\rfloor
( p e ) k = res a n s ← min ⌊ e res ⌋
注意这里即使 res < e \text{res} < e res < e 也没有关系,res < e \text{res} < e res < e 意味着 ⌊ res / e ⌋ = 0 \left\lfloor \text{res}/e \right\rfloor = 0 ⌊ res / e ⌋ = 0
a n s = 0 , a n s = ∞ ans = 0, \ ans = \infty a n s = 0 , a n s = ∞ 均无解
The Super Powers
不妨设一个超级幂的唯一分解,对于某质因子 p p p 有
p e = p s 1 s 2 ⋯ s m e = s 1 s 2 ⋯ s m \begin{aligned}
p^e &= p^{s_1s_2\cdots s_m} \\
e &= s_1s_2\cdots s_m
\end{aligned}
p e e = p s 1 s 2 ⋯ s m = s 1 s 2 ⋯ s m
不难想到,如果一个数是超级幂,满足
{ e 是合数,且 e > 4 枚举底数 x ∈ [ 2 → 2 64 − 1 ] , e ⩽ ⌈ 64 ⋅ log ( 2 ) log ( x ) ⌉ − 1 \begin{cases}
e \ \text{是合数,且} \ e > 4 \\
\text{枚举底数} \ x \in [2 \to 2^{64}-1], e \leqslant \left\lceil \frac{64 \cdot \log(2)}{\log(x)} \right\rceil - 1
\end{cases}
{ e 是合数,且 e > 4 枚举底数 x ∈ [ 2 → 2 6 4 − 1 ] , e ⩽ ⌈ l o g ( x ) 6 4 ⋅ l o g ( 2 ) ⌉ − 1
暴力法即可解决
for ∀ x ∈ [ 2 ⋯ ] \textbf{for} \ \forall x \in [2 \cdots ] for ∀ x ∈ [ 2 ⋯ ] 枚举底数 x , e ⩽ ⌈ 64 ⋅ log ( 2 ) log ( x ) ⌉ − 1 x, \quad e \leqslant \left\lceil \frac{64 \cdot \log(2)}{\log(x)} \right\rceil - 1 x , e ⩽ ⌈ l o g ( x ) 6 4 ⋅ l o g ( 2 ) ⌉ − 1
r e s ← 1 for ∀ i ∈ [ 1 → e ] res \leftarrow 1 \quad \textbf{for} \ \forall i \in [1 \to e] r e s ← 1 for ∀ i ∈ [ 1 → e ] 枚举指数 i i i
r e s ← r e s × ∏ x ⇔ r e s = r e s ⋅ x i \quad res \leftarrow res \times \prod x \ \Leftrightarrow \ res = res \cdot x^i r e s ← r e s × ∏ x ⇔ r e s = r e s ⋅ x i
if i 为合数 , x i 是 super power , r e s → ans { ⋯ } \textbf{if} \ i \ \text{为合数}, \quad x^{i} \ \text{是 super power}, \ res \to \text{ans}\{\cdots \} if i 为合数 , x i 是 super power , r e s → ans { ⋯ }
说明,在算法中我们只需要从小到大枚举底数 x x x ,然后取幂指 i i i 为合数即可,如果 x x x 可以进行分解
因为是从小到大枚举的,x x x 的因数一定在 x x x 之前被检查到了,并不会漏解
Teams
根据组合原理,所求的方案是
S ( n ) = ∑ k = 1 n ( n k ) ( k 1 ) = ∑ k = 1 n k ⋅ ( n k ) S ( n ) = 1 ( n 1 ) + 2 ( n 2 ) + ⋯ ( n − 1 ) ( n n − 1 ) + n ( n n ) S ( n ) = n ( n n ) + ( n − 1 ) ( n n − 1 ) + ( n − 2 ) ( n n − 2 ) ⋯ + 1 ( n 1 ) \begin{aligned}
S(n) &= \sum_{k=1}^{n} \binom{n}{k} \binom{k}{1} = \sum_{k=1}^{n} k \cdot \binom{n}{k} \\
S(n) &= 1\binom{n}{1} + 2\binom{n}{2} + \cdots (n-1) \binom{n}{n-1} + n \binom{n}{n} \\
S(n) = n\binom{n}{n} + &(n-1)\binom{n}{n-1} + (n-2)\binom{n}{n-2} \cdots + 1\binom{n}{1}
\end{aligned}
S ( n ) S ( n ) S ( n ) = n ( n n ) + = k = 1 ∑ n ( k n ) ( 1 k ) = k = 1 ∑ n k ⋅ ( k n ) = 1 ( 1 n ) + 2 ( 2 n ) + ⋯ ( n − 1 ) ( n − 1 n ) + n ( n n ) ( n − 1 ) ( n − 1 n ) + ( n − 2 ) ( n − 2 n ) ⋯ + 1 ( 1 n )
从而可以推出
2 S ( n ) = n ⋅ 2 n ⇒ S ( n ) = n ⋅ 2 n − 1 2S(n) = n \cdot 2^{n} \Rightarrow S(n) = n \cdot 2^{n-1}
2 S ( n ) = n ⋅ 2 n ⇒ S ( n ) = n ⋅ 2 n − 1
唯一分解定理
LCM Cardinality
其实条件可以写成
{ a ⋅ b = n ⋅ gcd ( a , b ) gcd ( a , b ) ∣ n \begin{cases}
&a \cdot b = n \cdot \text{gcd}(a, b) \\
&\text{gcd}(a, b) \mid n
\end{cases}
{ a ⋅ b = n ⋅ gcd ( a , b ) gcd ( a , b ) ∣ n
很容易想到应该对 n n n 进行素因子分解
对 n n n 进行素因子分解
n = p 1 s 1 p 2 s 2 ⋯ p m s m a = p 1 a 1 p 2 a 2 ⋯ p m s m b = p 1 b 1 p 2 b 2 ⋯ p m s m \begin{aligned}
n &= p_1^{s_1}p_2^{s_2} \cdots p_m^{s_m} \\
a &= p_1^{a_1}p_2^{a_2} \cdots p_m^{s_m} \\
b &= p_1^{b_1}p_2^{b_2} \cdots p_m^{s_m}
\end{aligned}
n a b = p 1 s 1 p 2 s 2 ⋯ p m s m = p 1 a 1 p 2 a 2 ⋯ p m s m = p 1 b 1 p 2 b 2 ⋯ p m s m
原问题等价于
{ max ( a i , b i ) = s i s i 中有多少种无序 ( a i , b i ) 组合 \begin{cases}
\max(a_i, b_i) = s_i \\
s_i \text{中有多少种无序} (a_i, b_i) 组合
\end{cases}
{ max ( a i , b i ) = s i s i 中有多少种无序 ( a i , b i ) 组 合
先从 ( a i , b i ) (a_i, b_i) ( a i , b i ) 中任选一个令其等于 s i s_i s i ,有 ( 2 1 ) 2 \choose 1 ( 1 2 ) 种
剩下的元素从 [ 0 , s i − 1 ] [0, s_i-1] [ 0 , s i − 1 ] 中选,有 s i s_i s i 种,一共有 ( 2 1 ) ⋅ s i = 2 s i \binom{2}{1} \cdot s_i = 2s_i ( 1 2 ) ⋅ s i = 2 s i 种
另外考虑到 a i = b i = s i a_i = b_i = s_i a i = b i = s i 这一种情况,因为是 ( a i , b i ) (a_i, b_i) ( a i , b i ) 无序数组,所以 ( s i , s i ) (s_i, s_i) ( s i , s i ) 算作 1 1 1 种
∀ p i \forall \ p_i ∀ p i ,一共有 2 s i + 1 2s_i + 1 2 s i + 1 种选择
∏ i ( 2 s i + 1 ) 2 \frac{\prod_i (2s_i + 1)}{2}
2 ∏ i ( 2 s i + 1 )
但注意 ∏ ( 2 s i + 1 ) \prod(2s_i + 1) ∏ ( 2 s i + 1 ) 是奇数,此时 ∏ ( 2 s i + 1 ) \prod(2s_i+1) ∏ ( 2 s i + 1 ) 的结果中包含 ( n , n ) (n, n) ( n , n ) 这一组
要 + 1 +1 + 1 后除以 2 2 2 才是答案
a n s = ⌈ ∏ i ( 2 s i + 1 ) + 1 2 ⌉ = ⌊ ∏ i ( 2 s i + 1 ) 2 ⌋ + 1 ans = \left\lceil \frac{\prod_i (2s_i + 1) + 1}{2} \right\rceil = \left\lfloor \frac{\prod_i (2s_i+1)}{2} \right\rfloor + 1
a n s = ⌈ 2 ∏ i ( 2 s i + 1 ) + 1 ⌉ = ⌊ 2 ∏ i ( 2 s i + 1 ) ⌋ + 1
UVA10791
先对 n = LCM n=\textbf{LCM} n = LCM 进行素因子分解,n = ∏ p i s i n = \prod p_i^{s_i} n = ∏ p i s i
那么 min sum = ∑ p i s i \min \text{sum} = \sum p_i^{s_i} min sum = ∑ p i s i ,其实不难证明
对于任意两个素因子 p i , p j , p i < p j p_i, p_j, \quad p_i < p_j p i , p j , p i < p j ,显然有 p i p j ⩽ p i + p j p_ip_j \leqslant p_i + p_j p i p j ⩽ p i + p j
p i p j ⩽ p i + p j ⇒ p i + p j p i p j ⩽ 1 ⇒ 1 p i + 1 p j ⩽ 1 p_ip_j \leqslant p_i + p_j \Rightarrow \frac{p_i+p_j}{p_ip_j} \leqslant 1 \Rightarrow \frac{1}{p_i} + \frac{1}{p_j} \leqslant 1
p i p j ⩽ p i + p j ⇒ p i p j p i + p j ⩽ 1 ⇒ p i 1 + p j 1 ⩽ 1
由此 ∑ p i s i \sum p_i^{s_i} ∑ p i s i 即为最小
在素因子分解后,如果少了某个素因子 p i p_i p i ,那么 lcm \text{lcm} lcm 就 < n < n < n 了,如果多了某个素因子 p i p_i p i ,如果此时 lcm ( A , B ) = n \text{lcm}(A, B) = n lcm ( A , B ) = n
令 B ← B / p i B \leftarrow B/p_i B ← B / p i ,仍然满足 lcm = n \text{lcm} = n lcm = n 并且 A + B A+B A + B 更小
另外,如果 n n n 是素数或者是 n = 1 n=1 n = 1 ,直接返回 n + 1 n+1 n + 1 即可
同余与剩余类
任意整数 a m o d p a \bmod p a m o d p ,可以根据余数组成 p p p 个类,分别为
{ 0 } , { 1 } , ⋯ , { p − 1 } \{0\}, \{1\}, \cdots , \{p-1\}
{ 0 } , { 1 } , ⋯ , { p − 1 }
于是很多同余问题就转换成剩余类计数问题,比如我们可以用 s { 0 } s_{\{0\}} s { 0 } 表示剩余类 { 0 } \{0\} { 0 } 的个数
剩余类的个数表示为
s { 0 } , s { 1 } , ⋯ , s { p − 1 } s_{\{0\}}, s_{\{1\}}, \cdots , s_{\{p-1\}}
s { 0 } , s { 1 } , ⋯ , s { p − 1 }
如果一个 B B B 位数能够被 p p p 整除,那么这个数每个数位的和 ∑ i \sum_{i} ∑ i 也能够被 p p p 整除
可以遍历每个数位 for ∀ i ∈ [ 0 , B ) \textbf{for} \ \forall i \in [0, B) for ∀ i ∈ [ 0 , B ) ,统计出
s { 0 } , s { 1 } , ⋯ , s { p − 1 } ∑ i ≡ 1 s { 1 } + 2 s { 2 } + ⋯ + ( p − 1 ) s { p − 1 } ( m o d p ) \begin{gathered}
s_{\{0\}}, s_{\{1\}}, \cdots , s_{\{p-1\}} \\
\sum_{i} \equiv 1s_{\{1\}} + 2s_{\{2\}} + \cdots + (p-1)s_{\{p-1\}} (\bmod p)
\end{gathered}
s { 0 } , s { 1 } , ⋯ , s { p − 1 } i ∑ ≡ 1 s { 1 } + 2 s { 2 } + ⋯ + ( p − 1 ) s { p − 1 } ( m o d p )
UVA11489
对于数位 b i b_i b i ,统计出剩余类个数 s { 0 } , s { 1 } , s { 2 } s_{\{0\}}, s_{\{1\}}, s_{\{2\}} s { 0 } , s { 1 } , s { 2 } ,并且计算出
∑ i ≡ ( s { 1 } + 2 s { 2 } ) ( m o d 3 ) \sum_{i} \equiv (s_{\{1\}} + 2s_{\{2\}}) (\bmod 3)
i ∑ ≡ ( s { 1 } + 2 s { 2 } ) ( m o d 3 )
如果 ∑ i ≡ 0 ( m o d 3 ) \sum_{i} \equiv 0 (\bmod 3) ∑ i ≡ 0 ( m o d 3 ) ,那么只需要考虑 { 0 } \{0\} { 0 } 这个剩余类
s { 0 } m o d 2 = 1 s_{\{0\}} \bmod 2 = 1 s { 0 } m o d 2 = 1 ,S S S 获胜,否则 T T T 获胜
如果∑ i ≡ { 1 } or { 2 } \sum_i \equiv \{1\} \ \textbf{or} \ \{2\} ∑ i ≡ { 1 } or { 2 } ,需要考虑 { 1 } , { 2 } \{1\}, \{2\} { 1 } , { 2 } 这两个剩余类
如果 ∑ i ≡ { 1 } , s { 1 } > 0 \sum_i \equiv \{1\}, \quad s_{\{1\}} > 0 ∑ i ≡ { 1 } , s { 1 } > 0 ,要满足取完数,所有数位的和能够被 3 3 3 整除
S S S 第一次取一定是拿走 b i ≡ 1 ( m o d 3 ) b_i \equiv 1(\bmod 3) b i ≡ 1 ( m o d 3 ) 的那个数位,这样
∑ ← ( 1 − 1 ) ( m o d 3 ) ⇒ ∑ ≡ 0 ( m o d 3 ) \sum \leftarrow (1-1) (\bmod 3) \Rightarrow \sum \equiv 0 (\bmod 3) ∑ ← ( 1 − 1 ) ( m o d 3 ) ⇒ ∑ ≡ 0 ( m o d 3 ) ,才能使剩下的数合法
∑ i ≡ { 2 } \sum_i \equiv \{2\} ∑ i ≡ { 2 } 同理
如果 ∑ i ≡ m ( m o d 3 ) , s { m } = 0 \sum_i \equiv m (\bmod 3), \quad s_{\{m\}} = 0 ∑ i ≡ m ( m o d 3 ) , s { m } = 0 ,那么 S S S 不能取数,T T T 获胜
否则的话,S S S 取数之后,转为第一种情况 ∑ ≡ 0 ( m o d 3 ) \sum \equiv 0(\bmod 3) ∑ ≡ 0 ( m o d 3 ) ,只不过最先取数的是 T T T
将第一种情况结果取反,就是答案
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 int s[4]; string str; void solve () { for (auto x : str) s[x % 3]++; int mo = 0; for (int i = 0; i <= 2; i++) mo += i * s[i]; mo %= 3; if (mo == 0) { string res; s[0] % 2 ? res = "S" : res = "T" ; printf ("%s\n" , res.c_str()); } else { if (s[mo] == 0) printf ("T\n" ); else { string res; s[0] % 2 ? res = "T" : res = "S" ; printf ("%s\n" , res.c_str()); } } } int main () { freopen("input.txt" , "r" , stdin); int T; cin >> T; int kase = 0; while (T--) { printf ("Case %d: " , ++kase); memset(s, 0, sizeof s); cin >> str; solve(); } }
组合计数基础
重复元素的全排列方案数
定理 n n n 个元素,分为 m m m 组,其中本组元素全部相同,不同组元素不同,并且第 i i i 组有 p i p_i p i 个
总的排列数为
n ! ∏ k = 1 m p k ! \frac{n!}{\prod_{k=1}^{m} p_k !}
∏ k = 1 m p k ! n !
Add Again
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 const int maxn = 15; const ll one[13] = { 0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111 }; int n; ll fac[maxn]; int cnt[maxn]; void prework () { fac[0] = fac[1] = 1; for (int i = 2; i <= 12; i++) { fac[i] = fac[i-1] * (ll)i; } } int main () { freopen("input.txt" , "r" , stdin); prework(); while (scanf("%d" , &n) == 1 && n) { memset(cnt, 0, sizeof cnt); int sum = 0; for (int i = 0; i < n; i++) { int x; scanf("%d" , &x); sum += x, cnt[x]++; } ll res = (ll)sum * fac[n-1]; for (int i = 0; i <= 9; i++) res /= fac[cnt[i]]; printf ("%lld\n" , res * one[n]); } }
回文串计数举例
UVA12050
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 const int N = 20; ll cnt[N]; int C; void prework () { cnt[1] = 9, cnt[2] = 9; for (int i = 3; i < N; i++) { if (i & 1) cnt[i] = cnt[i-2] * 10; else cnt[i] = cnt[i-1]; } } void solve () { // i len, C th int i = 1; for (; i < N; i++) { if (cnt[i] < C) C -= cnt[i]; else break ; } C--; string str(i, '0' ); int k = i/2; while (C) { str[k++] = '0' + C % 10; C /= 10; } str[i-1]++; for (int j = 0; j < i/2; j++) { str[j] = str[i-1-j]; } printf ("%s\n" , str.c_str()); } int main () { freopen("input.txt" , "r" , stdin); prework(); // for (int i = 1; i < N; i++) debug(cnt[i]); while (scanf("%d" , &C) == 1 && C) { solve(); } }