Atcoder arc111

發表於 更新於 分類於 ， Disqus： 文章字數： 3.2k 所需閱讀時間 ≈ 11 分鐘
E(生成函数)F(变进制数,mod,exgcd,分类讨论,最短路)

https://atcoder.jp/contests/arc112

E - Cigar Box

初始 a=[1...n]

每次操作 把一个元素移动到开头或结尾

给定m次操作后得到的a

问 有多少个具体的方案 能得到目标的a mod 998244353

$n\in [2,3000]$

m 3000

2s

1024mb

我的思路

m 只要大于等于n 就所有方案都可以

所以n的大小在这里更关键3000的话，难道要n^2左右的算法？

如果倒着来就是每次选开头或结尾的 插入到序列中任何位置

似乎没有变简单

如果把每个数字最后一次操作的时刻记录下来

对应到最后数组中的位置，一定是连续的

因为 最终数组 总可以 划分成 [左侧放入][未操作][右侧放入]， 每段长度可以为0

而对于单侧放入的，靠外的 最后一次操作时间 一定 晚于 靠内的

所以可以

dp[l][r][t] 表示 结果数组中[l..r] 这一段最后操作的时间为t的 到t时刻的方案数

初始状态

讨论一下 未操作的一段 如果非0， 首先一定要满足 单调递增，那么 这一段的对应dp[l][r][0]+=1

否则未操作的一段长度为0,那么首个停止的放入时 可以从左也可以从右

dp[l][l][t] += 2*(2n)^{t-1}, 前t-1随意操作，最后一次操作a[l]

然后转移

dp[l][r][t] => dp[l-1][r][t1], 要贡献，也就是(t+1..t1-1) 这一段随便操作，最后一次操作a[l-1]

dp[l-1][r][t1] += dp[l][r][t] * (2(n-(r-l+1)))^(t1-t-1) * 1

同理 从右侧加入

dp[l][r+1][t1] += dp[l][r][t] * (2(n-(r-l+1)))^(t1-t-1) * 1

ans = dp[1][n][m]

问题是状态是$O(n^2m)$的，而转移需要枚举$t_1$,所以时间是$O(n^2m^2)$的，会tle

一个观察是， 上面除了初始化和具体的l,r有关系，而后续的 似乎没关系，但实际上 受到边界的影响

$dp_{l,r,t,l<r,t>0}=\sum_{t_0 < t} dp_{l+1,r,t_0}(2(n-(r-l)))^{t-t_0-1}+dp_{l,r-1,t_0}(2(n-(r-l)))^{t-t_0-1}$

$\displaystyle dp_{l,r,t,l<r,t>0}=(2(n-(r-l)))^{t-1}\sum_{t_0 < t} \frac{dp_{l+1,r,t_0}+dp_{l,r-1,t_0}}{(2(n-(r-l)))^{t_0}}$

这样的话 可以前缀和，时间复杂度$O(n^3)$

再从贡献的角度来看，初始是[l,r,t]的情况

那么 每次到下一个状态 中间的任意的可选次数都是 每次-1， 与选左选右没有关系

$(2(n-(r-l+1)))^{t_0}(2(n-(r-l+1)-1))^{t_1}\cdots (2)^{t_{n-(r-l+1)}}$

而其中 有$(l-1)$次是 选左边，所以$\binom{n-(r-l+1)}{l-1}$ 个 与左右相关的顺序

然后 $t+\sum_{i=0}^{n-(r-l+1)} (t_i+1)= m$

而初始状态 只有 全操作过$l=r,t>0$和 有不动块$t=0$两种情况（注意重叠

所以 需要计算 $f(t,s)=(2(n-s))^{t_0}(2(n-s-1))^{t_1}\cdots (2)^{t_{n-s}},t+\sum_{i=0}^{n-s} (t_i+1)= m$

$ans = \sum_{p=1}^{n} \sum_{t=1}^{m} 2(2n)^{t-1}\binom{n-1}{p-1}f(t,1)+\sum_{l,r,a[l\cdots r]单增} \binom{n-(r-l+1)}{l-1}f(0,r-l+1)$

$f$看着有点怪，换个角度$f(t,s) = g(m-t,n-s)$

$g(t,s)=f(m-t,n-s)=(2(s))^{t_0}(2(s-1))^{t_1}\cdots (2)^{t_{s}},\sum_{i=0}^{s} (t_i+1)=t$

$ans = \sum_{p=1}^{n} \sum_{t=1}^{m} 2(2n)^{t-1}\binom{n-1}{p-1}g(m-t,n-1)+\sum_{l,r,a[l\cdots r]单增} \binom{n-(r-l+1)}{l-1}g(m-0,n-(r-l+1))$

$g(t,s)=\sum_{t_0=0}^{t-1}(2s)^{t_0} g(t-(t_0+1),s-1),\sum_{i=0}^{s} (t_i+1)=t$

$g(t,1) = 2^{t-1}$

令$g_s(x)=\sum_{t=1}^{\infty} g(t,s)x^t$, 即$[x^0]g_s(x)=0$

$[x^t]g_s(x) = \sum_{t_0=0}^{t-1}(2s)^{t_0} [x^{t-(t_0+1)}] g_{s-1}(x)$

$[x^t]h_s(x)=(2s)^{t_0}$

$[x^t]g_s(x) = \sum_{t_0=0}^{t-1} [x^t]h_s(x) [x^{t-(t_0+1)}] g_{s-1}(x)$

$g_s(x) = x h_s(x)g_{s-1}(x)$

$g_1(x)=\sum_{i=1}^{\infty} g(i,1)x^i=\sum_{i=1}^{\infty} 2^{i-1}x^i$

令$H_s(x)=xh_s(x)=x\sum_{i=0}^{\infty} (2s)^{i} x^i=\sum_{i=1}^{\infty} (2s)^{i-1} x^i$

注意到 $g_1(x)=H_1(x)$

$g_s(x)=\prod_{i=1}^{s} H_i(x)$

应该就过了

代码

https://atcoder.jp/contests/arc112/submissions/50523401

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
#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
const int MOD=998244353;
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++)
ll read(){ll r;scanf("%lld",&r);return r;}
using poly=vector<mint>;
void add(poly&p,int pwr,mint v){ if(!(pwr < (int)p.size())) {p.resize(pwr+1);} p[pwr]+=v; }
const int N=3000;
mint binom[N+10][N+10];
int main(){
  rep(i,0,N+1) binom[i][0]=1;
  rep(i,1,N+1) rep(j,1,i+1) binom[i][j] = binom[i-1][j-1]+binom[i-1][j];
  int n=read();
  int m=read();
  vector<int> a(n+1,0);
  rep(i,1,n+1) a[i]=read();
  vector g(n+1,vector<mint>(m+1,0)); // g[s](x) = prod h[1..s](x), g[可选大小][剩余次数]
  vector<mint>hs(m+1,0); // [x^i]h[s](x) = (2s)^{i-1};
  g[0][0] = 1; // g_0(x)=1
  rep(s,1,n+1) {
    hs[1] = 1;
    rep(i,2,m+1) hs[i]=hs[i-1]*(2*s);
    g[s]=convolution(g[s-1],hs);
    while((int)g[s].size() > m+1) g[s].pop_back();
  }
  mint ans = 0;
  rep(l,1,n+1) { // 全部操作，最先不操作的是l
    mint n2t1 = 1; // (2n)^{t-1}
    rep(t,1,m+1) {
      ans += n2t1*2*binom[n-1][l-1]*g[n-1][m-t]; // t时刻[l,l]固定
      n2t1*=2*n;
    }
  }
  rep(l,1,n+1) rep(r,l,n+1) { // [l..r]不操作且单增
    if(r != l and a[r] < a[r-1]) break;
    ans += binom[n-(r-l+1)][l-1] * g[n-(r-l+1)][m-0]; // 0时刻[l,r]固定
  }
  printf("%d",ans.val());
  return 0;
}

F - Die Siedler

n种卡, m种卡包（至少一张），卡包i中有第j种卡$s_{i,j}$张

snuke 初始第j种卡有$c_j$张,(至少一张)，可以任意次操作

  • 类型1: 获得任意指定的一种卡包所有卡
  • 类型2: 选一个卡类型j, 丢弃这种类型$2j$张(他必须原来有至少$2j$张), 同时$j+1$循环右移的卡多1张,

问 最少最终有多少张

$n\in [2,16]$

$m\in [1,50]$

$0\le s_{i,j},c_j < 2j$

6s

1024mb

我的思路

顺序上 因为最终目标尽量少，而第二种操作 需要被指定的j类型的卡至少$2j$才能操作，

所以认为先 获得要获得的卡包，然后多次进行类型2的操作

而类型2的操作的结果是唯一的，因为它让自己下降，后一个增加1,所以只要操作总数都会下降，而一个位置如果当前可以下降，那么如果现在不下降未来总是依然可以下降的，所以每个可下降的总会下降，所以

$a_j$表示操作后类型$j$的张数

把满足 $\forall j, a_j < 2j$的状态称作 规则状态，$ans=min(|规则状态|)$

一个tle的想法是，规则状态数 $=n!2^n$, 而$n=16$时$=137’1195’9580’9996’8000$

而每个卡包 通过线性组合以后可以得到的规则状态 也就在这里面

不过线性组合的要求 是全是非负的

另一个想法就是 这是一个有循环变进制的数

也就是 (2n,2(n-1),...,2)为它的循环进制

那么 $m$ 个卡包不过是$m$个数

$c+\sum_{i}k_im_i,k_i\ge 0$ 在 变进制表示下的 各数位和 最小

一个没啥用的观察，就是$k_i$就是小于 一轮循环进制能表示的最大的数，和上面的状态的一样的结论，因为 抽屉原理，而这个数字很大

不过转化成进制以后有一个想法是 能否从2来看，因为目前进制都是2的倍数，那么如果$k_i=2t_i+1,2t_i$去讨论奇偶

或者说 bitmask $2^{16}=65536$去尝试不同k的奇偶，让剩余使用的k一定是偶数

这样处理的话 问题变成了 $nc=c+\sum_{i\in\mathrm{mask}} m_i$

$\mathrm{nc}$中的奇数的贡献也可以提取出来

那么问题直接缩减$2^{16}$倍

也就是 (n,(n-1),...,1)为它的循环进制, 然而$16!=20’9227’8988’8000$

还是 m个数，求和在循环进制下 的 数位和 最小

好像还是不太对

突然发现 如果所有 都是同进制的 都不太会

也就是 给定初始c, 和m个数， 要在指定2w进制下 的数位和最小要如何做?

想不出一点

题解

首先一样的结论，能下降一定下降

然后 题解的方程，就是按进制转换成数字

但这里多想了一点，这个数字另一个意义是 放在最低位，所以它可以 $\mod (2^nn!-1)$, 因为 每$2^nn!-1+1$个 又循环到最低位,

令$M=2^nn!-1$， 而只有 全0和全是进位减1时 才$\mod M=0$,显然,因为对应的就是$0\cdots M$

但题目保证了 手里非空

初始$c$个

显然 令$\begin{aligned} d = c ~(\text{mod gcd} (N,s_1,\dots,s_m)) ~\cdots (1) \end{aligned}$， 其中$s_i$就是每个数展开后的值

$d$在$1\cdots M$之间唯一表示

然后上

$\begin{aligned} \exists a_0\dots,a_m\in \mathbb{Z}, d - c = a_0M+a_1s_1+\dots +a_ms_m \cdots (1’) \end{aligned}$

而根据 扩展欧几里德，显然能找到 $a$使得上面有解，且通过调整a,使得$a_{>0} \ge 0$ 因为$a_0M+a_js_j=(a_0-s_j)M+(a_j+M)s_j$

而这里$a_0$对应$j=n$的降低，其它的对应到卡包的购买，而中间的降低是通过 进制自动完成了！

所以一定有解 $ans = d = c+k\gcd()$的对应值的 表示的数位和

令$g=gcd(M,s_{\cdots})$

$0 < ans=c+kg \pmod{g} \le M$ 对应的最小数位和

if $g > M/g$, 枚举$k$, $O(2^nn!/g)$ 最大$1.1 \cdot 10^9$ 说的6s 能跑???

if $g < M/g$

考虑 变成 广搜的最短路问题

0~g-1点 表示 mod g的结果

那么所有c+kg的取值 全部对应点 c%g

边是$v+2^{t}t!\pmod{g},t=0\cdots n-1$到$v\pmod{g}$

经过边 一次 表示减去了对应的值，那么从$c\pmod{g}$到0的最短路就是答案

因为如果 $c+kg$ 的数位和最小，那么 就是对应的数位 就对应了上面新建立的边的路径，所以答案一定能被表示

再 证明 最短路一定对应答案，沿着最短路把上面 $2^tt!$加起来，就对应了一个$\mod g =c$的值，而这些值 总是有对应k得到的

所以充分必要性证明了，O(gn)边 和 复杂度

其中要注意的是0到0的距离依然不是0!,所以可以反过来，每次增加，初始化增加1次的

代码

341ms python3

https://atcoder.jp/contests/arc112/submissions/50525410

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
import sys
readline = sys.stdin.buffer.readline
from math import gcd
n,m=map(int,readline().split())
w=[1] # w[i] = 2^i i!
for i in range(1,n+1):
    w.append(w[-1]*2*i)
def getvalue(): # 读取并转化成变进制
    a=list(map(int,readline().split()))
    return sum([w[i]*a[i] for i in range(n)])
c=getvalue() # 初始值
g=w[n]-1
for _ in range(m):
    g=gcd(g,getvalue())

if g<=(w[n]-1)//g: # g小， 建立0..g-1个点, 边(v+2^i i!)->v
    dist=[-1 for _ in range(g)] # dist[点] # 注意0的距离 不是0 且 >0
    q=[] # bfs 顺序
    def scan(v,d): # 从v出发, 新的距离为d
        for i in range(n):
            p = (v+w[i])%g
            if dist[p] == -1:
                dist[p] = d
                q.append(p)
    scan(0,1)
    head=0
    while head < len(q):
        v=q[head]
        head+=1
        scan(v,dist[v]+1)
    print(dist[c%g])
else: # g大, 枚举 d=c+kg
    ans=2*n*n
    for d in range((c-1)%g+1,w[n],g): # 不能全零
        ans=min(ans,sum([(d//w[i])%(2*(i+1)) for i in range(n)]))
    print(ans)

Ref

https://atcoder.jp/contests/arc112/editorial

总结

E: 生成函数,虽然写得有点久,但是自己搞出来了

F: 看了题解以后的确比E有趣多了，3432评分

这个mod 应该很显然的,没想到太不应该了

然后就是exgcd 的, 怎么说呢回头看也很显然，这里与其说是exgcd,不输说在上面的mod转换以后计算哪些值可以被表示，exgcd出现也很自然的

然后 就是 因数分析 和 分类讨论，最短路，这个最短路反而觉得可能是最可能想不到的点

最后就是 其实并没有 上面的1.1x1e9那么恶劣 wolframalpha 的分解告诉 要不然就很大，要不然就很小，所以才有了py还是300+ms就跑完了

$2^22!-1=7$

$2^{3}3-1!=47$

$2^{4}4-1!=383$

$2^{5}5-1!=11 × 349$

$2^{6}6-1!=11 × 59 × 71$

$2^{7}7-1!=331×1949$

$2^{8}8-1!=10321919$

$2^{9}9-1!=19×199×49139$

$2^{10}10-1!=19×757×258353$

$2^{11}11-1!=23×41×86690993$

$2^{12}12-1!=23^2×43×71×1214827$

$2^{13}13-1!=51011754393599$

$2^{14}14-1!=6421×222446522819$

$2^{15}15-1!=31×83×16653662530363$

$2^{16}16-1!=31×43×1028654132108003$