Atcoder arc059

發表於 更新於 分類於 ， Disqus： 文章字數： 595 所需閱讀時間 ≈ 2 分鐘
F(卷积,生成函数)

F - Unhappy Hacking

https://atcoder.jp/contests/arc059/tasks/arc059_d

操作 push(0),push(1),pop(),其中pop在空时也可以操作

给定0/1串,问有多少不同n次的操作序列 能得到s, 方案数mod1e9+7

n 5000

2s

256mb

我的思路

对于 开头 需要计算 多少次可以在空时pop的操作 得到长度0

对于 中间 需要计算 多少次不可以在空时pop的操作 得到长度0

那么 用生成函数表示

$[x^t]g_0(x)$ 表示 $t$次操作长度0的第一种操作

$[x^t]f_0(x)$ 表示 $t$次操作长度0的第二种操作

那么有$ans = [x^{n}] g_0(x) (\cdot x \cdot f_0(x))^{|s|}$

$= [x^{n}] g_0(x) \cdot x^{|s|} \cdot f_0(x)^{|s|}$

$= [x^{n-|s|}] g_0(x) \cdot f_0(x)^{|s|}$

后面直接多项式快速幂就好了，1e9+7 原根太小,没法ntt

代码

https://atcoder.jp/contests/arc059/submissions/50447532

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
45
46
47
#include <bits/stdc++.h>
const int MOD=1'000'000'000+7;
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;}
const int N = 5000;
char s[N+10];

vector<ll> polymul(const vector<ll> &v0,const vector<ll>&v1,int polymxpwr){
  vector<ll> ret(min(polymxpwr+1,(int)v0.size()+(int)v1.size()-1),0);
  rep(i,0,size(v0)) rep(j,0,size(v1)) if(i+j < (int)ret.size()) (ret[i+j]+=v0[i]*v1[j]%MOD)%=MOD;
  return ret;
}
// (t^pwr) % x^{polymxpwr+1}
vector<ll> polypwr(vector<ll> t,int pwr,int polymxpwr){
  vector<ll> ret={1};
  while(pwr){
    if(pwr&1) ret=polymul(ret,t,polymxpwr);
    t=polymul(t,t,polymxpwr);
    pwr/=2;
  }
  return ret;
}

int main(){  
  vector t(N+1,vector<ll>(N+1,0)); // tmp
  t[0][0] = 1;
  rep(i,0,N) rep(j,0,N+1) if(t[j][i]!=0) {
          (t[j+1]         [i+1]+=t[j][i]*2%MOD)%=MOD; // +1/+0
          (t[max(j-1,0ll)][i+1]+=t[j][i]      )%=MOD; // -1
  }
  auto g=t[0]; // g[剩余个数][操作次数] 允许=0时删减
  rep(i,0,N+1)rep(j,0,N+1) t[i][j]=0;
  t[0][0] = 1;
  rep(i,0,N) rep(j,0,N+1) if(t[j][i]!=0) {
          (t[j+1]         [i+1]+=t[j][i]*2%MOD)%=MOD; // +1/+0
    if(j) (t[max(j-1,0ll)][i+1]+=t[j][i]      )%=MOD; // -1
  }
  auto f=t[0]; // f[剩余个数][操作次数] 不允许=0时删减
  int n=read();
  scanf("%s",s);
  int sz=strlen(s);
  auto ans = polymul(g, polypwr(f,sz,n-sz),n-sz);
  printf("%lld\n",(((n-sz < (int)ans.size()) ? ans[n-sz] : 0 )+MOD)%MOD);
  return 0;
}

总结

会了生成函数 没啥难的，这里就是1e9+7意思就是不让用ntt,但是n 5000就是手动卷积就好了,纯水了一篇文章