Atcoder abc245

發表於 更新於 分類於 ， Disqus： 文章字數： 2.7k 所需閱讀時間 ≈ 9 分鐘
G(dijkstra)Ex(数论,矩阵快速幂,中国剩余定理)

https://atcoder.jp/contests/abc245/tasks

G - Foreign Friends

N个点, 第i个人颜色是Ki

其中一些点是好的点

初始没有边

有m个可选边, 第i个可以花费 Ci 让ui和vi连一条边(无重边自环)

对于每个点, 独立的求最小代价 让它和一个异色好点连通, 或报告不可能

范围

N 1e5

M 1e5

我的思路

既然是每个到异色好点最短距离, 那么路径上一定都是同色或非好点

目前思路是 按一个颜色的个数能不能根号分治

另一个是记录到每个点最小代价不同色的两个最近点

考虑用Floyd+提前退出? 问题是 时间复杂度怎么估计和保证

题解

如果 忽略颜色

多源的好点做dij, 然后 每个点取最小, 然而这个肯定TLE

但如果增加一个点S, 然后它到所有好点距离都是0(单向边!), 那么就可以单源最短路在范围内了

再考虑颜色不同的限制

如果暴力,就是把上面的最短距离多一个维度 [首个好点的颜色], 然而这样也是复杂度超了

注意到, 第三小的颜色的距离永远不对答案有贡献, 所以只用记录最小的两个不同, (这个我倒是想到了)

代码

https://atcoder.jp/contests/abc245/submissions/35054327

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
const ll INF = 0x3f3f3f3f3f3f3f3f;
template <typename T> using minPQ = priority_queue<T,vector<T>, greater<T>>; // 小根堆
ll read(){ll r;scanf("%lld",&r);return r;}

int main() {
  int n = read(); // 1e5, 0-index
  int m = read();
  int k = read(); // 颜色
  int l = read(); // 好点
  vector<int>a(n); // 颜色
  vector<vector<pair<int, ll> > >e(n); // e[u] = {v, cost}
  vector<int>used(n, 0); // 0 未访问, > 0 上一个访问的颜色, =-1 已经两个颜色访问了
  auto d2 = vector(n,map<int,ll>()); // [u][color] = dis;
  minPQ<tuple<ll, int, int> >pq; // 小根堆 { 距离, 点, 起始好点的颜色 }

  rep(i,0,n) a[i] = read(); // 颜色
  rep(i,0,l) { // 好点
    int u = read() - 1;
    pq.push({0,u,a[u]});
  }
  rep(i,0,m) {
    int u = read()-1;
    int v = read()-1;
    int c = read(); // 颜色1-index, 0 表示未确定
    e[u].push_back({v,c});
    e[v].push_back({u,c});
  }
  while (!pq.empty()) {
    auto [dis,u,c] = pq.top();
    pq.pop();
    if(d2[u].count(c) || d2[u].size() == 2)continue; // 没有更新
    d2[u][c] = dis;
    for(auto [v,len]:e[u]) pq.push({dis+len, v, c});
  }
  rep(u,0,n) {
    ll dis = INF;
    for(auto [c,d]:d2[u]) if(c != a[u]) dis=min(dis,d);
    printf("%lld%c",dis == INF?-1:dis," \n"[u==n-1]);
  }
  return 0;
}

Ex - Product Modulo 2

长$k$的序列, 求满足要求的序列的个数mod 998244353

$A_i\in [0,M-1]$

$\prod_{i=1}^k A_i \equiv N \pmod M$

范围

k 1e9

$0\le N < M \le 10^{12}$

2s

1024mb

我的思路

数数题 还是 数论题

这里没有说M是质数

如果M是质数的话

那么, 如果N = 0 吧,这个特殊, 因为Ai < M , 所以如果全部不为0,则不可能为0, 所以这是其中一些为0,剩下的随便填的方案数, 简单的排列组合问题, 或者所有情况-非零的时候

如果 $N\ne 0$, 那么 f(i,j) 表示前i个 乘积为j的方案数, 则有f(i,j0) = f(i,j1), 因为归纳法, i=1时,所有相等,而i时如果所有相等,那么f(i+1,j) = sum f(i,1..m-1), f(i+1,j) = (m-1)f(i,j), 啊不就很好算, ans[n] = (m-1)^{k-1}

回到一般情况, 如果M不是质数

那用上面的想法,就是找等价类

去计算等价类之间的关系

直接想想不出, 用2x3=6和2x3x5=30来试试

1
2
3
4
5
6
7
8
9
N = 6
a = [1 for i in range(N)]
for t in range(20):
    b = [0 for i in range(N)]
    for i in range(N):
        for j in range(N):
            b[(i*j)%N] += a[i]
    print(b)
    a = b

输出

1
2
3
4
5
6
7
8
6:
[15, 2, 6, 5, 6, 2]
[133, 4, 28, 19, 28, 4]
[975, 8, 120, 65, 120, 8]
15:
[135, 8, 24, 20, 24, 18, 60, 8, 24, 20, 54, 8, 60, 8, 24, 45, 24, 8, 60, 8, 54, 20, 24, 8, 60, 18, 24, 20, 24, 8]
[8113, 64, 448, 304, 448, 244, 2128, 64, 448, 304, 1708, 64, 2128, 64, 448, 1159, 448, 64, 2128, 64, 1708, 304, 448, 64, 2128, 244, 448, 304, 448, 64]
[359775, 512, 7680, 4160, 7680, 2952, 62400, 512, 7680, 4160, 44280, 512, 62400, 512, 7680, 23985, 7680, 512, 62400, 512, 44280, 4160, 7680, 512, 62400, 2952, 7680, 4160, 7680, 512]

发现: 从一次以后,就可以分类了, 相同的持续相同,不同的持续不同

感觉上是和N的gcd有关, gcd相同的为一组

稍微证明, 前i个达到v,那么v开始得到的i+1的 kv % N, 有 gcd(kv%N,N) = gcd(kv,N), 是gcd(v,N)的倍数

那么归纳法,如果i次时,gcd相同的数的值一样,那么i+1次也显然就一样了

N 1e12 的话, gcd就都是它的约数, 第一轮算个矩阵, 后面矩阵快速幂

2*3*5*7*11*13*17*19*23*29*31*37 = 7420738134810 = 7e12

2^12 = 4096

但似乎 4096^3 log(k) 会超时?

重新考虑下

上面注意到i的值的和N的gcd只会增不会减, 考虑指定一些位置是贡献这些gcd的

剩下的就全是与N互质的数的乘积?

但这样的话, 其实并不可行, 因为比如6, 2 * 2 依然是gcd = 2

而对于12这种, 2 * 2 更难分配出现的位置

题解

$M=p_1^{q_1} p_2^{q_2} p_3^{q_3}\ldots$

对于每一组, 求$0\le a_i \le p^q -1, \prod_{i=1}^k a_i \equiv N \pmod {p^q}$

然后答案乘起来

emmmm, 为啥, 虽然一个数 如果满足每个组的要求,那么一定是一个满足题意的方案, 而每一个满足题意的,也一定满足每组的要求, 但为啥是方案数之乘积呢?

即是要证明

0<= x < p1p2

存在且唯一存在一个x满足

x = k1 mod p1

x = k2 mod p2

证

x1 != x2 但是都满足

有 x1-x2 = 0 mod p1, x1-x2 = 0 mod p2, 所以不可能存在两个不同解

x = (k1 p2 * (p2 在 mod p1 的逆元) + k2 p1 * (p1 在 mod p2 的逆元)) mod (p1p2)

显然是一个值, 且满足上述要求, 则是一个解

对于高次就是 孙子定理(中国剩余定理)

设 F(p,q,K,N) 是上面子问题(p,q) 的方案数

一样,先考虑次放q=1, 得到我那个都相等的结论 (p-1)^{k-1},

q > 1 时

要证明的性质是 可以把 p的幂次相等的一组方案数相等

同样是归纳,i时一样,i+1时也一样

比如 (p=3,q=3) mod 3^3

1
2
3
4
5
6
7
(1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26)

(3,6,12,15,21,24)

(9,18)

(0)

证明, 每个和它同组和比它组小的变成它的方法数一致, 得证, (感觉我应该 都得到了gcd有关,这个也可以得到的, 关键是没想到第一步的拆分

// 举例 , 3->12 可以 x4,13,22 , 而12–>3, 是x7,16,25… , (都是3个方案)

因此直接分组, 组之间关系, 就

math.log(10)/math.log(2) * 12 = 39.863137138648355

直接矩阵快速幂即可

然后注意有个坑, 是如果与998244353 有关,运算可能会 除以0, 但幸运的是998244353^2 > 1e12, 所以一定是一次方, 而一次方可以直接表达式

代码(矩阵快速幂)

https://atcoder.jp/contests/abc245/submissions/35055072

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
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
ll read(){ll r;scanf("%lld",&r);return r;}

int cp(ll &n, ll p) { // 计算 n包含是p的多少次方,并在n中除掉
  if (n == 0) return 1e9;
  ll e = 0;
  while (n % p == 0) {
    ++e;
    n/=p;
  }
  return e;
}

vector<pair<ll, ll>> factor(ll n) { // sqrt(1e12) = 1e6 暴力, {prime, power}
  vector<pair<ll, ll>> pe;
  for (ll i = 2;i*i<= n; ++i) if (n%i==0) pe.push_back({i, cp(n,i)});
  if (n > 1) pe.push_back({n, 1});
  return pe;
}

vector<vector<mint>> mul(const vector<vector<mint>>&m0, const vector<vector<mint>>&m1){
  auto r = vector(m0.size(),vector<mint>(m1[0].size(),0));
  rep(i,0,m0.size()) rep(j,0,m1[0].size()) rep(k,0,m0[0].size()) r[i][j] += m0[i][k] * m1[k][j];
  return r;
}

mint f(ll p, int e, ll k, ll n) { // k个数, % p^e == n
  vector<mint> x(e + 1); // x[pwr幂次] = 个数
  x[e] = 1; // 0
  x[e - 1] = p - 1; // k p^{e-1}
  per(i,0,e-1) x[i] = x[i + 1] * p; // k p^i
  // 有个坑 如果 (p-1)%998244353 == 0 或者 p%998244353 == 0, 那么x[c] 就是0, 无法除, 但幸运的是 这样的话e一定等于1
  // 而对于质数的1次方, 能直接推表达式 不需要矩阵乘法
  if(e == 1) return (n%p == 0)?(mint(p).pow(k) - mint(p-1).pow(k)) : (mint(p-1).pow(k-1));

  auto r = vector(1,vector<mint>(e+1,0));
  r[0][0] = 1; // [0]次有一个方案
  auto t = vector(e+1,vector<mint>(e+1,0));
  rep(i,0,e+1) rep(j,0,e+1) t[j][min(e,i+j)] += x[i]; // j次幂次 乘上i幂次 变为 i+j次幂次, 初始化矩阵
  while (k) {
    if(k&1) r = mul(r, t);
    t = mul(t,t);
    k/=2;
  }
  int c = min(cp(n, p),e);
  return r[0][c] / x[c];
};

int main() {
  ll k = read();
  ll n = read();
  ll m = read();;
  auto pe = factor(m);
  mint ans(1);
  for (auto [p, e] : pe) ans *= f(p, e, k, n);
  printf("%d\n",ans.val());
  return 0;
}

压缩版 https://atcoder.jp/contests/abc245/submissions/35055288

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
#include<bits/stdc++.h>
#include<atcoder/modint>
using mint=atcoder::modint998244353;
using namespace std;
using ll=long long;
#define rep(i,a,n)for(ll i=a;i<(ll)n;i++)
#define M(a,b) vector(a,vector<mint>(b,0))
ll g(ll&n,ll p){
  if(!n)return 64;
  ll e=0;
  while(n%p==0){
    ++e;
    n/=p;
  }
  return e;
}
template<class T>T mul(T&a,T&b){
  auto r=M(a.size(),b[0].size());
  rep(i,0,a.size())rep(j,0,b[0].size())rep(k,0,b.size())r[i][j]+=a[i][k]*b[k][j];
  return r;
}
mint f(ll p,ll e,ll k,ll n){
  vector<mint>x(e+1);
  x[e]=1;
  x[e-1]=p-1;
  for(ll i=e-1;i-->0;)x[i]=x[i+1]*p;
  if(e==1)return n%p?mint(p-1).pow(k-1):mint(p).pow(k)-mint(p-1).pow(k);
  auto r=M(1,e+1),t=M(e+1,e+1);
  r[0][0]=1;
  rep(i,0,e+1)rep(j,0,e+1)t[j][min(e,i+j)]+=x[i];
  while(k){
    if(k&1)r=mul(r,t);
    t=mul(t,t);
    k/=2;
  }
  ll c=min(g(n,p),e);
  return r[0][c]/x[c];
}
int main(){
  ll k,n,m;
  cin>>k>>n>>m;
  mint r=1;
  for(ll i=2;i*i<=m;++i)if(m%i==0)r*=f(i,g(m,i),k,n);
  if(m>1)r*=f(m,1,k,n);
  printf("%d\n",r.val());
  return 0;
}

总结

G

第二次遇到 dij 中使用长0的边!!!, 第三大的颜色不会贡献 倒是我自己能想到

Ex

数论 的拆的想法有,但是这之间的计数关系完全不熟

官方答案还有个推组合数的,学不会

虽然这个可以矩阵快速幂,据说还有 BM线性递推 没学过

参考

官方题解

bilibili dls

Berlekamp_Massey 算法

BM