Pinely Round 1

發表於 更新於 分類於 ， Disqus： 文章字數： 3.4k 所需閱讀時間 ≈ 11 分鐘
D(数数)E(图论)F(数学,智慧,TODO)G(TODO)

https://codeforces.com/contest/1761

D. Carry Bit

f(x,y) = g(x)+g(y)-g(x+y)

其中g(x) = x二进制下的bit为1的个数

问 $f(x,y) = k$ 有多少个, 其中 $x,y \in [0,2^n)$, 答案mod 1e9+7

范围

n < 1e6

1s

256mb

我的思路

打了表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 4
0 0 1 1 0 0 2 2 0 0 1 1 0 0 3 3
0 2 1 2 0 3 2 3 0 2 1 2 0 4 3 4
0 0 0 0 1 1 1 1 0 0 0 0 2 2 2 2
0 1 0 3 1 2 1 3 0 1 0 4 2 3 2 4
0 0 2 2 1 1 2 2 0 0 3 3 2 2 3 3
0 3 2 3 1 3 2 3 0 4 3 4 2 4 3 4
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 2 0 1 0 4 1 2 1 3 1 2 1 4
0 0 1 1 0 0 3 3 1 1 2 2 1 1 3 3
0 2 1 2 0 4 3 4 1 3 2 3 1 4 3 4
0 0 0 0 2 2 2 2 1 1 1 1 2 2 2 2
0 1 0 4 2 3 2 4 1 2 1 4 2 3 2 4
0 0 3 3 2 2 3 3 1 1 3 3 2 2 3 3
0 4 3 4 2 4 3 4 1 4 3 4 2 4 3 4

推了个 多项式的矩阵幂次, 然而 赛后才知道, 1e9+7 就是不希你用ntt因为原根极小等于没有

1
2
3
4
5
(1,0)
      (3, x)^n
      (1,3x)
            (1)
            (1)

题解

类似的, 可以dp

dp[n][上半0/下半1][k] 表示 [0..2^n) 里, 上半/下半 中=k个个数

dp[n][0][k] = 3dp[n-1][0][k] + dp[n-1][1][k]

dp[n][1][k] = 3dp[n-1][0][k-1] + dp[n-1][1][k-1]

ans = sum dp[n][0,1][k]

显然是一个O(nk)的dp, 1e6 过不了

a[i] 表示a的第i个bit

b[i] 表示b的第i个bit

然后 其实 carry bit 意译为 进位, 其实 定义上意义是 运算发生的进位的次数

1,1 的话, 始终进位 不用关心后面的

0,0 的话, 始终不进位 不用关心后面的

(0,1), (1,0) 的话, 也就是需要后面连着 一串 (0,1) (1,0) 然后接上一个(1,1)

然后就((0 and 1)* , (1,1)), ((0 and 1)* (0,0)) 注意的是最右可以放不是(0,0)结束的

但这样实际上并不好算, 考虑把进位的连续的看作整体

这样, 连续进位一段的最右是(1,1), 中间3种方案

这样, 连续不进位一段的最右是(0,0), 中间3种方案, (最右特殊

那么就是 有多少个进位与不进位的 分界点, 这些位置只有1个方案, 其它都是3个方案

负1位看作不进位,

所以枚举q个分界的位置, 那么剩下的有$3^{n-q}$个方案

也就是 (q+1)/2 个连续进位, 和 q+1-(q+1)/2个连续的不进位

那么就是把k个进位 放在连续的进位段, 和n-k个不进位放在连续的不进位段, 每段至少一个

代码

https://codeforces.com/contest/1761/submission/182043486

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int 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-->(ll)a;)
int read(){int r;scanf("%d",&r);return r;}
 
ll mypow(ll v,int pwr){
  if(pwr<0) return 0;
  ll ret=1;
  while(pwr){
    if(pwr&1) (ret*=v)%=MOD;
    (v*=v)%=MOD;
    pwr/=2;
  }
  return ret;
}
 
const int N = 1000000;
ll fac[N+10]={1};
ll ifac[N+10];
 
ll binom(int n,int m){
  return (m>n || m<0)?0:(fac[n]*ifac[m]%MOD*ifac[n-m]%MOD);
}
 
int main(){
  int n=read();
  int k=read();
  rep(i,1,N+1) fac[i]=fac[i-1]*i%MOD;
  ifac[N]=mypow(fac[N],MOD-2);
  per(i,0,N) ifac[i]=ifac[i+1]*(i+1)%MOD;
  ll ans=0;
  if(k==0){
    ans=mypow(3,n);
  }else{
    rep(q,1,n+1){ // q个变化
      int one=(q+1)/2; // k个进位
      int zero = (q+2)/2; // n-k+1个不进位(包含-1位)
      (ans+=mypow(3,n-q)*binom(k-1,one-1)%MOD*binom(n-k+1-1,zero-1)%MOD )%=MOD;
    }
  }
  printf("%lld\n",ans);
  return 0;
}

E. Make It Connected

n点简单无向图, 让图联通

任意次操作:

每次操作 选一个点u, 颠倒所有和(u,v)的连接状态(也就是 原来连接变不连接, 原来不连接变链接)

求一个方案

范围

1s

512mb

n 4000

我的思路

显然 翻转操作不要求顺序性, 其实是问选点集S, 改变 这些点和 (所有点-S) 之间的边

显然可以看成多个联通块

显然选一个最小的联通块的所以点作为S是一个方案

1
1-2-3 4-5-6

然而 上面 选择3 的话 可以3-(1,4,5,6) 只用选1个

如果有一个独立点, 选它即可, 否则任何联通块点数 >= 2

按照这个角度的话, 如果任何连通块的话里有两个点没有直接相连, 那么就可以 选其中一个, 就是解

否则的话 每个联通块内部都是两两相连

= 2个联通块的 有1个点的 方案吗?, 有2个点的方案吗?

显然 1个点不行, 选它会让和原来联通块分离

2个点: 两个点来自一个连通块, 同样的, 会让和原来的联通块分离

2个点: 两个点来自不同的连通块, 如果联通块个数>=3 显然可以, 因为它们 分别连上对面的块, 和其它块

如果 联通块个数为2的话, 只有选小的联通块, 似乎就没了

然后炸了, wa 4,

1
2
3
4
5
6
7
8
7
0100000
1000000
0001110
0010100
0011000
0010001
0000010

问题在于 连通时 非连通的点的选择上, 例如 1-2-3-4 ,不能选择2, 这样会把1和3-4切断

也就是选的点 做了颠倒后和分别的连通连通, 换句话说 u 和拆了以后的剩下的多个连通块 都不是满联通关系

比如这种 虽然d会让图不连通, 但是又会连上a和f, 也是可以的

1
2
3
4
5
  b   e
 / \ / \
a   d   f
 \ / \ /
  c   g

证明 最小度的点可以满足,

设 u 是一个非法点, u拆了以后, 剩下一个连通点集 都和u相连

u (v0...vi) (v...)

u和所有点连, 一定不是最小度, 否则u不合所有点连 所以 那么有 u的度 = v集合的大小 + (>=1 一定还有其它点)

而v点集内的一定度 <= v集合的大小, 所以 du[u] > du[v]

证明了一个非法点 一定有du比它晓得点, 逆否命题得证

代码

https://codeforces.com/contest/1761/submission/182054992

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}

int n;

char s[4010][4010];

void dfs(int u,vector<int>&a, vector<bool>&vis){
  vis[u]=true;
  a.push_back(u);
  rep(v,0,n) if(v!=u && s[u][v]=='1' && !vis[v]) dfs(v,a,vis);
};

void w(){
  n = read();
  rep(i,0,n) scanf("%s",s[i]);
  vector<bool> vis(n);
  vector<vector<int>> connect;
  rep(i,0,n) if(!vis[i]) {
    vector<int> a;
    dfs(i,a,vis);
    connect.push_back(a);
  }
  if((int)connect[0].size() == n){ // 全部一起
    printf("0\n");
    return ;
  }
  for(auto &b:connect) if((int)b.size()==1){ // 独立点
    printf("1\n");
    printf("%d\n",b[0]+1);
    return ;
  }
  for(auto &b:connect) { // 同一个连通块中 最小的du
    pair<int,int> du_u = {b.size()-1,b[0]}; // {du,u}
    for(auto u:b) {
      int du=0;
      for(auto v:b) du+= s[u][v]=='1';
      du_u=min(du_u,make_pair(du,u));
    }
    if((int)du_u.first != (int)b.size()-1){
      printf("1\n");
      printf("%d\n",du_u.second+1);
      return ;
    }
  }
  // 所有联通块 点数 >= 2, 联通块个数 >= 2, 所有联通块内部互连
  if(connect.size() >= 3){
    printf("2\n");
    printf("%d %d\n",connect[0][0]+1,connect[1][0]+1);
  }else{// 两个联通块
    if(connect[0].size() > connect[1].size()) swap(connect[0],connect[1]);
    printf("%d\n",(int)connect[0].size());
    for(auto u:connect[0]) printf("%d ",u+1);
    printf("\n");
  }
}

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

F1,F2. Anti-median

2m+1 长的数组, 如果 sort以后 正中的是同一个数值, 那么称作bad

对于一个部分给定的 1~n 的排列, 问有多少中填写方式 让它的所有奇数长度子数组(长度>=3) 非bad

范围

n 1000(F1), 1e6(F2)

2s

256mb

我的思路

考虑 小的情况, 比如5个非法 是否3个非法

然而1 4 3 5 2, 中间的4 3 5 是合法的

但考虑到3个a b c, 考虑 中间填大于小于号, 发现 要么a>b<c 要么a<b>c

说明 整个数列也是 一大一小的间隔就可以 满足所有长3的子序列了

考虑长5的序列 a<b>c<d>e, 这种的话, 显然c < a 或者c < e

a<b>c<d>e<f>g<h>i, 长一点, 还是考虑长5

若 c < e, 那么必须 e < g, 从而 g < i,

换句话说, 小于关系中, 存在一个a[i-2] > a[i] < a[i+2],(a[i-1] > a[i] < a[i+1]), 然后向两侧, 都是 >符号和 <符号, 大概> > > < < <的形状

对a[i-1] < a[i] > a[i+1] 的来说, 同样存在 < < < < > > > > 的关系

所以是这样的形状

1
2
3
4
5
6
7
8
9
        x
      x   x
    x       x
  x          x
x          x
 x       x
   x   x
     x

问题: 7个呢,9个呢…

注意到 中间的子数组 依然满足这个形状, 只要证明这个形状的全长始终合法即可

其实注意到 如果 < < < > > > 中< < <中的, 那么 左侧的全小于它, 只有右侧全大于它才可能, 其它3种情况 对称 显然

所以 所有奇数个都合法

问题变成, 构建这种 错开的峰 谷 形状

那么关心最大最小值的位置, 那么左右就是不相关的 两串 单调递增 序列,

两串 单调递增 1 ....... n, 1 ....... n, 中间有一些点的值被确定了

这样很好算, 找第一小的binom(c, 间隔), 第二小binom(剩下个数, 间隔) … 乘起来就行了

每个都是 binom(v[i]-1-used[i-1], 间隔)

used[i-1] 注意到 如果比它小的来自两侧, 那么used[i-1] 不会变, 而如果单测 就有关

1
2
3
v0       v1
   x   x
     x

间隔类似的, 如果间隔始终在 右侧序列里, 间隔不会变, 如果在序列间 就会变

所以有不少的 方案之间 中间的binom是不会变的, 变的都是两头的

但具体咋讨论, 并不会

题解

也是 先 考虑3个的一样的结论,(这里 用了局部最大 描述

然后也是 考虑5个, 一样的结论

如果 偶数项 局部最大, 那么有 偶数项先增后减, 奇数项先减后增

如果 奇数项 局部最大, 那么有 奇数项先增后减, 偶数项先减后增

然后 奇偶情况, 都是按照形状,考虑放成一个环(!!!),

dp[l][r] = 最大的 (r-l+1)个放在[l..r] 的方案数, 就可以n^2 dp了, (F1 可做)

考虑 放n的位置, 然后从大向小放, 对于环来讲, 每次拼在左侧或者右侧

但这样的顺序 并不能保证 满足题目 , (填写的时候一侧折反回来 , 导致没有局部性

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

什么情况呢 就是上面这种折反, 也就是 值从大到小的前缀[5..9], 奇数个的个数(7,6,5:3个) 大于 偶数的个数(9,8:2个)

作为后缀同理

另一个观察, 如果确定x的位置, 那么 值x..n 的放置 要么在x左侧连续, 或者右侧连续, (在环上显然)

于是变成状态转移, x[i]..n 的一个状态, 转移到 x[i-1]的一个状态, 而 这两个x就是 已知的相邻的值 对应的状态

看成(0,0) 向右和向上移动 走到(a,b), 不要跨过某个 x=y+c 的线 的统计

其中 (a,b) 表示的是 a个偶项,b个奇项, 而不是n的左右, 这样的话

对于[x..n] 在x左侧 的话, a,b 是与n的具体位置无关的!

对于[x..n] 在x右侧 的话, a,b 是与n的具体位置无关的!

且注意到n 和最大已知 所覆盖的连续段, 不会有其它的已知, 所以初始状态计数好了, 向下就容易转移,O(n)可搞

代码

TODO

1
2
3
4
5
6
7
// 奇偶 变换 => arr
ans = 0
for n 在 奇/偶
  for n在 次大值 左/右
    for i = 已知 从大到小
      f[i] = f[i+1] * 转移
    ans += f[1]

总结

状态极差(a题写了个 a==b==n 找了一年bug) + 脚本炸了(修了半天脚本), -169 分

D

给 1e9+7 就是不希望用 ntt

我英语太菜, 完全没去考虑实际意义, 只会打个表..

数数好难啊(不是

E

这E比D简单很多啊, 自己想出来了…

F1, F2

果然也是从小开始考虑 3个 5个,

然后这个不管 奇偶 都是变成环(!!!!!!!!!!)再考虑, 啊 没想到, 啊 为啥我想不到呢, 事后看又觉得变环很自然, 没有智力

其实 强写 也是有 渺茫的可能, 问题就在如何把这 反复存在的奇偶给搞定合在一起

还有后面这个 放置, 说明 上面我想的binom还是有问题, 也是这种折反一圈导致的问题, 还是没有想到折反导致的问题 的特例情况

然后就是这里 考虑连续段的想法, 虽然 我有想到 一个确定到一个确定 之间的变化, 但是没有去想每一步的变化(!!!!!!), 而直接跳步了, 如果能注意到每一步的变化都是连续一段, 也许就更容易反应出需要转化成环了

G

参考

官方