Atcoder abc279

發表於 更新於 分類於 ， Disqus： 文章字數： 1.3k 所需閱讀時間 ≈ 4 分鐘
Ex(Pentagonal Number Theorem, 广义二项式定理, Lucas' Theorem)

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

Ex - Sum of Prod of Min

给定正整数, n,m, 保证 $m \in [n,2n]$

对所有长n 且和为m的正整数序列S, $f(S) = \prod_{i=1}^n min(i,S_i)$

输出 $\sum_S f(S) \bmod 200003$

范围

$n \in [1,10^{12}]$

2s

1024mb

我的思路

这n 是真的大

但是也还好, 因为 sqrt(n) 大概是10^6

而注意到$\min [n,2n]$

而每个数要是正数, 所以$S_i > i$ 的不会超过 $O(sqrt(n))$ 个!

dp[第c个超过] = vector{最后超过的i, 剩余 > 1的部分, 前面乘积}

这状态感觉也少不了

一个是 当前超过的是啥, 前面的乘积, 自由的状态, 剩余的未分配数

等一下,上面读错题了, 是min不是max

题解

答案 为 $[x^M]\ \prod_{i=1}^{N} (x+2x^2+3x^3+\dots+ix^i+ix^{i+1}+ix^{i+2}+\dots).$

很显然, i表示 第i个的值的选择情况, 幂次为实际选的数, 系数为乘法贡献, M为实际选的总和

然后幂次大于 i的 系数就都是i了, 小于等于的就是本身

$= [x^M] \prod_{i=1}^{N} i(x+x^2+x^3+\cdots) - ((i-1)x+(i-2)x^2+(i-3)x^3+\dots+(1)x^{i-1})$

$= [x^M] \prod_{i=1}^{N} \frac{ix}{1-x} + \frac{x(-x^i+i(x-1)+1)}{(x-1)^2}$

$= [x^M] \prod_{i=1}^{N} \frac{x(1-x^i)}{(1-x)^2}$

$= [x^{M-N}] \prod_{i=1}^{N} \frac{(1-x^i)}{(1-x)^2}$

$= [x^{M-N}] \frac{\prod_{i=1}^{N} (1-x^i)}{(1-x)^{2N}}$

!!! 注意到的是分子上 通过五边形数定理 只有$O(\sqrt{N})$ 个幂次系数不为$0$

$= [x^{M-N}] \frac{\sum_{i=1}^{k} a_k x^{e_k}}{(1-x)^{2N}}$

然后 配合 广义二项式定理 + Lucas’ Theorem 就可以搞了

代码

https://atcoder.jp/contests/abc279/submissions/36912683

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

mint fac[MOD]={1};
mint ifac[MOD];
mint binom(ll n,ll m){
  if(m > n) return 0;
  if(n >= MOD) return binom(n/MOD,m/MOD)*binom(n%MOD,m%MOD);// lucas
  return fac[n]*ifac[m]*ifac[n-m];
}

int main(){
  ll n,m;
  std::cin>>n>>m;
  for(int i=1;i<MOD;i++)fac[i]=fac[i-1]*i;
  ifac[MOD-1]=fac[MOD-1].inv();
  for(int i=MOD-2;i>=0;i--)ifac[i]=ifac[i+1]*(i+1);
  mint ans=0;
  auto calc=[&](ll k){
    ll pwr = m-n-k*(3*k-1)/2; // Pentagonal Number Theorem, O(sqrt(n))
    if(pwr < 0) return false;
    ans += binom(2*n+pwr-1,pwr)*((k&1)?-1:1);// (-1)^k * (-1)^pwr * binom(-2n,pwr)
    return true;
  };
  for(ll k=0;calc(k);k++);
  for(ll k=-1;calc(k);k--);
  printf("%d\n",ans.val());
  return 0;
}

欧拉 五边形数定理 Pentagonal Number Theorem

$\displaystyle \prod_{i=1}^{\infty} (1-x^i) = \sum_{n=-\infty}^{\infty} (-1)^nx^{\frac{n(3n-1)}{2}}.$

显然, 要证明就是 n 的 拆分成 奇数个不同的正整数和的个数 * -1 + 偶数个不同的正整数和的个数 * 1 = -1/0/1

思路方向就是 想办法建立 奇偶拆分之间的一一对应, 这样只有特殊的1个无法匹配的话, 就贡献1或-1

我拆不出来

Franklin’s bijective proof

Ferrers 图

1
2
3
4
5
xxxxxx
xxxxx
xxxx
xxx
oo

底部个数记为m

1
2
3
4
xxxxxxo
xxxxxo
xxxx
xxx

顶部右侧45度 记作s

性质:

若 m > s 则 把右侧45度 放到底部, 且只能操作一次(因为放完以后一定 news >= s = newm)

若 m <= s, 考虑把底部移动到右边, 同样至多操作一次(newm > m = news), 但是注意特殊情况 底部和45度共用一个点时 无法操作

注意到上面能操作的时候 奇偶会改变, 所以奇偶建立了一一映射, 而至多有1种不满足

1
2
3
xxxxx
xxxx
xxx

那么个数是 $\frac{s+(2s-1))s}{2}$ (简单的梯形公式)

贡献是$(-1)^s$

得证

注意幂次是$O(s^2)$的, 换句话说, 反过来就是指定了幂次上界以后,就是$O(根号上界)$ 个的非零系数

广义二项式定理

牛顿广义二项式定理

$(x+y)^{\alpha} = \sum_{k=0}^{\infty} \binom{\alpha}{k} x^{\alpha-k}y^k$

其中 $\binom{\alpha}{k} = \frac{\alpha(\alpha - 1)\cdots(\alpha-k+1)}{k!}$

所以$\alpha$ 为负整数时

$\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}$

Lucas’ Theorem

用来求 $\binom{n}{m} \bmod p$, 其中$p$ 是质数

$\binom{sp+q}{tp+r} \equiv \binom{s}{t}\binom{q}{r} \pmod{p}$

proof

$p$是质数 显然 $i \in [1,p-1]$ 时, $\binom{p}{i} \equiv 0 \pmod{p}$

$(1+x)^{sp+q} \equiv ((1+x)^p)^s \cdot (1+x)^q$

$\equiv (1+x^p)^s \cdot (1+x)^q $

$\equiv (\sum_{i=0}^s \binom{s}{i} x^{ip})(\sum_{j=0}^q \binom{q}{j} x^j)$

要求$tp+r$ 的系数, 显然 左边贡献的都是$p$的倍数的, 右边贡献的是小于p的

得证

总结

这个G一个int overflow找了一年, 没看Ex

Ex

五边形数定理:

五边形数定理作为雅可比三元积的特例出现。

干 第一次又读错题目了, 读成了max,结果是min

不过还是缺少 去向生成函数的方向思考, 即使看错成max,也可以同样去建立方程(至于能不能算另说), 没去朝这个方向想真是不应该

广义二项式定理, 好像之前几次有涉及一点,这次终于把它补了

Lucas 定理

参考

官方题解

Mathologer Youtube Euler’s pentagonal formula

wikipedia Pentagonal number theorem

百度百科 二项式定理