Codeforces Round 740

發表於 2021-08-25 更新於 2024-10-23 分類於 Codeforces ， Div1 Disqus：文章字數： 3.3k 所需閱讀時間 ≈ 11 分鐘

B(DP优化) D(插入排序反向组合数树状数组) E(二分图论数学 bfs)

B

题意

n <= 4e6, 1e8<mod<1e9, mod is prime, 时间6s，内存128MB

$f(1) = 1$

$f(x) = \sum_{y=1}^{x-1}f(y) + \sum_{z=2}^{x}f(\lfloor \frac{x}{z} \rfloor)$

给定n和mod, 求f(x)%mod

先看时间复杂度

虽然题目给了6s, 但是这里n已经是4e6了

显然左边可以前缀和

$ f(x) = presumf(x-1) + \sum_{z=2}^{x}f(\lfloor \frac{x}{z} \rfloor)$

左边 O(1)了

右边，注意到$\lfloor \frac{x}{z} \rfloor$ 的取值个数是$O(\sqrt{n})$ 的

这一块即使用了连续段的优化依然整个是$O(n^{1.5})$的复杂度

剩余我没想到的题解部分

考虑 S(x+1) 和 S(x) 的差别

对于加法，多一个 S(x+1-1 = x),

对于除法，多一个 S((x+1)/(x+1) = 1)

对于 i > 1, 可能 S(x+1) 中是 S(i) 而 S(x)中是 S(i-1)

举例

10:的除序列
5,3,2,2,1,1,1,1,1
11:的除序列
5,3,2,2,1,1,1,1,1,1(多)
12:的除序列
6(变),4(变),3(变),2,2(变),1,1,1,1,1,1(多)

$\lfloor \frac{x+1}{i} \rfloor \neq \lfloor \frac{x}{i} \rfloor $ , 原始值变化为$\frac{1}{i} \leq 1$

$\lfloor \frac{x+1}{i} \rfloor = 1 + \lfloor \frac{x}{i} \rfloor $

$\frac{1}{i}$ 的增加在跨越一个整数时必定是整数

$ x+1 = ki $

所以 $i$ 是 x的约数时才会变

约数看成倍数, 计算到x时 -> diff[kx] += f[x]-f[x-1]

直接变成递推，时间$O(n \log n)$, 空间$O(n)$

Code

on codeforces

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)
 
int n;
 
ll MOD;
 
// 计算之前的是结果，之后的是差异
ll f[4000010];
 
 
int main(){
    cin>>n>>MOD;
    f[1] = 1;
    rep(i,2,n+1){
        if(i == 2){
            // 特殊 没有第一个 f[i-1]
            f[i] = 2;
        }else{
            (f[i] += f[i-1] + (f[i-1] + f[1]))%=MOD;
        }
        rep(j,2,n+1){
            ll ij=i*j;
            if(ij > n)break;
            (f[ij] += f[i]-f[i-1])%=MOD;
        }
    }
    printf("%lld\n",(f[n]+MOD)%MOD);
    return 0;
}

总结

关键点在直接换个思路，换成计算差异，然后这里的差异能从整数部分不同推导到刚好是约数时会变，从而就能完成效率优化

D

题意

t <= 1e5 组测试

每组

0 <= m < n <= 2e5

所有组m保证 sum{m} <= 2e5, 不对n有相应保证

每次是长度为n的数组(不提供具体值)，告诉你m个操作，每次操作x,y (y < x) ，意思是把位置在x移动到y(一次插入排序的操作,也就是 y 是最大的插入位置)

例如

1 2 3 2

如果把最后一个2 ，可以插入在2前，也可以是3前，这里只能选择3前, 所以给的(x y)是 (4 3)

问原始序列所有值在[1~n]之间的合法方案数, MOD 998244353

题解

首先 n 不限制，那么可能会有离散化相关的内容

假设序列开始是[a0 a1 a2 …] 那么根据m次操作，有唯一的移动结果,因为每次都指定的x和y

对于移动以后，必定非严格单调递增

那么问题变成了两个，找到可能一样的值的组（通过能确定的不一样的值做切分），这些组如何得到答案

换个计数法

令c表示，在最终序列中,相邻值“一定不同”的个数（也就是有c个小于号(来源交换推导出的大小关系)）,而最终序列中剩余的相邻的位置，可能相同可能不同

那么把这c个一定不同的位置-1，变成了所有相邻位置可能相同可能小于，范围由n变为了n-c

也就是 n个数，范围在[1~ n-c]中，非严格单调递增的方案数

也就是 n 个相同的球，放入 n-c 个不同盒子中（可以空盒子）

也就是 n+n-c 个相同的球，放入 n-c 个不同盒子中（不能空盒子）

挡板法,有 2n-c-1 个间隙

显然方案数 C(2n-1-c,n)

也就有了，如果能的到c就能得到答案

计算必定小于个数

离线+倒序

维护一个位置集合S,初始含有1到n

按照插入的倒序，(知道xi是单调递减的)

对于(xi,yi),

// 操作前 （反向操作会让 [xi~n]这部分之后再也不会使用）
[1....yi-1][yi...xi-1][xi][xi+1...n]
// 操作后
[1....yi-1][xi][yi...xi-1][xi+1...n]
// 因为我们是反向操作，所以 关注的是这两个
            !   !                    
            p   q

p = S中第yi小的

q = S中第yi+1小的

标记q是前面相邻被拆入过值的,然后删除p (因为xi是单调递减，xi 到n，在倒序处理过程中，都不再回用到，和把p变成n+1一样效果

而找第k小和移除一个数，这种可以通过线段树，树状数组来完成

效率

注意到不要做成 O(n log n), 要是O(m log n), 一个办法是，首次建立足够大的树状数组/线段树。每轮询问结束后，再回滚，这样建树 O( max n ), 操作都是 O ( m log n )

这样算法+效率问题都解决了

代码

狗都不手写平衡树

倒序+树状数组+二分法查找第k大+组合数

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

const int N = 400000;
ll fac[N+10];

ll pwr(ll v,ll mi){
  ll r =1;
  while(mi){
    if(mi%2) (r*=v)%=MOD;
    (v*=v)%=MOD;
    mi/=2;
  }
  return r;
}

ll inv(ll v){
  return pwr(v,MOD-2);
}

ll C(ll n,ll m){
  return (((fac[n]*inv(fac[m]))%MOD)*inv(fac[n-m]))%MOD;
}

int n,m;

ll ta [2*N+10];

ll lowbit(ll v){
  return v & -v;
}

void tinit(){
  rep(i,1,2*N+1){
    ta[i] = lowbit(i);
  }
}

void tadd(int i,int v){
  for(;i < 2*N+1;i+=lowbit(i)){
    ta[i] += v;
  }
}

ll tpre(int i){
  ll s = 0;
  for(;i!=0;i-=lowbit(i)){
    s+=ta[i];
  }
  return s;
}

ll getk(int k){
  ll l = 0;
  ll r = N+1;
  while(l+1 < r){
    int mid = (l+r)/2;
    ll p = tpre(mid) ;
    if(p>=k)r=mid;
    else l=mid;
  }
  return r;
}



ll getc(vector<int>&ys){
  set<int> used ;
  vector<int> rm;
  per(i,0,m){
    int y = ys[i];
    used.insert(getk(y+1));
    int rmi = getk(y);
    rm.pb(rmi);
    tadd(rmi,-1);
  }
  int r = used.size();
  per(i,0,m){
    tadd(rm[i],1);
  }

  return r;
}

int main(){
  fac[0]=1;
  rep(i,1,N+1){
    fac[i] = (fac[i-1]*i)%MOD;
  }
  tinit();
  int t;
  cin>>t;
  while(t--){
    vector<int> ys;
    scanf("%d %d",&n,&m);
    rep(i,0,m){
      int x,y;
      scanf("%d %d",&x,&y);
      ys.pb(y);
    }
    ll c= getc(ys);
    printf("%lld\n",C(2*n-c-1,n));

  }
  return 0;
}

Ext

pbds

对于题解提到的 Policy-Based Data Structures 见下面洛谷日报，总之是在std以外，c++的一个扩展库里提供了对应的平衡树实现，可以不用自己去写平衡树

Rope

1 2	#include<ext/rope> using namespace __gnu_cxx;

1	rope<变量类型>变量名称;

简单来说 rope是个超级string 内部实现平衡树，也就是可以不用上面的所有知识，直接正着做XD, 本意可能是用作巨大文本编辑时使用

crope = rope<char>

https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/ext/rope

复杂度看https://www.geeksforgeeks.org/stl-ropes-in-c/ 里说操作都是log，所以总的复杂度应该是 m log n

Ref

官方题解

洛谷日报39期 pbds

gnu online doc pbds

E

题意

无向连通图

保证每点出度大于2

无自环和重边

点<=1000

边<=2000

每个点有 1<= a[i],b[i] <= 1e9

初始值x, 从点1出发, 每次首次经过一个点，需要满足当前x > a[i],首次经过该点后会 x+=b[i]

可以重复走边走点

额外限制，走完一条边以后不能立刻重走该边, 也就是不能 a->b->a

求能够经过所有点的最小的x

每次100组测试，每次测试内容的 sum{n}<=1000 sum{m}<=2000

题解

显然，x单调递增，也就是如果我们能超过最大点，则所有点都能走，那么x的下界是 max{最大a点的a-sum{其它b},1点相邻点的最小a}+1

上界直接最大值+1

所以如果给定一个值，我们能校验其合法性的话，那么可以二分 [既然是2分了，其实不考虑上下界直接[1~1e9+1]开始二分也行]

定义set表示已经访问过的集合, 我们找寻两种增广路径

到set以外的一些点的简单路径，并返回到set中， set中的点a->out->out->out…->set中的点b,我们把这些out的点加入到set中。注意因为首先我们知道set中的点任意两点至少有一条简单路径，现在能通过外部建立一条简单路径，那么必定可以仅在set中任意的行走，走到任意的点, 对于点a点b是同一个点，就更显然，我们有一个环，能在set中走环上任意点，然后即可走到set上任意点
不一定返回原来的set中，但是能在外部走成环 set中的点->out->out->out->out中出现过的点, 同上加入set中，我们又可达任意的点

以上两种都解决了不能立刻原路返回的限制

上面两种是必要的方法，但是充分性需要证明一下，也就是没有其它的方案

如果从set中走出，无法达成上面两种，则所有出走都是死路，因为连通性和度保证不会因为边的路径限制而是死路，只会因为不能立刻回头+a[i] 的限制而成死路，因为每走一步，既不成环也不回到set，那么out没走过的必然-1，数量离散有下界，单调递减，必有界，

证明如果全是死路，则当前set无法完成，如果全是死路，则所有路径均不会消耗所有点，且无法扩展，出走后无法行走，如果消耗完所有点，那么说明x比所有a都打，必定可以成环矛盾

再证每次增广的顺序不会影响，初始set，

对于一个可行的x和可行的增广顺序，显然x单调递增，如果有不同的方案导致死路，那么死路前的set，可以按照合法的增广顺序操作，每一次操作的x值都大于等于原合法顺序的值，必定可行，所以增广的顺序和初始x值是否可行没有关系,

同时一个 set的 最终x = sum{b}+初始x

那么问题就变成

对于给定的x，通过上述两种方案增广直到全覆盖，或者全死路为止

O(效率 log(max(a)))

那么 v->out->out->u(out) ，记录到u的时x的值 , 那么如果有另一条路径到达u,两条路径中大x的值向小x值走动,那么可以和它构成环, 所以dfs即可

代码

暴力bfs过了，没缩点时间复杂度，每次 bfs( O(m+n) ), 增广次数O(n), 所以总时间复杂度 O(n(m+n)log(max(a)))

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define t3 1000+10
#define t4 10000+10
#define t5 100000+10
#define t6 1000000+10
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

int n,m;

ll a[1010];
ll b[1010];

vector<int> p2[1010];


vector<ll> get_circle(ll x ,vector<ll> & vis, vector<ll> bfs){
  vector<ll> cur = vector(1010,(ll)0);
  vector<ll> fa = vector(1010,(ll)0);
  int st = 0;
  while(st < bfs.size()){
    int p = bfs[st];
    for(auto item:p2[p]){
      if(item == fa[p])continue; // 不能立即返回
      // item set 内
      if(vis[item]){
        // p set 内
        if(vis[p]){
          continue;
        }
        vector<ll> ret ;
        while(p && !vis[p]){
          ret.pb(p);
          p = fa[p];
        }
        assert(ret.size());
        return ret;
      }
      // item非set内
      if(cur[item] != 0){ // 访问过
        // p->item <- old
        // 这个比较有必要吗，因为 cur[x] > a[x] 是肯定的, 所以最小值一定在a中出现，必定至少成立一个不等式
        // if(cur[item] > a[p] // old->item -> p -> ...
        //   || max(cur[p],x) > a[item]) { // p->item -> old
          vector<ll> ret ;
          while(p && !vis[p]){
            ret.pb(p);
            p = fa[p];
          }
          p = item;
          while(p && !vis[p]){
            ret.pb(p);
            p = fa[p];
          }
          assert(ret.size());
          return ret;
        // }
      }else{
        // 未访问过 且可达
        if( max(cur[p],x) > a[item] ){
          bfs.pb(item);
          cur[item] = max(cur[p],x) + b[item];
          fa[item] = p;
        }
      }
    }
    st++;
  }
  return {};
}

bool test(ll startx){
  vector<ll> vis = vector(1010,(ll)0);
  vector<ll> s; // set 中的点
  s.pb(1);
  vis[1] =  1;
  int cnt = 1;
  while(true){
    auto r = get_circle(startx, vis,s);

    if(!r.size()){
      return false;
    }
    for(auto item:r){
      if(!vis[item]){
        // TODO 缩点
        vis[item] = 1;
        s.pb(item);
        cnt++;
        startx += b[item];
      }
    }
    if(cnt == n){
      return true;
    }
  }
}


int main(){
  int t;
  cin>>t;
  while(t--){
    scanf("%d %d",&n,&m);
    rep(i,2,n+1){
      scanf("%lld",a+i);
    }
    rep(i,2,n+1){
      scanf("%lld",b+i);
    }
    rep(i,0,m){
      int u,v;
      scanf("%d %d",&u,&v);
      p2[u].pb(v);
      p2[v].pb(u);
    }
    ll l = 0;
    ll r = 1'000'000'001;
    while(l+1 < r){
      ll mid = (l+r)/2;
      if(test(mid)){
        // printf("%lld ok\n",mid);
        r = mid;
      }else{
        // printf("%lld not ok\n",mid);
        l = mid;
      }
    }
    printf("%lld\n",r);
    // clear;
    rep(i,1,n+1){
      p2[i] = {};
    }
  }
  return 0;
}

百度之星2021 复赛1002题 (第二类斯特林数)

發表於 2021-08-23 更新於 2024-10-23 分類於 bestcoder Disqus：文章字數： 637 所需閱讀時間 ≈ 2 分鐘

第二类斯特林数

痛失1002只过了1001签到题

虽然凭空推出过一些定理，但多数定理还是难以凭空推出的 QAQ

https://acm.hdu.edu.cn/showproblem.php?pid=7095

题意

1e4组测试

每组测试给定(n,m <= 3k)

一个x，n个加法$+a_1,+a_2,…,+a_n$, $ \cdot b_1,\cdot b_2,\cdot b_m$，m个乘法

任意排列它们，计算从左向右，无优先级

如果任意变量，两个表达式值都相同，那么两个表达式本质相同

求本质不同的方案数

例子

如2加1乘(注意无优先级从左向右算)

$x+a_1 + a_2 \cdot b_1 $

$x+a_1 \cdot b_1 + a_2 $

$x+a_2 \cdot b_1 + a_1 $

$x \cdot b_1 +a_1 + a_2 $

一共4种

思路

a和b间隔，

那么他们数量差不大于1

对于a分为k组，方案数

$f(a,k) * (f(b,k-1)+2f(b,k)+f(b,k+1))$

如果能线性算出 $f(a,b)$ 那么就能在时间内算出

问题变成了，把n个数拆分成k个非空集合的方案数如何算

这就是我卡住尝试自己想，但未想出方案(oi wiki都还没人加上这个)

第二类斯特林数

S(n,m) 表示把n个不同的小球放在m个相同的盒子里（且每个盒子至少一个）方案数

第一个球单独在一个盒子里 S(n,m)+=S(n-1,m-1)

第一个球不单独放，那就是剩余放完以后，其中一个盒子中再放入1，对于所有剩余放完后，都有m种选法S(n,m)+=mS(n-1,m)

所以

S(n,m) = S(n-1,m-1) + mS(n-1,m)

这样我们可以直接初始化完整个S

回到原题

因为原题还是有序

上面的S是无序的，所以每次 S(n,m) 乘上 n! 就行

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define t3 1000+10
#define t4 10000+10
#define t5 100000+10
#define t6 1000000+10
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);


ll S[3010][3010];
ll pwr[3010];


ll f(ll a,ll b){
    return (pwr[b]*S[a][b])%MOD;
}

void work(){
    int n,m;
    scanf("%d %d",&n,&m);
    if(n>m)swap(n,m);
    ll ans = 0;
    rep(k,1,n+1){
        (ans+= f(n,k) * (f(m,k-1) + 2*f(m,k)+f(m,k+1)))%=MOD;

    }
    printf("%lld\n",ans);
}


int main(){
    S[1][1] = 1;
    rep(i,2,3001){
        rep(j,1,i+1){
            (S[i][j] = S[i-1][j-1] + j * S[i-1][j])%=MOD;
        }
    }
    pwr[0]=1;
    rep(i,1,3001){
        pwr[i] = (pwr[i-1]*i)%MOD;
    }

    int t;
    cin>>t;
    while(t--){
        work();
    }
  return 0;
}

Zeckendorf's theorem

發表於 2021-07-29 更新於 2024-10-23 分類於 algorithm Disqus：文章字數： 308 所需閱讀時間 ≈ 1 分鐘

任何正整数都可以唯一表示成不连续的Fibonacci数列和

定理

任何正整数都可以唯一表示成不连续的Fibonacci数列和

proof

可表示性

对于任意自然数n

有唯一i使得 $fib(i) <= n < fib(i+1)$

说明 $fib(i) > n/2 $ 否则 $fib(i+1) = fib(i)+fib(i-1) < fib(i)+fib(i) = 2fib(i) <= n$ 矛盾

$n-fib(i) < n/2$

$n-fib(i) < fib(i-1)$, 否则 $n >= fib(i)+fib(i-1) = fib(i+1)$，保证了非连续

说明$f(n)$ 的表示通过拆除fib(i)方案数与 $f(n-fib(i))$ 一致，

所有都是唯一可递归下降，f(0) 唯一表示为空

所以所有都可以表示

下面证明唯一表示

上面我们每次取得都是不大于n的最大的fib(i), 这种情况下非连续且可表示

下面证明如果不这样操作，则不可表示，就能证明其唯一性

$fib(i) <= n < fib(i+1)$

证明$fib(i-1)+fib(i-3)+fib(i-5)+… < fib(i) < n$

$1 + fib(i-1)+fib(i-3)+fib(i-5)+… = fib(i) $

$fib(i-1)+fib(i-3)+fib(i-5)+… = fib(i) - 1 < fib(i) = n$

得到如果不取$fib(i)$,那么最大的非连续和无法构成n，则唯一性得证

STOER-WAGNER 无源无汇最小割

發表於 2021-07-27 更新於 2024-10-23 分類於 algorithm Disqus：文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘

问题

一个无向联通图,应该要正边权?，最小割分成两个子图

方法

引理

图G中的两个点s,t,

如果最小割分割了它们，那么直接求s到t的最小割

如果没有，那么合并s-t，得到的新图G1 和原图的最小割一致

因此有方法, 任意选择点a，加入集合A中

每次选择和A距离和最大的点加入集合中，也就是上面的合并操作

注意，这里每次都不是把图里的最大的边去掉，而是集合A距离最大的点加入A中

这样反复操作，一直到剩下3个点A,b,c ，可以得到一个割的值, 除了A以外的两个点b,c在这次分割中一定是被分开了的

我们也能得到一个b和c是被分割的值

重新初始的图

合并 b和c成集合B

重复上面所有操作，直到剩余3个点，B,d,e

重新初始的图

合并b,c成集合B, 合并d和e成集合D

重复上面所有操作，直到剩余3个点，?a,?b,?c,

我们能到到一个分割值，也能让下一轮的操作合并两个点

这样我们最终所有操作中最小的分割就是答案

Proof

对于每一轮剩余3个点的时候，我们有该轮的初始集合S，和另外两点$p_1,p_2$

因为合并规则一直是与S距离最大的边，所以$p_1,p_2$ 一定是被分割的，

虽然因为边的长度可能在操作过程中相等，也就意味着在每一轮操作开始时，甚至$p_1,p_2$ 是哪两个点，是不确定的,(当然我们可以给所有点提前编号，保持即使值相等的点也有一定的偏序关系，来让结果唯一)

但是可以证明，对于每次计算到剩余3个点时，其中的$p_1,p_2$来说，当前图里面这是这两个点要切割的最小割

我们把这轮的$(p_1,p_2)$ 命作$(s,t)$

对于给定图$G$，和通过上述步骤得到的$s,t$

如果两个点之间没有相连，我们在数值上可以看做有一条相连权重为0的边,在下面的计算上没有影响(因为每次取得是最大的), 连通的判断时权重为0视为不连通

割: 把原图分成两个联通块的边集

$C$是$G$上$s-t$的一个任意的割,即$s,t$在不同连通块

$CP$是按照上述步骤得到的$s-t$的割

$W(边集)$ = 边集的权重和

$W(点集A，点v)$ = $点v$到$点集A$中所有点的边权和

要证:$W(C) \ge W(CP)$

对于上述给定流程$CP$，根据点加入的顺序，命名为$a_1,a_2,a_3…a_{n-1},a_n$, 其中$s = a_{n-1},t = a_n$

对于 $i$,如果$a_{< i-1}$和$a_{i}$ 位于割C的两侧,那么称为$i$为$active$的(简化后面描述)

我们不用讨论$CP$，因为序列就是$CP$产生的，所有操作都是位于$CP$割的同一连通块

点集 $A_i = 集合(a_1…a_{i-1}) $

也就是$a_i$前面的点

边集 $C_i = 集合(边|边的两端均属于集合(a_1…a_i)) ∩ C$

也就是割边中，端点都在前面$a_1..a_i$ 中

我们要证明对于每一个$active$的$i$, $W(A_i, a_i) \le W(C_i)$,

也就是$a_i$和它之前的点的边权和小于割$C$中的两端来自前$a_1 … a_i$的边权和

接下来归纳开始 (归纳的目标和总目标一致)

初始: 若$i$是最小使得$active$的，那么$W(A_i,a_i) = W(C_i)$

因为说明前面的边,按照割C，都在同一侧，所以$C_i$中所有的边，都一个顶点是$a_i$

对于$i,j,(i < j)$ 都是$active$相邻

$i$和$j$是active, $i$和$j$之间没有其它$active$的,

$W(A_j,a_j) = W(A_i,a_j) + W(A_j - A_i, a_j) $

直接的拆分点集$A_j$

$\le W(C_i) + W(A_j - A_i, a_j) $

根据初始条件和归纳,$W(A_i,a_j)\le W(A_i,a_i) \le W(C_i)$ , 前一半不等式是操作过程中每次选最大距离的连通，后一部分是归纳

$= W(C_j)$

因为$i$和$j$之间没有其它$active$，所以也就是$i$和$j$之间的点不会与小于$j$的点构成属于$C_u$的边，
而对于$W(A_j-A_i,a_j)$的贡献，不会和$C_i$重复因为(不包含$a_j$),

综上

$W(A_n,a_n) \le W(C_n) = W(C)$

左边不等式是归纳的结果，右边是因为所有C中的边且两端的点在所有点中，就是$C$自己

结论:

也就是说，对于图$G$的$s-t$任何的割$C$，都不小于$t$单独划分出来的边权和

所以这是一个最小分割

回到操作过程

也就是每一轮，都能产生$s-t$分割的最小割，之后的轮次，$s$和$t$就在同一个“连通块”里了

这里有一点 实际上再思考仔细一点，这个过程中其实并不满足题意(分成两个)，因为我们很可能把原图分割成了好几个连通块，也就是不止两个。但是因为如果能分割成多个，反向操作，每次最多把两个合成一个，必定最小割是分成两个的。所以得到的答案也一定是割, 保证了正确性

也就是你合并的s和t可能，它们还并不连通，只不过你从划分上认为属于一块了

综上，算法正确性证毕

Ref

https://basics.sjtu.edu.cn/~dominik/teaching/2016-cs214/presentation-slides/2016-12-06-StoerWagner-BigNews.pdf

https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm

project euler 218 (别写代码用数学)

發表於 2021-07-20 更新於 2024-10-23 分類於 Project Euler Disqus：文章字數： 624 所需閱讀時間 ≈ 2 分鐘

题目

原题链接

直角三角形$(a,b,c)$,其中$c$为斜边

perfect定义

边互质$gcd(a,b) = 1$
斜边是平方数$c = x^2$

super-perfect

perfect
直角三角形面积是6和28的倍数

求

$c \le 10^{16}$ 内,有多少perfect的不是super-perfect

题解

前面的PE我们学习到，$gcd(a,b)=1$ 的直角三角形可以唯一表示成

$(a,b,c) = (m^2-n^2,2mn,m^2+n^2)$

其中两个直角边可以对换

其中 $gcd(m,n) = 1, (m+n) = 1 (\bmod 2)$

$lcm(6,28) = 84$

简化成

$m^2+n^2 = c = x^2 \le 10^{16} $

求 $mn(m^2-n^2) != 0 (\bmod 84)$ 的个数

注意到这里又是一个直角三角形公式

$ordered(m,n,x) = ordered(2uv,u^2-v^2,u^2+v^2)$

即

$u > v, gcd(u,v) = 1, u+v = 1 (\bmod 2)$

$u^2+v^2 \le 10^{8}$

$ordered(m,n) = ordered(2uv,u^2-v^2) $

求 $mn(m^2-n^2) != 0 (\bmod 84)$ 的个数

代码

直接翻译很好写了

perfect_but_not_super_perfect = 0

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)


for v in range(1,10**4):
    if v % 100 == 0:
        print("b:", v)
    for u in range(v+1,10**4,2):
        if gcd(u,v) != 1:
            continue

        if u**2+v**2 > 10**8:
            break;

        m,n = u**2-v**2,2*u*v

        if n > m:
            m,n=n,m

        if (m*n*(m**2-n**2)) % 84 != 0:
            perfect_but_not_super_perfect += 1


print("ans",perfect_but_not_super_perfect )

时间

1
2
3

real    0m30.195s
user    0m30.195s
sys     0m0.000s

不要到此为止上数学

就完了吗

它要是个长长的数字可能也没这篇文章了，因为PE的 one-minute rule 已经满足了

但是它的答案是0那就激起了推导的兴趣

命题

$u > v, gcd(u,v) = 1, u+v = 1 (\bmod 2)$

$(m,n) = (2uv,u^2-v^2) $

则 $mn(m^2-n^2) = 0 (\bmod 84)$

这里我们没有范围限制，考虑模运算的性质，没有了大小顺序正负

代入

$2uv(u^2-v^2)(6u^2v^2-u^4-v^4) = 0 (\bmod 84)$

$uv(u^2-v^2)(6u^2v^2-u^4-v^4) = 0 (\bmod 42)$

$42 = 2 \cdot 3 \cdot 7$

讨论

2 显然，因为$u+v=1(\bmod 2)$ , u 和 v一奇一偶

3 如果u和v其中有3的倍数，那么是3的倍数，如果均不是3的倍数,因为 $1^2=2^2=1 (\bmod 3)$ , 所以 $u^2-v^2 = 0 (\bmod 3)$

7 如果u和v其中有7的倍数，那么是7的倍数，否则都不是7的倍数，还是写一点代码

1
2
3

for u in range(1,7):
    for v in range(1,7):
        print(u,v,((u**2-v**2)*(6*u*u*v*v-u**4-v**4))%7)

输出都是0 得证

B

题意

先看时间复杂度

剩余我没想到的题解部分

Code

总结

D

题意

题解

换个计数法

计算必定小于个数

效率

代码

狗都不手写平衡树

Ext

pbds

Rope

Ref

E

题意

题解

代码

痛失1002只过了1001签到题

虽然凭空推出过一些定理，但多数定理还是难以凭空推出的 QAQ

例子

思路

问题变成了，把n个数拆分成k个非空集合的方案数如何算

第二类斯特林数

回到原题

代码

定理

相关

proof

可表示性

下面证明唯一表示

问题

方法

Proof

Ref

题目

题解

代码

不要到此为止 上数学

命题

代入

讨论

不要到此为止上数学