Codeforces Round 803

發表於 更新於 分類於 ， Disqus： 文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘
F(数学,数组,相邻无序对)G(GF(2),meet in middle,不懂证明)

F

https://codeforces.com/contest/1698/problem/F

给长度n的数组A和B

每次可以选择A数组中值相等两个数,把它们中间的区间颠倒顺序

求$n^2$次数内的方案得到B

范围

n 500

1s

256MB

题解

我的思路

没有思路

只知道首个和末个 有重复的数字的一定位置不会变,且它们两侧的也不会变

但如何记录翻转并不知道

可行的话, 首先每个值个数要一样

题解

数组不变量

首先a1和an是不会变的

然后是相邻元素构成无序对不变, 因为 区间 v…v颠倒,那么 中间和v连接的依然和v连接

必要显然

充分性, 我们具体构造

假设 前缀 a[..i] 和 b[..i] 相同, a[i] = x

a[i+1] = y

b[i+1] = z

如果存在 a[i..] = [x,y,...,z,x,...] 那么直接翻转 做1次

如果 a[i...] = [x,y,...,x,z,...], 如果 x,z 右侧还有x 则翻转2次

否则 x,z 的x是最后出现的x, 所以, x至少2个

如果x恰好2个, 且是连着 a[i..]= [x,y,x,z,...], b[i..] = [x,z,....y,x,y,...] , 这样转b

否则a[i..] 中 x相邻至少3对相邻

那么根据上面的,只有最后的那一个x的右侧不能通过,x本身交换 完成, 而a和b的操作是对称的

所以 3对中 最多2对无法交换,所以总存在一个相邻,可以0~2次 完成换到a[i..] = [x,?,...]

即只要满足,无序对的性质

那么a[0..i] 一致了 就有办法让b[0..i] 一致

直接暴力找 O(n^2)

注意到的是算法实际的次数是不超过4n的

而需要的是小于$n^2$的次数,所以考察 n=[1..4]的合法的数组的操作次数时候

n=1 0次

n=2 0次

n=3 0次

n=4 0次/1次

所以也满足次数要求

代码

https://codeforces.com/contest/1698/submission/162605498

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#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;)

int read(){int r;scanf("%d",&r);return r;} // read

int n;
int a[510];
int b[510];

// 翻转区间
void rev(int *arr,int i,int j){
  rep(k,i,j+1){
    int rk = j-(k-i);
    if(rk < k)break;
    swap(arr[k],arr[rk]);
  }
}

// 找arr[sti...]中 找 [x,y,...,z,x,...], 翻转成[x,z...]
bool op(int *arr,int sti,int z,vector<pair<int,int>> & ans){
  int x = arr[sti];
  rep(i,sti+1,n){
    // [x,y........z,x]
    // [sti............i]
    if(arr[i] == x && arr[i-1] == z){
      rev(arr, sti+1,i-1);
      ans.push_back({sti+1,i+1});
      return true;
    }
  }
  return false;
}

// 找arr[sti...]中 找 [x,y,...,x,z,...,x,...], 翻转成[x,z...]
bool oprev(int *arr,int sti,int z,vector<pair<int,int>> & ans){
  int x = arr[sti];
  rep(i,sti+1,n){
    // [x,y........x,z,.....x]
    // [sti..........i      j]
    if(arr[i] == z && arr[i-1] == x){
      rep(j,i+1,n){
        if(arr[j] == x){
          rev(arr, sti+1,j-1);
          ans.push_back({sti+1,j+1});
          return op(arr,sti,z,ans);
        }
      }
      return false;
    }
  }
  return false;
}

void w(){
  n = read();
  rep(i,0,n) a[i] = read();
  rep(i,0,n) b[i] = read();
  if(a[0] != b[0]) {
    printf("NO\n");
    return ;
  }
  if(a[n-1] != b[n-1]){
    printf("NO\n");
    return ;
  }
  vector<pair<int,int>> pa;
  rep(i,1,n){
    int u = a[i-1];
    int v = a[i];
    if(u > v) swap(u,v);
    pa.push_back({u,v});
  }
  vector<pair<int,int>> pb;
  rep(i,1,n){
    int u = b[i-1];
    int v = b[i];
    if(u > v) swap(u,v);
    pb.push_back({u,v});
  }
  sort(pa.begin(),pa.end());
  sort(pb.begin(),pb.end());
  if(pa != pb){
    printf("NO\n");
    return ;
  }
  printf("YES\n");
  // 一定可以
  // -------------
  vector< pair<int,int> >ans; // 正向
  vector< pair<int,int> >revans; // 反向
  rep(i,0,n){
    if(a[i] != b[i]){
      int x = a[i-1];
      //
      if(op(   a,i-1,b[i],ans))continue;
      if(oprev(a,i-1,b[i],ans))continue;
      if(op(   b,i-1,a[i],revans))continue;
      if(oprev(b,i-1,a[i],revans))continue;
      int w = -1; // 找既不等于 b[i] 也不等于a[i]的 x相邻的, 至少存在一个
      rep(j,i+1,n){
        if(a[j] == x){
          if(a[j-1] != a[i] && a[j-1] != b[i]){
            w = a[j-1];
          }else if(a[j+1] != a[i] && a[j+1] != b[i]){
            w = a[j+1];
          }
          assert(w!=-1);
          break;
        }
      }
      assert(w!=-1);
      if(!op(a,i-1,w,ans)){
        assert(oprev(a,i-1,w,ans));
      }
      if(!op(b,i-1,w,revans)){
        assert(oprev(b,i-1,w,revans));
      }
    }
  }
  per(i,0,revans.size()) ans.push_back(revans[i]);
  printf("%d\n",(int)ans.size());
  for(auto [u,v]:ans){
    printf("%d %d\n",u,v);
  }
}

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

G

S 是长度n的0/1串

让S与任意个S的任意正位移 做xor

求 结果中1的个数恰好2个,且字符串表示下字典序最大的串中, 这两个1的位置

限制

n 35

2s

256MB

题解

我的思路

显然 第一次取S

然后把首个1以后的内容 的 首个1与S的首个1对齐 做xor, 直到后续剩余的只有1个1

这样的话,S的首个1和末个1各贡献一次, 位置就可以算了

为了简化运算,可以预处理掉S的前后缀0记录下来

然而n有35, 虽然无法估计精确复杂度,但这样做上限是2的35次方会超时,写出来也果然tle 6 了

官方

多项式问题

首先 忽略S前后缀0, 这些零在最后的结果中会加回来

那么把S看作在GF(2)域中多项式P(x)

Galois Field, 只有0,1二元及+（异或运算）×（与运算）

那么要求的是$P(x)Q(x) = x^k+1$ 的最小k

P(x)的常数项是1, Q是任意的, 所以一定存在

证明, 显然 $x^k$ 随着k增大$x^k \mod P(x)$ 成周期,且始终不为0, 那么周期的就是一个$x^k \mod P(x) = 1$的解

所以$k \le 2^{35}$ 依然很大

要用的方法是meet in middle?

emmmmm 就是直接除 然后meet in middle?

我没懂 这个prod 为何一定是 mod 为1, 以及GF(2)域上的相关性质

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
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
#define all(x) (x).begin(), (x).end()

int n;
char s0[100];
ll mod;

// (i*j)%mod in GF(2)
ll mul(ll i, ll j) {
  ll res = 0;
  rep(x, 0, n-1) {
    if (i & (1LL << x)) res ^= j;
    j <<= 1;
    if (j & (1LL << (n - 1))) j ^= mod; // 取mod in GF(2)
  }
  return res;
}

// (2**i)%mod in GF(2)
ll pow2(ll pwr) {
  ll res = 1; // result
  ll b = 2; // base
  while (pwr) { // pwr
    if (pwr & 1) res = mul(res, b);
    b = mul(b, b);
    pwr >>= 1;
  }
  return res;
}

// v的二进制最高位1在2的多少幂次, high1(3) = 1
int high1(ll v){
  int leadz = __builtin_clzll(v); // x 前缀0个数
  return 63 - leadz;
}

int main() {
  char *s = s0;
  scanf("%s",s);
  n = strlen(s);
  vector<int> pos; // 只用来判断 <= 2的1
  rep(i,0,n){
    if (s[i] == '1') pos.push_back(i+1);
  }
  per(i,0,n) { // remove trailing zero
    if(s[i] != '0') break;
    s[i] = 0;
  }
  rep(i,0,n) { // remove prefix zero
    if(s[0] != '0') break;
    s++;
  }
  int offset = s - s0; // 前导0
  n = strlen(s);
  if (pos.size() == 0) { // all zero
    printf("-1\n");
    return 0;
  }
  if (pos.size() == 1) { // only 1 of 1
    printf("%d %d\n",pos[0],pos[0]+1);
    return 0;
  }
  if (pos.size() == 2) { // 恰好2个
    printf("%d %d\n",pos[0],pos[1]);
    return 0;
  }
  rep(i, 0, n) { // 正向和逆向结果一样的
    if (s[i] == '1') mod |= (1LL << i); // s.trim().tobinary()
  }
  printf("s: %lld\n",mod);

  int h = (n + 1) / 2; // 半长

  ll val = mod;
  ll prod = 1; // (2**h(x)-1)(2**h(x))**(pwr-1)
  rep(x, 3LL, 1 << h) { // GF(2)乘法还满足结合率
    if (!(x & 1)) continue; // x 末位是1
    int pwr = 0; // val = x^pwr * ... 相当于 计算GF(2) 中 val的因子和幂次
    while (true) {
      ll curr = val;
      ll other = 0;
      rep(bit, 0, n) {
        if (!(curr & (1LL << bit))) continue;
        curr ^= x << bit;
        other ^= 1LL << bit;
      }
      if (curr)  break;
      // val = x * other in GF(2)
      printf("%lld = %lld * %lld\n", val, x, other);
      val = other;
      pwr++;
    }
    if (pwr) { // x的pwr次方
      printf("=> %lld ** %d\n",x,pwr);
      printf("high1[%lld] =  %d\n",x,high1(x));
      // prod *= (10-1) * 10 * 10 ,        3**3
      prod *= (1LL << high1(x)) - 1;
      rep(y, 1, pwr) prod *= 1LL << high1(x);
    }
  }
  // val 的 一次方
  if (val > 1) prod *= (1LL << high1(val)) - 1;
  // mod => GF(2) => 基的幂次 乘积 => (2的幂次)的幂次和2的(幂次-1) 的 积

  ll ans = 1LL << 60;
  // printf("prod:%lld\n",prod);
  assert(pow2(prod) == 1); // 2**prod ???????????????????????????????????????????
  for (ll x = 1; x * x <= prod; x++) { // 长度一定是prod的因子 ????????????????????????????????
    if (prod % x ) continue;
    if (pow2(x) == 1) ans = min(ans, x);
    if (pow2(prod / x) == 1) ans = min(ans, prod / x);
  }
  printf("%d %lld\n",offset+1,offset+ans+1);
}

总结

F

这个交换性质 厉害了,之前并不了解,也没有自己推出

相等的位置的交换,必定让相邻无序对是不变的,而且是充要条件

还是不变量的思考

G

GF(2) 真的没有系统学过

通过这个题看起来 乘法还 满足 结合率

加减也是对称的 A+B= C, A-B=C

参考

官方

洛谷 GF(2)