Atcoder abc271

發表於 更新於 分類於 ， Disqus： 文章字數： 2k 所需閱讀時間 ≈ 7 分鐘
G(概率论,矩阵)Ex(构造)

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

G - Access Counter

给定 长24的C

如果 Ci==T, 甲 X % 可能访问

如果 Ci==A, 乙 Y % 可能访问

超过的C看作循环

好的状态 = 甲不是第N次方案的

求好的状态的 概率 mod 998244353

范围

n 1e18

x,y [1,99]

|c| == 24

2s

1024mb

我的思路

先最无脑的

dp[i][j] = 第i个被访问, 且是第j次 的概率

dp[i][j] = dp[k < i][j-1] * prod p[k+1..i-1] 不被访问 p[i]

ans = sum dp[i是乙][n]

然而是个无限的求和

要干掉无限

那么换个角度

dp[j][idx] 第j次访问, 位置在C[idx] 的概率

dp[j][idx] = dp[j-1][i=0..23] * p[i->idx] 从i开始下一次访问idx, 中间不访问其它的概率

这里把dp[j] 看成一个向量, p与j无关的常系数矩阵, 不就是矩阵快速幂了!

所以如何算p[pos0 -> pos1]

直接走到 = prod(1-p[pos0+1..pos1-1]) * p[pos1]

绕一圈走到 = prod(1-p[pos0+1..pos1-1]) * prod(1-p[...]) * p[pos1]

绕两圈走到 = prod(1-p[pos0+1..pos1-1]) * prod(1-p[...])^2 * p[pos1]

综上 = prod(1-p[pos0+1..pos1-1]) * p[pos1] * 1/(1-prod(1-p[...]))

问题来了, 如果分母为0 怎么办?

代码

https://atcoder.jp/contests/abc271/submissions/35941851

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
65
66
67
68
69
70
71
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
ll read(){ll r;scanf("%lld",&r);return r;}

namespace MatrixVec{
  template<class T>
    vector<vector<T>> mul(const vector<vector<T>>& a,const vector<vector<T>>&b){// 矩阵乘法
      auto n=a.size();
      if(n==0)return {};
      auto K=a[0].size();
      assert(K==b.size());
      int m=0;
      if(K)m=b[0].size();
      auto r=vector(n,vector<mint>(m,0));
      rep(i,0,n)rep(j,0,m)rep(k,0,K)r[i][j]+=a[i][k]*b[k][j];
      return r;
    }

  template<class T>
    vector<vector<T>> pow(vector<vector<T>> a,ll pwr){ // 矩阵幂次
      auto n=a.size();
      if(n==0)return {};
      assert(n==a[0].size());
      auto r=vector(n,vector<T>(n,0));
      rep(i,0,n)r[i][i]=1;
      while(pwr){
        if(pwr%2)r=mul(r,a);
        a=mul(a,a);
        pwr/=2;
      }
      return r;
    }

};

char c[30];
mint p[30];

int main(){
  ll n = read();
  mint x = read();
  mint y = read();
  scanf("%s",c);
  int m=strlen(c); // 24;
  rep(i,0,m) p[i] = (c[i]=='T'?x:y)/100;
  auto M = vector(m,vector<mint>(m,0));
  mint t = 1;
  rep(i,0,m) t *= (1-p[i]);
  assert(t!=1); // ?
  t = (-t+1).inv();
  rep(i,0,m)rep(j,0,m){ // 综上` = prod(1-p[pos0+1..pos1-1]) * p[pos1] * 1/(1-prod(1-p[...]))`
    M[i][j] =p[j]*t;
    rep(k,1,m) {
      if((i+k)%m==j)break;
      M[i][j] *= -p[(i+k)%m]+1;
    }
  }
  auto ret = MatrixVec::pow(M,n);
  auto row = vector(1,vector<mint>(m,0));
  row[0][m-1] = 1;
  auto col = vector(m,vector<mint>(1,0));
  rep(i,0,m) if(c[i]=='A') col[i][0]=1;
  printf("%d\n",MatrixVec::mul(MatrixVec::mul(row,ret),col)[0][0].val());
  return 0;
}

Ex - General General

t 个测试

棋子在(0,0)

受限制的八邻移动, 要移动到(A,B) 求最小操作次数, 或无法实现

其中限制通过 0/1 串 s给出, 如果s[i] 则可以执行对应移动, 下面是s的下标和(x,y) 的关系, 

1
2
3
4
5
6
7
8
9
(x,y)

 y

 1  4 3 2
 0  5 s 1
-1  6 7 8

 x -1 0 1

范围

t 1e4

a,b [-1e9,1e9]

5s

1024mb

我的思路

看起来是构造贪心一类的

又像线性规划

t…. = A

t…. = B

xi >= 0

min sum xi

最大的问题是 xi不能为负数 , 所以似乎不能简单的判断是否和(A,B)线性相关, 当然如果线性无关, 那么肯定不行

一般化 不妨通过旋转 让A,B非负数

那么 考虑(X,0) 这样的, 如果有(1,0) 那么就选它

否则至少需要有 (1,-1) 或 (1,1)

这样讨论下去也不是个办法

再换个角度, 最多会用到多少个移动

首先 对称的一定不会用,因为这样的移动会抵消掉

所以至多四个

而如果有3邻用了, 那么其实等价于 两边的变成用中间的, 所以不需要任何3临的使用

所以 如果 即是用了4个, 又没有3邻的使用, 从对称关系上讲只有一种情况:

1
2
3
  x x
x s
    x

而这等价于 (+1,+1) = 正上方

综上 其实最多同时用3个

现在问题变成 在限制内, 同时用3个是否有可能达到(A,B), 最小使用个数

启发式??

题解

只考虑

  1. 一种/两种移动
  2. 两个对角 + 一个沿坐标轴的一次

证明

还是考虑通过替换下降种类

1
2
3
4 3 2
5 s 1
6 7 8

首先对称不会选, 如果不选 坐标轴方向, 那么 最多选两个

考虑1必选

(坐标x2+对角)1+3+2 = 2+2, 不会出现对角三连

(坐标x2+对角)1+3+8 = 1+1, 不会出现这种组合

(坐标x2+对角)1+3+6 = 空, 不会出现这种组合

综上 不会出现选(两个坐标向+一个对角向的)

(坐标+对角x2)1(>1)+2+4 = 1(-2)+2(+1)+4(-1), 所以 对角 + 坐标轴, 坐标轴最多一次

(坐标+对角x2)1(>1)+4+6 = 1(-2)+4(-1)+6(-1), 所以 对角 + 坐标轴, 坐标轴最多一次

其实最多一次直接认为使用一次, 否则就是用两个

对于用两个来说, 一定不会对称的两个, 所以一定线性无关, 直接解线性方程, 看是否非负

代码

https://atcoder.jp/contests/abc271/submissions/35944649

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
ll read(){ll r;scanf("%lld",&r);return r;}
using Arrow=pair<ll,ll>;

namespace MatrixVec{
  // 行列式 高斯消元 解增广矩阵, 答案全为整数
  // {是否成功, 消元后的增广矩阵(左边nxn 为单位矩阵)}
  pair<bool,vector<vector<ll>>> solvell(const vector<vector<ll>>& _a){
    auto a=_a;
    auto n=a.size(); // 行
    if(n==0) return {true,{}};
    assert(n < a[0].size()); // 增广
    rep(j,0,n){
      rep(i,j,n)if(a[i][j]!=0){ // >=j行中找j列首个非零值,做行交换
        if(i!=j) std::swap(a[i],a[j]);
        break;
      }
      if(a[j][j]==0) return {false,{}};
      per(k,j,a[j].size()){ // 保证答案全为整数, 注意顺序
        if(a[j][k] % a[j][j] !=0) return {false,{}};
        a[j][k]/=a[j][j];
      }
      rep(i,0,n) if(i!=j)per(k,j,a[i].size())a[i][k]-=a[i][j]*a[j][k]; // 行变换, 注意per顺序
    }
    return {true,a};
  }
};

vector<Arrow> XY={
  {1,0},
  {1,1},
  {0,1},
  {-1,1},
  {-1,0},
  {-1,-1},
  {0,-1},
  {1,-1},
};

const ll INF=0x3f3f3f3f3f3f3f3f;

char s[10];

ll solve1(Arrow xy,Arrow ab){
  auto [x,y] = xy;
  auto [a,b] = ab;
  if(x*b!=a*y) return INF; // a/x == b/y
  ll res = (x==0?b/y:a/x);
  return res>=0?res:INF;
}

ll solve2(vector<vector<ll>> mat){
  auto [ok,res] = MatrixVec::solvell(mat);
  if(!ok) return INF; // 无整数解
  ll a = res[0][2];
  ll b = res[1][2];
  return (a>=0 && b>=0)?a+b:INF;
}

void w(){
  ll a= read();
  ll b= read();
  scanf("%s",s);
  if(!a && !b) {
    printf("0\n");
    return ;
  }
  vector<Arrow>op;
  rep(i,0,8) if(s[i]=='1') op.push_back(XY[i]);
  ll ans = INF;
  for(auto o:op) ans = min(ans,solve1(o,{a,b}));
  rep(i,0,op.size()) rep(j,i+1,op.size()){
    auto [x0,y0] = op[i];
    auto [x1,y1] = op[j];
    if(x0+x1==0 && y0+y1==0) continue; // 不会取逆向
    ans = min(ans, solve2({
          {x0,x1,a},
          {y0,y1,b},
          }));
  }
  rep(k,0,op.size()){
    auto [x,y] = op[k];
    if(abs(x)+abs(y) != 1) continue; // 使用一次的轴向边
    rep(i,0,op.size()) rep(j,i+1,op.size()){
      auto [x0,y0] = op[i];
      auto [x1,y1] = op[j];
      if(x0+x1==0 && y0+y1==0) continue; // 不会取逆向
      ans = min(ans, 1+solve2({
            {x0,x1,a-x},
            {y0,y1,b-y},
            }));
    }
  }
  printf("%lld\n",ans==INF?-1:ans);
}

int main(){
  int t=read();
  while(t--)w();
  return 0;
}

总结

G

没啥难的, 主要在 分母不会为0的问题上

似乎可以暴力一下 反正x,y ,[1,99] 然后 (1-px)^t * (1-py)^{24-t} 的所有值 都不为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
MOD=998244353

def qp(v,pwr):
    r = 1
    while pwr != 0:
        if pwr % 2 :
            r = (r*v)%MOD
        v = (v*v)%MOD
        pwr//=2
    return r

def inv(v):
    return qp(v,MOD-2)

inv100 = inv(100)

for x in range(1,100):
    for y in range(x,100): # y > x
        pnotx = 1-x*inv100
        pnoty = 1-y*inv100
        for t in range(24):
            v = qp(pnotx,t) * qp(pnoty,24-t) % MOD
            print(x,y,t,v)
            assert(v!=1)

Ex

把8种 向下降 考虑同时使用的方向没问题, 但是 止步于3种了, 没能再下降

这里怎么分类也是 感觉很事后诸葛

参考

官方题解