https://codeforces.com/contest/1228

C. Primes and Multiplication

 

题意:定义 g(x,y)g(x,y) 为最大能整除x的y的幂次,f(x,y)f(x,y) 为所有x的质因数k的 g(y,k)g(y,k) 值的乘积。例如:f(30,70)=g(70,2)g(70,3)g(70,5)=213051=10f(30, 70) = g(70, 2) \cdot g(70, 3) \cdot g(70, 5) = 2^1 \cdot 3^0 \cdot 5^1 = 10,求 f(x,1)f(x,2)f(x,n)mod(109+7)f(x, 1) \cdot f(x, 2) \cdot \ldots \cdot f(x, n) \bmod{(10^{9} + 7)}(2x109,1n1018)(2 \le x \le 10^{9},1 \le n \le 10^{18})

首先 x\sqrt 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(n2logn)O(n^2\log n)

二维容斥原理

枚举至少ii 行没有1,至少jj 列没有1。

ans=i=0nj=0n(1)i+jCniCnj(k1)in+jnijkn2(in+jnij)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)}

感觉二维的容斥很难理解啊。。前面的是二维容斥,后面的是至少ii 行没有1,至少jj 列没有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(nlogn)O(n\log n)

二维容斥+二项式定理

还是上面那个式子,考虑化简成一层循环。

ans=i=0nj=0n(1)i+jCniCnj(k1)in+jnijkn2(in+jnij)=i=0n(1)iCni(j=0nCnj(k1)in+jnijkn2(in+jnij))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)})\\

第二个 \sum 可以根据二项式定理化简。

(k1)in+jnijkn2injn+ij=[(k1)i]nj[(k1)n]j[k(ni)]nj=[(k1)i]j[(k1)ikni]nj(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}

所以第二个 \sum 为:

[(k1)ikni(k1)n]n[(k-1)^ik^{n-i}-(k-1)^n]^n

则结果为:

ans=i=0n(1)iCni[(k1)ikni(k1)n]nans=\sum_{i=0}^n(-1)^iC_n^i\cdot [(k-1)^ik^{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(nlogn)O(n\log n)

预处理+一维容斥

有两个维度,考虑消除 jj 的影响,那么就需要规定列一定是满足条件的。

首先预处理出一个函数 f(i)f(i) 表示 ii 行,nn 列的矩阵,每列至少有1个1的方案数。

f(i)=(ki(k1)i)nf(i)=(k^i-(k-1)^i)^n

还是比较容易理解的,总的方案数-没有1的方案数。

再容斥。

ans=i=0n(1)iCni(k1)inf(ni)ans=\sum_{i=0}^n(-1)^iC_n^i\cdot (k-1)^{in}\cdot f(n-i)

取出 ii 行放最后,每行都没有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;
}