牛客多校第二场

A:Eddy Walker

题意

给你一个n的点的环，一开始从0号点开始，每次可以前进1或者后退1，问第一次站在m号点的时候已经遍历完所有点的概率，求出前缀概率积

思路

一：

暴力打表找规律

AC代码

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

double p[10];
bool vis[10];
int n;

bool Check() {
    for (int i = 0; i < n; i ++)
        if(!vis[i]) return false;
    return true; 
}

void dfs(int idx, double px) {
    if(px < 1e-10) return ;
    vis[idx] = 1;
    if(!Check()) {
        int nxt = (idx+1)%n;
        int tmp = vis[nxt];
        vis[nxt] = 1;
        dfs(nxt, px*0.5);
        vis[nxt] = tmp;
        nxt = (idx-1+n)%n;
        tmp = vis[nxt];
        vis[nxt] = 1;
        dfs(nxt, px*0.5);
        vis[nxt] = tmp;
    }else p[idx] += px;
}


int main() {
    for (n = 1; n <= 7; n ++) {
        printf("n: %d\n", n);
        memset(p, 0, sizeof(p));
        memset(vis, 0, sizeof(vis));
        dfs(0, 1);
        for (int i = 0; i < n; i ++) {
            printf("i: %d, p: %lf\n", i, p[i]);
        }
    }
    return 0;
}

这是打表的结果，可以发现结果与m无关(当m>0时)而且近似为$\frac{1}{n-1}$

二：
数学分析:
因为是最后站在一个非0的位置上，而每个非零的点的最后一次到达的概率是相同的，所以是$\frac{1}{n-1}$

B:Eddy Walker2

题意

现在是给你一条链，从0点出发，一个最多走k步，每一步的概率都是$\frac{1}{k}$ ,问最后走到n的概率

思路

根据题意可以写出一个递推式子：

$dp[i] = \frac{1}{k}\sum\limits_{i=1}^{k}dp[n-i]$

如果n很小的话，可以直接用dp来写，但是n的大小是$1e^{9}$，所以我们就得用BM直接套板子线性递推

但是有一个问题，就是n可能为无穷，我们可以这样来写，

我们每次行动的移动记录期望是$\frac{1}{k}\sum\limits_{i=1}^{k}i=\frac{(k+1)k}{2k}=\frac{k+1}{2}$ ,也就是每行动一次大概移动$\frac{k+1}{2}$ ，而我们移动到n的次数可能为m次，那么移动的距离期望就是$\frac{(k+1)m}{2}$ 而n在其中，在这$\frac{(k+1)m}{2}$个点中，我们一共会走m个点，那么就是n在这m个点之间的概率$\frac{1}{m}$ , 期望就是$m$ ,而在整体的概率就是$\frac{m}{\frac{(k+1)m}{2}}=\frac{2}{k+1}$

$dp[i]=\begin{cases} \frac{1}{k}\cdot (dp[i-1]+dp[i-2]+…+dp[i-k]),i>=k\\ \frac{2}{k+1},i=\infty \\\end{cases}$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
#define sz(x) ((int)(x).size())
typedef vector<ll> VI;
 
ll Ksm(ll a, ll b) {
    ll res = 1; a %= mod;
    assert(b >= 0);
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
 
int _, n;
namespace Linear_Seq{
    const int N = 10010;
    ll res[N], base[N], _c[N], _md[N];
    vector<int> Md;
     
    void Mul(ll *a, ll *b, int k) {
        for (int i = 0; i < k+k; i ++) _c[i] = 0;
        for (int i = 0; i < k; i ++)
            if(a[i]) for (int j = 0; j < k; j ++)
                _c[i+j] = (_c[i+j] + a[i]*b[j]) % mod;
        for (int i = k + k - 1; i >= k; i --)
            if(_c[i]) for (int j = 0; j < sz(Md); j ++)
                _c[i-k+Md[j]] = (_c[i-k+Md[j]] - _c[i] * _md[Md[j]]) % mod;
        for (int i = 0; i < k; i ++)
            a[i] = _c[i];
    }
 
    int solve(ll n, VI a, VI b) {
        ll ans = 0, pnt = 0;
        int k = sz(a);
        assert(sz(a) == sz(b));
        for (int i = 0; i < k; i ++) _md[k-1-i] = -a[i];
        _md[k] = 1; Md.clear();
        for (int i = 0; i < k; i ++) 
            if(_md[i]) Md.push_back(i);
        for (int i = 0; i < k; i ++) res[i] = base[i] = 0;
        res[0] = 1;
        while((1ll<<pnt) <= n) pnt ++;
        for (int p = pnt; p >= 0; p --) {
            Mul(res, res, k);
            if((n>>p) & 1) {
                for (int i = k-1; i >= 0; i --) res[i+1] = res[i];
                res[0] = 0;
                for (int j = 0; j < sz(Md); j ++)
                    res[Md[j]] = (res[Md[j]] - res[k] * _md[Md[j]]) % mod;
            }
        }
        for (int i = 0; i < k; i ++) ans = (ans + res[i] * b[i]) % mod;
        if(ans < 0) ans += mod;
        return ans;
    }
 
    VI BM(VI s) {
        VI C(1, 1), B(1, 1);
        int L = 0, m = 1, b = 1;
        for (int n = 0; n < sz(s); n ++) {
            ll d = 0;
            for (int i = 0; i < L + 1; i ++) d = (d + (ll)C[i] * s[n-i]) % mod;
            if (d == 0) ++m;
            else if(2 * L <= n) {
                VI T = C;
                ll c = mod - d * Ksm(b, mod-2) % mod;
                while(sz(C) < sz(B) + m) C.push_back(0);
                for (int i = 0; i < sz(B); i ++) C[i+m] = (C[i+m] + c * B[i]) % mod;
                L = n + 1 - L; B = T;
                b = d; m = 1;
            }else {
                ll c = mod - d * Ksm(b, mod-2) % mod;
                while(sz(C) < sz(B) + m) C.push_back(0);
                for (int i = 0; i < sz(B); i ++) C[i+m] = (C[i+m] + c * B[i]) % mod;
                ++ m;
            }
        }
        return C;
    }
 
    int Gao(VI a, ll n) {
        VI c = BM(a);
        c.erase(c.begin());
        for (int i = 0; i < sz(c); i ++) c[i] = (mod-c[i]) % mod;
        return solve(n, c, VI(a.begin(), a.begin()+sz(c)));
    }
};
using namespace Linear_Seq;
 
void solve() {
    ll n, k;
    scanf("%lld %lld", &k, &n);
    if(n == 0) {
        printf("1\n");
        return ;
    }else if(n == -1) {
        printf("%lld\n", 2 * Ksm(k+1, mod-2) % mod);
        return ;
    }
    VI dp(3*k, 0), v;
    dp[0] = 1;
    v.push_back(1);
    for (int i = 1; i <= k; i ++) {
        for (int j = 0; j < i; j ++)
            dp[i] = (dp[i] + dp[j]) % mod;
        dp[i] = dp[i] * Ksm(k, mod-2) % mod;
        v.push_back(dp[i]);
    }
    for (int i = k+1; i <= 2 * k; i ++) {
        for (int j = 1; j <= k; j ++)
            dp[i] = (dp[i] + dp[i-j]) % mod;
        dp[i] = dp[i] * Ksm(k, mod-2) % mod;
        v.push_back(dp[i]);
    }
    printf("%lld\n", Gao(v, n));
}
 
int main() {
    int T;
    scanf("%d", &T);
    while(T --)
        solve();
    return 0;
}

E:MAZE

题意

给你一个NxM的地图，0表示可走，1表示不可走，

有$Q$次询问，可能会对某一位置取反，可能问你从$(1,a)$到$(n,b)$有多少走法

思路

因为题目 要求不能往回走，所以如果我们从下面开始走，那么我们在横向移动是就不能改变方向，然后向上走

我们先用$dp$来考虑一下做法：设$dp[i][j]$是经由下面$dp[i-1][j]$走过来的走法数，那么从左边或右边走过来的方法数呢，我们可以在最后在加一层，那么$dp[0][j]$就加上了第1层左右到达$dp[1][j]$的方法数

那么$dp[i][j] = sum(dp[i-1][j]+dp[i-1][j-1] + … dp[i-1][j-k])+sum(dp[i-1][j+1]+dp[i-1][j+2]+…+dp[i-1][j+k])$

$dp[i][j]$由$i-1$层，$i$的左边第一个1和$i$的右边第一个1，这么一段区间里的$dp$值转移过来

比如这样一个2X6的地图,

$dp[1][3]=dp[2][2]+dp[2][3]+dp[2][4]+d[2][5]$

$dp[1][4]=dp[2][2]+dp[2][3]+dp[2][4]+d[2][5]$

由于上一层的每个值都是有下面的值组成，那么我们就可以构造出一个矩阵

这样我们就能从第$i$层转移到第$i-1$层了

现在来考虑地图修改的情况

这n个矩阵我们可以用一个线段树来维护，地图修改时用线段树来修改矩阵就行了

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
 
const int maxn = 5e4 + 5;
const int mod = 1e9+7;
char c[maxn][15];
int dp[maxn][15];
 
int N, M, Q;
 
struct Maze {
    int maze[15][15];
 
    Maze() {memset(maze, 0, sizeof(maze));}
 
    void init() {for (int i = 0; i < 15; i ++) maze[i][i] = 1;}
 
    Maze friend operator * (Maze a, Maze b) {
        Maze c;
        for (int i = 0; i < M; i ++)
            for (int j = 0; j < M; j ++)
                for (int k = 0; k < M; k ++)
                    c.maze[i][j] = (c.maze[i][j] + 1ll * a.maze[i][k] * b.maze[k][j]) % mod;
        return c;
    }
 
};
 
struct Seg{
    Maze w[maxn<<2];
 
    void Build(int rt, int l, int r) {
        if(l == r) {
            for (int i = 0; i < M; i ++) {
                if(c[l][i] == '0') {
                    for (int j = i; j >= 0; j --)
                        if(c[l-1][j] == '1') break;
                        else w[rt].maze[j][i] = 1;
                    for (int j = i; j < M; j ++)
                        if(c[l-1][j] == '1') break;
                        else w[rt].maze[j][i] = 1;
                }
            }
            return ;
        }
        int m = (l + r) >> 1;
        Build(rt*2, l, m);
        Build(rt*2+1, m+1, r);
        w[rt] = w[rt*2] * w[rt*2+1];
    }
 
    void Updata(int rt, int l, int r, int pos) {
        if(l == r) {
            for (int i = 0; i < M; i ++)
                for (int j = 0; j < M; j ++)
                    w[rt].maze[i][j] = 0;
            for (int i = 0; i < M; i ++) {
                if(c[l][i] == '0') {
                    for (int j = i; j >= 0; j --)
                        if(c[l-1][j] == '1') break;
                        else w[rt].maze[j][i] = 1;
                    for (int j = i; j < M; j ++)
                        if(c[l-1][j] == '1') break;
                        else w[rt].maze[j][i] = 1;
                }
            }
            return ;
        }
        int m = (l + r) >> 1;
        if(pos <= m) Updata(rt*2, l, m, pos);
        else Updata(rt*2+1, m+1, r, pos);
        w[rt] = w[rt*2] * w[rt*2+1];
    }
 
    void Updata(int pos) {
        Updata(1, 1, N, pos);
    }
    
}seg;
 
int main() {
    scanf("%d %d %d", &N, &M, &Q);
    for (int i = 0; i < N; i ++) scanf("%s", c[i]);
    for (int i = 0; i < M; i ++) c[N][i] = '0';
    seg.Build(1, 1, N);
    //seg.Print(1, 1, N);
    while(Q --) {
        int op, a, b;
        scanf("%d %d %d", &op, &a, &b);
        if(op == 1) {
            if(c[a-1][b-1] == '0') c[a-1][b-1] = '1';
            else c[a-1][b-1] = '0';
            if(a > 1) seg.Updata(a-1);
            seg.Updata(a);
        } else {
            Maze ans = seg.w[1];
            Maze t1;
            t1.maze[0][a-1] = 1;
            t1 = t1 * ans;
            printf("%d\n", t1.maze[0][b-1]);
        }
    }  
     
    return 0;
 
}

F:Partition problen

题意

给你2N个人，每对人如果不在同一队的话，有一个竞争值，你要把这些人分为人数相等的两个队，使得竞争值最大

思路

直接暴力

AC代码

//队友代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 1e5 + 5;
vector<int> a, b;
int c[30][30];
int n;
ll ans = 0;

void dfs(int idx, ll cur) {
    if(idx == 2 * n + 1) {
        ans = max(ans, cur);
        return ;
    }
    ll sum = 0;
    if(a.size() < n) {
        a.push_back(idx);
        sum = 0;
        for (int &v: b) sum += c[idx][v];
        dfs(idx+1, cur+sum);
        a.pop_back(); 
    }
    if(b.size() < n) {
        b.push_back(idx);
        sum = 0;
        for (int &v: a) sum += c[idx][v];
        dfs(idx + 1, cur + sum);
        b.pop_back();
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= 2*n; i ++)
        for (int j = 1; j <= 2*n; j ++)
            scanf("%d", &c[i][j]);
    dfs(1, 0);
    printf("%lld\n", ans);
    return 0;
}

H:Second Large Rectangle

题意

给你一个NXM的矩阵，只有01组成，求第二大的全为1的子矩阵

思路

单调栈求最大子矩阵，在过程中就也求出了第二大的子矩阵，然后第一大的宽减一，高减一，和第二大的比较输出最大的

单调栈求最大子矩阵的方法：

逐层遍历，对于每一层求出一个h[]，h表示以此层为底1的高度

比如：

这样一个矩阵,h为：

这样对于每一层就变成一个求最大矩阵的形式，

对于每一层用单调栈求出最大矩阵，注意要记得去重，像上图中的第二层，第二列，第三列，第四列求出的是同一个矩阵，不去重的话无法跟第二大的比较，去重很简单，就记录一下，左边界和上边界即可，

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 1e3+5;
const int inf = 0x3f3f3f3f;
typedef pair<int, int> pis;

struct Pis{
  int res, x, h;

  bool friend operator < (Pis a, Pis b) {
    return a.res > b.res;
  } 
};

char c[maxn][maxn];
int maz[maxn][maxn], h[maxn];
int pre[maxn], suf[maxn];
stack<pis> sta;
int n, m;
map<pis, int> mp;
vector<Pis> ans;

void getPS() {
    while(!sta.empty()) sta.pop();
    sta.push(pis{-inf, 0});
    for (int j = 1; j <= m; j ++) {
      while(h[j] <= sta.top().first) sta.pop();
      pre[j] = sta.top().second+1;
      sta.push(pis{h[j], j});
    }
    while(!sta.empty()) sta.pop();
    sta.push(pis{-inf, m+1});
    for (int j = m; j >= 1; j --) {
      while(h[j] <= sta.top().first) sta.pop();
      suf[j] = sta.top().second-1;
      sta.push(pis{h[j], j});
    }
}

void getH(int i) {
    for (int j = 1; j <= m; j ++)
      if(maz[i][j]) h[j] += 1;
      else h[j] = 0;
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i ++)
    scanf("%s", c[i]+1);
  for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= m; j ++)
      maz[i][j] = c[i][j] - '0';
  for (int i = 1; i <= n; i ++) {
      getH(i); getPS();
      mp.clear();
      for (int i = 1; i <= m; i ++) {
        if(!mp[pis{pre[i], h[i]}]) {
          mp[pis{pre[i], h[i]}] = 1;
          int sum = (suf[i]-pre[i]+1) * h[i];
          ans.push_back(Pis{sum, pre[i], h[i]});
        }
      }
  }  
  sort(ans.begin(), ans.end());
  if(ans.size() <= 1) printf("0\n");
  else {
    int tx = ans[0].res/ans[0].h, ty = ans[0].h;
    printf("%d\n", max(ans[1].res, max(tx*(ty-1), (tx-1)*ty)));
  }
  return 0;
}