https://codeforces.com/contest/1228
C. Primes and Multiplication
题意:定义 g ( x , y ) g(x,y) g ( x , y ) 为最大能整除x的y的幂次,f ( x , y ) f(x,y) f ( x , y ) 为所有x的质因数k的 g ( y , k ) g(y,k) g ( y , k ) 值的乘积。例如:f ( 30 , 70 ) = g ( 70 , 2 ) ⋅ g ( 70 , 3 ) ⋅ g ( 70 , 5 ) = 2 1 ⋅ 3 0 ⋅ 5 1 = 10 f(30, 70) = g(70, 2) \cdot g(70, 3) \cdot g(70, 5) = 2^1 \cdot 3^0 \cdot 5^1 = 10 f ( 30 , 70 ) = g ( 70 , 2 ) ⋅ g ( 70 , 3 ) ⋅ g ( 70 , 5 ) = 2 1 ⋅ 3 0 ⋅ 5 1 = 10 ,求 f ( x , 1 ) ⋅ f ( x , 2 ) ⋅ … ⋅ f ( x , n ) m o d ( 1 0 9 + 7 ) f(x, 1) \cdot f(x, 2) \cdot \ldots \cdot f(x, n) \bmod{(10^{9} + 7)} f ( x , 1 ) ⋅ f ( x , 2 ) ⋅ … ⋅ f ( x , n ) mod ( 1 0 9 + 7 ) ,( 2 ≤ x ≤ 1 0 9 , 1 ≤ n ≤ 1 0 18 ) (2 \le x \le 10^{9},1 \le n \le 10^{18}) ( 2 ≤ x ≤ 1 0 9 , 1 ≤ n ≤ 1 0 18 )
首先 x \sqrt x x 分解x的质因数,然后考虑每个质因数的贡献。
对于一个质因数,不断增加幂次,同时计算1到n里有几个,就乘几次。
注意控制数不要爆了ll,乘到极限就不要乘了。
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 #include <bits/stdc++.h> using namespace std;#define ll long long const int N = 1e5 + 10 ;const int INF = 0x3f3f3f3f ;const ll mod = 1000000007 ;ll x, n; int tot;int prime[N];bool vis[N];void init (int n) { for (int i = 2 ; i <= n; i++) { if (vis[i])continue ; prime[++tot] = i; for (int j = i; j <= n; j += i)vis[j] = 1 ; } } vector<ll>pr; ll Pow (ll a,ll b) { ll res = 1 ; a %= mod; while (b) { if (b & 1 )res = res * a%mod; a = a * a%mod; b >>= 1 ; } return res; } int main () { cin >> x >> n; init (100000 ); for (int i = 1 ; i<=tot&&prime[i] <= x; i++) { if (x%prime[i] == 0 ) { pr.push_back (1ll *prime[i]); while (x%prime[i] == 0 )x /= prime[i]; } } ll ans = 1 ; if (x != 1 )pr.push_back (x); for (ll u : pr) { ll tmp = u; while (u <= n) { ll t = n / u; ans = ans * Pow (tmp, t) % mod; if (t < tmp)break ; u *= tmp; } } cout << ans << endl; return 0 ; }
D. Complete Tripartite
题意:给定无向图,求完全三分图的点染色方案。
完全三分图和普通的三分图又不同,完全三分图的每个属于相同点集的点的连边情况都完全相同。
这个关键点想到了之后就很简单了,那么总共只有三种连边情况了,map维护邻接表,如果个数不等于3,就不行。注意还要判断如果有孤立点,一定没法染成完全三分图,因为要求和其它点集的点都有连边。
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 #include <bits/stdc++.h> using namespace std;#define ll long long const int N = 1e5 + 10 ;const int INF = 0x3f3f3f3f ;int n, m, cnt;set<int >G[N]; map<set<int >, int >mp; int main () { scanf ("%d%d" , &n, &m); for (int i = 0 ; i < m; i++) { int u, v; scanf ("%d%d" , &u, &v); G[u].insert (v); G[v].insert (u); } for (int i = 1 ; i <= n; i++) { if (G[i].empty ()) { puts ("-1" ); return 0 ; } if (!mp.count (G[i]))mp[G[i]] = ++cnt; } if (cnt != 3 )puts ("-1" ); else for (int i = 1 ; i <= n; i++)printf ("%d%s" , mp[G[i]], i == n ? "\n" : " " ); return 0 ; }
E. Another Filling the Grid
题意:一个nn的矩阵要填数,要求每行最小值为1,每列最小值为1,问方案数。
三种做法,虽然现在都不会orz,但还是记一下。
做法一:
O ( n 2 log n ) O(n^2\log n) O ( n 2 log n )
二维容斥原理
枚举至少 有 i i i 行没有1,至少 有 j j j 列没有1。
a n s = ∑ i = 0 n ∑ j = 0 n ( − 1 ) i + j C n i C n j ⋅ ( k − 1 ) i n + j n − i j ⋅ k n 2 − ( i n + j n − i j ) ans=\sum_{i=0}^n\sum_{j=0}^n(-1)^{i+j}C_n^iC_n^j\cdot(k-1)^{in+jn-ij}\cdot k^{n^2-(in+jn-ij)}
an s = i = 0 ∑ n j = 0 ∑ n ( − 1 ) i + j C n i C n j ⋅ ( k − 1 ) in + jn − ij ⋅ k n 2 − ( in + jn − ij )
感觉二维的容斥很难理解啊。。前面的是二维容斥,后面的是至少 有 i i i 行没有1,至少 有 j j j 列没有1的方案数。
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 #include <bits/stdc++.h> using namespace std;#define ll long long const int N = 1e6 + 10 ;const int INF = 0x3f3f3f3f ;const ll mod = 1e9 + 7 ;ll n, k, ans; ll C[300 ][300 ]; ll Pow (ll a,ll b) { ll res = 1 ; while (b) { if (b & 1 )res = res * a%mod; a = a * a%mod; b >>= 1 ; } return res; } ll f (ll i) { return Pow (Pow (k, i) - Pow (k - 1 , i), n); } int main () { scanf ("%lld%lld" , &n, &k); for (int i = 0 ; i <= n; i++)C[i][0 ] = C[i][i] = 1 ; for (int i = 2 ; i <= n; i++) for (int j = 1 ; j < i; j++) C[i][j] = (C[i - 1 ][j - 1 ] + C[i - 1 ][j]) % mod; for (int i = 0 ; i <= n; i++) { for (int j = 0 ; j <= n; j++) { ll cnt = i * n + j * n - i * j; ll tmp = Pow (-1 , i + j)*C[n][i] % mod*C[n][j] % mod*Pow (k - 1 , cnt) % mod*Pow (k, n*n - cnt) % mod; ans = (ans + tmp + mod) % mod; } } cout << ans << endl; return 0 ; }
方法二:
O ( n log n ) O(n\log n) O ( n log n )
二维容斥+二项式定理
还是上面那个式子,考虑化简成一层循环。
a n s = ∑ i = 0 n ∑ j = 0 n ( − 1 ) i + j C n i C n j ⋅ ( k − 1 ) i n + j n − i j ⋅ k n 2 − ( i n + j n − i j ) = ∑ i = 0 n ( − 1 ) i C n i ⋅ ( ∑ j = 0 n C n j ( k − 1 ) i n + j n − i j ⋅ k n 2 − ( i n + j n − i j ) ) ans=\sum_{i=0}^n\sum_{j=0}^n(-1)^{i+j}C_n^iC_n^j\cdot(k-1)^{in+jn-ij}\cdot k^{n^2-(in+jn-ij)}\\
=\sum_{i=0}^n(-1)^iC_n^i\cdot(\sum_{j=0}^n C_n^j(k-1)^{in+jn-ij}\cdot k^{n^2-(in+jn-ij)})\\
an s = i = 0 ∑ n j = 0 ∑ n ( − 1 ) i + j C n i C n j ⋅ ( k − 1 ) in + jn − ij ⋅ k n 2 − ( in + jn − ij ) = i = 0 ∑ n ( − 1 ) i C n i ⋅ ( j = 0 ∑ n C n j ( k − 1 ) in + jn − ij ⋅ k n 2 − ( in + jn − ij ) )
第二个 ∑ \sum ∑ 可以根据二项式定理化简。
( k − 1 ) i n + j n − i j ⋅ k n 2 − i n − j n + i j = [ ( k − 1 ) i ] n − j ⋅ [ ( k − 1 ) n ] j ⋅ [ k ( n − i ) ] n − j = [ ( k − 1 ) i ] j ⋅ [ ( k − 1 ) i k n − i ] n − j (k-1)^{in+jn-ij}\cdot k^{n^2-in-jn+ij}\\
=[(k-1)^i]^{n-j}\cdot[(k-1)^n]^j\cdot [k^{(n-i)}]^{n-j}\\
=[(k-1)^i]^j\cdot[(k-1)^ik^{n-i}]^{n-j}
( k − 1 ) in + jn − ij ⋅ k n 2 − in − jn + ij = [( k − 1 ) i ] n − j ⋅ [( k − 1 ) n ] j ⋅ [ k ( n − i ) ] n − j = [( k − 1 ) i ] j ⋅ [( k − 1 ) i k n − i ] n − j
所以第二个 ∑ \sum ∑ 为:
[ ( k − 1 ) i k n − i − ( k − 1 ) n ] n [(k-1)^ik^{n-i}-(k-1)^n]^n
[( k − 1 ) i k n − i − ( k − 1 ) n ] n
则结果为:
a n s = ∑ i = 0 n ( − 1 ) i C n i ⋅ [ ( k − 1 ) i k n − i − ( k − 1 ) n ] n ans=\sum_{i=0}^n(-1)^iC_n^i\cdot [(k-1)^ik^{n-i}-(k-1)^n]^n
an s = i = 0 ∑ n ( − 1 ) i C n i ⋅ [( k − 1 ) i k n − i − ( k − 1 ) n ] n
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 #include <bits/stdc++.h> using namespace std;#define ll long long const int N = 1e6 + 10 ;const int INF = 0x3f3f3f3f ;const ll mod = 1e9 + 7 ;ll n, k, ans; ll C[300 ][300 ]; ll Pow (ll a,ll b) { ll res = 1 ; while (b) { if (b & 1 )res = res * a%mod; a = a * a%mod; b >>= 1 ; } return res; } ll f (ll i) { return Pow (Pow (k, i) - Pow (k - 1 , i), n); } int main () { scanf ("%lld%lld" , &n, &k); for (int i = 0 ; i <= n; i++)C[i][0 ] = C[i][i] = 1 ; for (int i = 2 ; i <= n; i++) for (int j = 1 ; j < i; j++) C[i][j] = (C[i - 1 ][j - 1 ] + C[i - 1 ][j]) % mod; for (int i = 0 ; i <= n; i++) { ll tmp = Pow (-1 , i)*C[n][i] * Pow ((Pow (k - 1 , i)*Pow (k, n - i) % mod - Pow (k - 1 , n) + mod) % mod, n) % mod; ans = (ans + tmp + mod) % mod; } cout << ans << endl; return 0 ; }
做法三:
O ( n log n ) O(n\log n) O ( n log n )
预处理+一维容斥
有两个维度,考虑消除 j j j 的影响,那么就需要规定列一定是满足条件的。
首先预处理出一个函数 f ( i ) f(i) f ( i ) 表示 i i i 行,n n n 列的矩阵,每列至少 有1个1的方案数。
f ( i ) = ( k i − ( k − 1 ) i ) n f(i)=(k^i-(k-1)^i)^n
f ( i ) = ( k i − ( k − 1 ) i ) n
还是比较容易理解的,总的方案数-没有1的方案数。
再容斥。
a n s = ∑ i = 0 n ( − 1 ) i C n i ⋅ ( k − 1 ) i n ⋅ f ( n − i ) ans=\sum_{i=0}^n(-1)^iC_n^i\cdot (k-1)^{in}\cdot f(n-i)
an s = i = 0 ∑ n ( − 1 ) i C n i ⋅ ( k − 1 ) in ⋅ f ( n − i )
取出 i i i 行放最后,每行都没有1,其它行组成的矩阵每列至少有1个1.
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 #include <bits/stdc++.h> using namespace std;#define ll long long const int N = 1e6 + 10 ;const int INF = 0x3f3f3f3f ;const ll mod = 1e9 + 7 ;ll n, k, ans; ll C[300 ][300 ]; ll Pow (ll a, ll b) { ll res = 1 ; while (b) { if (b & 1 )res = res * a%mod; a = a * a%mod; b >>= 1 ; } return res; } ll f (ll i) { return Pow (Pow (k, i) - Pow (k - 1 , i), n); } int main () { scanf ("%lld%lld" , &n, &k); for (int i = 0 ; i <= n; i++)C[i][0 ] = C[i][i] = 1 ; for (int i = 2 ; i <= n; i++) for (int j = 1 ; j < i; j++) C[i][j] = (C[i - 1 ][j - 1 ] + C[i - 1 ][j]) % mod; for (int i = 0 ; i <= n; i++) { ll tmp = Pow (-1 , i)*C[n][i] * Pow (k - 1 , n*i) % mod*f (n - i) % mod; ans = (ans + tmp + mod) % mod; } printf ("%lld\n" , ans); return 0 ; }