Atcoder abc285

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

G

h * w 的格子 要用 1x1 和1x2 填满

上面有写 1,2,? 三种

1需要1x1覆盖

2需要1x2 覆盖(可以旋转成2x1)

? 任意

问 是否有可行方案

范围

h,w 300

3s

1024mb

我的思路

1 不需要关心, 只用关心2, 以及辅助2的?

看起来可以奇偶分边, 来做 二分图最大匹配 O(300^4) 感觉过不了

而且还有问题, 这里并不是要最大匹配, 只是要无冲突和匹配完所有2

另一个想法类似的, 能不能网络流, 还是奇偶分左右点, ?与?不连边, 但是 依然不知道如何表示 优先选2, 难道要费用流? 2的费用更低? 但似乎也没有”保证”

题解

可以变成匹配问题, 点 和 格子中点对应, 如果相邻点都不是1, 增加一条边, 是否有 点匹配, 让所有2都被选中

这个图是二分的, 可以转化 成网络流, 所有边容量是2, 问是否有方案, 让所有点=2 和S/T连的实际流量为1

说是典型的 a (maximum) flow problem with minimum capacities

---

讨论 当所有 容量都多了个下界时, 如何退化成简单的最大流, 等一下, 这就是上次的那个啊!!! Codeforces Edu 139 F 用的 有最小值限制的网络流, 当时叫Maximum Flows with Edge Demands , 上下界限网络流. 学过一次这个套路, 还没熟悉.

方法就是 如果原来 u-> v 容量是R, 它的下限是L

那么把原来容量R的边删掉, 变成 如下的容量(S’,T’ 是新增的源和汇), 这个拆法就是对于u,v 以外的点来说,和u,v的出入流量都没有变, 而需要S’,T’与它们之间满流量

然后两种处理方案, 一个是增加无限大容量的T -> S的边, 然后看是否能跑满 S’

另一个是 不增加这条边, 按照S’->T,S’->T,S->T’,S->T的顺序算最大流, 然后看S’出流量和T’如流量是否一致

以及为啥用Dinic复杂度是O((HW)^{1.5}), (oi-wiki: 特别地，在求解二分图最大匹配问题时，Dinic 算法的时间复杂度是O(E sqrt(V)))

代码

https://atcoder.jp/contests/abc285/submissions/38271384

#include <bits/stdc++.h>
#include<atcoder/maxflow>
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 di[]={0,0,-1,1};
int dj[]={-1,1,0,0};

int main(){
  int h=read();
  int w=read();
  vector<string>b(h);
  for(int i=0;i<h;i++)cin >> b[i];

  atcoder::mf_graph<int>g(h*w+4); // 双源, 双汇
  // hw,hw+2 - left - right - hw+1,hw+3

  int s=h*w,t=s+1; // 原始的源和汇
  int s2=s+2,t2=t+2; // 新增的S', T' 用来保证2的下界的
  int left2=0,right2=0; // 左侧点2个数 和 右侧点2个数
  auto _=[w](int i,int j){return i*w+j;};
  auto ok=[h,w,&b](int i,int j){ return 0<=i and i<h and 0<=j and j<w and b[i][j] != '1'; };
  int cap=0;
  rep(i,0,h) for(int j=i%2;j<w;j+=2)if(b[i][j]!='1'){ // 奇偶来实现二分, S->_(i,j)
    if(b[i][j]=='2'){ // S-(1)>_(i,j) 转化成 S->T'(这个不单独加了, 直接加个合并的大容量边), S'->_(i,j)
      g.add_edge(s2,_(i,j),1);
      cap++;
      left2++;
    }else if(b[i][j]=='?'){
      g.add_edge(s ,_(i,j),1);
    }
    //left to right
    rep(k,0,4){
      int ni=i+di[k];
      int nj=j+dj[k];
      if(ok(ni,nj)) g.add_edge(_(i,j),_(ni,nj),1);
    }
  }
  //right
  rep(i,0,h) for(int j=1-i%2;j<w;j+=2){ // _(i,j) ->T
    if(b[i][j]=='2'){ // 变成 _(i,j)->T' , S'->T(也是加个合并的大容量边)
      g.add_edge(_(i,j),t2,1);
      cap++;
      right2++;
    }else if(b[i][j]=='?'){
      g.add_edge(_(i,j),t ,1);
    }
  }
  // 合并的大容量边
  g.add_edge(s,t2,left2);  // S ->T'
  g.add_edge(s2,t,right2); // S'->T

  g.add_edge(t,s,0x3f3f3f3f); // T->S inf 容量
  auto res = g.flow(s2,t2);
  printf("%s\n",res == cap?"Yes":"No");
  return 0;
}

Ex - Avoid Square Number

给K个数: e1,e2,…,ek

问有多少个长n的不含平方数的正整数 序列满足 所有值乘积 = $\displaystyle \prod_{i=1}^{K} p_i^{E_i}$, 其中$p_i$ 为第i大的质数

mod 1e9+7

范围

n,k,ei [1,1e4]

3s

1024mb

我的思路

这里质数只要用来表示不同, 与质数具体值无关

相当于问题是 k维度向量 = $(e_1,e_2,\cdots,e_k)$

把它拆成 有序的n个 k维非负向量的和, 且每个向量不能是全是偶数. 的方案数

---

之前有了解到给你1e9+7不给你998244353 就是不让用ntt

---

有点像生成方程

一个数的选择$E_i$的分解就是 $(1+x^1+x^2+…x^{E_1})$ , 这个感觉更大也行(选了也没用), 就是$\frac{1}{1-x}$

不让选择全偶数, 就是 $(1+x^2+x^4+\cdots)(1+y^2+y^4+\cdots)\cdots = \frac{1}{1-x^2}\frac{1}{1-y^2}\frac{1}{1-z^2}\cdots$

要求的就是 $[x^{E_1}y^{E_2}z^{E_3}\cdots]$ 的系数

$ans = [x^{E_1}y^{E_2}z^{E_3}\cdots] (\frac{1}{1-x}\frac{1}{1-y}\frac{1}{1-z}\cdots - \frac{1}{1-x^2}\frac{1}{1-y^2}\frac{1}{1-z^2}\cdots )^n$

$= [x^{E_1}y^{E_2}z^{E_3}\cdots] \sum_{i=0}^n \binom{n}{i} (\frac{1}{1-x}\frac{1}{1-y}\frac{1}{1-z}\cdots)^i (-\frac{1}{1-x^2}\frac{1}{1-y^2}\frac{1}{1-z^2}\cdots )^{n-i}$

对于第i项的 可以拆出 $x^{E_1}^i(\frac{1}{1-x^2})^{n-i}$

然后把这些 $x,y,z$的乘起来, 再乘上$\binom{n}{i} (-1)^{n-i}$ 就可以了

负二项式定理

$(1+x)^{-d} = \sum_{n=0}^{\infty} (-1)^n \binom{d+n-1}{n}x^n$

$(\frac{1}{1-x})^i = (1-x)^{-i} = \sum_{j=0}^{\infty} \binom{i+j-1}{j}x^j$

$(\frac{1}{1-x^2})^{n-i} = (1-x^2)^{-(n-i)} = \sum_{j=0}^{\infty} \binom{n-i+j-1}{j}x^{2j}$

$[x^{E_1}] (\sum_{j=0}^{\infty} \binom{i+j-1}{j}x^j)(\sum_{j=0}^{\infty} \binom{n-i+j-1}{j}x^{2j})$

---

看起来 for 外层的i=1..n 要1e4, 然后这里 遍历k 也要1e4

所以对于给定i 这个乘积要是算出来在1e4 预处理掉, 就可以ac

问题就是对于给定$i$ 这个$(\frac{1}{1-x})^i(\frac{1}{1-x^2})^{n-i}=(\sum_{j=0}^{\infty} \binom{i+j-1}{j}x^j)(\sum_{j=0}^{\infty} \binom{n-i+j-1}{j}x^{2j})$ 如何算出

其实想麻烦了, 先不需要二项式定理, 首先不能ntt, 然后, 即使可以多个log也无法接受

$(\frac{1}{1-x})^i(\frac{1}{1-x^2})^{n-i} = (\frac{1}{1-x})^i(\frac{1}{1-x^2})^{n}(\frac{1}{1-x^2})^{-i} = (\frac{1-x^2}{1-x})^i(\frac{1}{1-x^2})^{n} = (1+x)^i(\frac{1}{1-x^2})^{n}$

所以随着i 增大, 每次 乘上(1+x), 就是 a[i] = a[i] + a[i-1]

这里 只有初始化, i=0时 ,初始使用 二项式定理

---

综上, 初始化

$a_j = [x^j] (\frac{1}{1-x^2})^n =[x^j]\sum_{t=0}^{\infty} \binom{n+t-1}{t}x^{2t}$

$i$ 增加 $a_j = a_j+a_{j-1}$, 贡献$\binom{n}{i} (-1)^{n-i} \prod_{j=1}^k a_{E_j}$

代码

https://atcoder.jp/contests/abc285/submissions/38272090

#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=1e9+7;
using mint = atcoder::static_modint<MOD>;
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;}

const int N=20000;
int e[10010]; // 拆解
mint fac[N+10]={1};
mint ifac[N+10];
mint a[10010];
mint binom(int n,int m) { return fac[n]*ifac[m]*ifac[n-m];}
int main(){
  rep(i,1,N+1) fac[i]=fac[i-1]*i;
  ifac[N]=fac[N].inv();
  per(i,0,N) ifac[i]=ifac[i+1]*(i+1);

  int n=read(); // 1e4
  int k=read(); // 1e4
  rep(i,0,k) e[i]=read();
  mint ans=0;
  rep(j,0,10000+1) if(j%2==0) a[j] = binom(n+j/2-1,j/2); // (1/(1-x^2))^n
  rep(i,0,n+1){
    mint c=binom(n,i)*((n-i)%2==0?1:-1); // binom(n,i) (-1)^{n-i}
    rep(j,0,k) c*=a[e[j]];
    ans+=c;
    per(j,1,10000+1) a[j]+=a[j-1]; // *(1+x)
  }
  printf("%d\n",ans.val());
  return 0;
}

总结

G

前面这几个形状的网络流都能想到, 但都不能直接出答案

网络流 套路又复习了一次a (maximum) flow problem with minimum capacities

其实从 2一定要, 不应该没想到转化成$\ge 1$ 的这种下界表示形式

Ex

第二次自己推出Ex, 虽然耗时比较久(看提交时间差是1h13min). 感觉学会生成函数以后 这题没啥难的, 主要是不熟练时间还用得久, 甚至怀疑3192的评分是否严重虚高

参考

官方题解

snuke 日文 Maximum flow with minimum capacities