https://atcoder.jp/contests/abc297/tasks
Ex - Diff Adjacent
正整数序列，和为N, 没有相邻元素相等
求所有满足的序列的长度 的和 mod 998244353
n 2e5
我的思路
~~2e5 打表啊 ~~
f(m,n) = 长度为m,和=n,满足没有相邻的方案数
ans(n) = sum m f(m,n)
g(m,n,v) = 长度为m, 和=n, 最后一个数为v, 满足没有相邻相同的方案数
f(m,n) = sum g(m,n,1…)
g(1,n,n) = 1
g(1,n,!=n)=0
g(m,n,v) = sum g(m-1,n-v, != v)
注意到转移和m无关, 所以相当于初始矩阵经过 m 次矩阵乘法以后得到的
1
2
3
4
5
6
7
8
| 初始(1行n^2列)
转换^m
m (对应第n行的是m,非n行的是0)
0
0
m
0
0
|
然而直接的话，矩阵大小是((n^2)^2) 因为转移每次 都并不是行列对齐
n^2都不行，更别说n^4还要乘法了
而注意到最左和最右的两个行/列矩阵，非零元不超过n
能否靠这个简化
另一些思路，有容斥相邻位置，但是2^{位置}次方吗?
不要等于，换成 f(=n) = f(<=n) - f(<= n-1)
中间想拆成生成函数表示，但是没有拆成功
长度之和 就是每个位置贡献1, 能不能拆
虽然11不能相邻，但是12间隔还是长度能达到 2n/3
题解
如果先不看长度
f(n) = 和为n的无相邻相等序列的方案数
// 注: 这里直接简单可以看成容斥。也可以属性(后缀长度l是1, 而对于长度l的小于的部分 奇偶抵消，所以 -1 幂次的系数和 最终还是 -1或1)
对于最后一位放1
f(n) += [...]1 - [...]11 + [...]111 - ... = $\sum_{i \ge 1} (-1)^{i-1} f(n-1\cdot i)$
对于最后一位放2
f(n) += [...]2 - [...]22 + [...]22 - ... = $\sum_{i \ge 1} (-1)^{i-1} f(n-2\cdot i)$
对于最后一位放v
f(n) += [...]v - [...]vv + [...]vv - ... = $\sum_{i \ge 1} (-1)^{i-1} f(n-v\cdot i)$
$f(n) = \sum_{v\ge 1} \sum_{i \ge 1} (-1)^{i-1} f(n-v\cdot i)$
$= \sum_{j=i\cdot v \in [1,n]} \sum_{i \ge 1, i|j} (-1)^{i-1} f(n-j)$
$= \sum_{j=i\cdot v \in [1,n]} f(n-j) \sum_{i \ge 1, i|j} (-1)^{i-1}$
所以, $F(x) = 1+F \star G$, $[x^n]G(x) = \sum_{i \ge 1, i|n} (-1)^{i-1}$
即$G(x) = \sum_{n\ge 1} (\sum_{i \ge 1, i|n} (-1)^{i-1} )x^n$
$= \sum_{i\ge 1} (\sum_{n \ge 1, i|n} (-1)^{i-1} )x^n$
$= \sum_{i\ge 1} (\sum_{v \ge 1} (-1)^{i-1} )x^{iv}$
$F=\frac{1}{1-G}$
$f(N,M)=[x^Ny^M]F(x,y) =$ 和为$N$长度$M$ 的方案数
在生成函数上 做容斥,同样是对于最后一位放什么数字
对于最后一位放$j$
$f(N,M) = \sum_{j\ge 1} (f(N-j,M-1) - f(N-2j,M-2) + f(N-3j,M-3) - \cdots )$
$=\sum_{j\ge 1} \sum_{i\ge 1} (-1)^{i-1} f(N-ij,M-i)$
表达式上推起来能推，但是还是不够显然
从意义上 就是 F[合法] + G[非法连续j]对应$F\star G$
所以也有$F=1+F\star G$
$F=\frac{1}{1-G}$
$\displaystyle G(x,y) = \sum_{i=1}^{\infty} \sum_{j=1}^{\infty} (-1)^{j-1}x^{ij}y^{j} = \sum_{i=1}^{\infty} \frac{x^iy}{1+x^iy}$
考虑生成函数$[x^N]H(x)=$ 和为N的合法序列的长度和
那么 $\displaystyle [x^N]H(x)= \sum_{M\ge 1} M [x^Ny^M]F(x,y)$
$\displaystyle = \sum_{M\ge 1} [x^Ny^{M-1}]\frac{\partial}{\partial y}F(x, y)$
$\displaystyle = [x^N] (\frac{\partial}{\partial y}F(x, y) |_{y=1} )$
$\displaystyle = [x^N] (\frac{\partial}{\partial y}(\frac{1}{1-G(x,y)}) |_{y=1} )$
$\displaystyle = [x^N] (\frac{\frac{\partial}{\partial y} (G(x, y) - 1)}{(1-G(x, y))^2}) |_{y=1} )$
$\displaystyle = [x^N] (\frac{\frac{\partial}{\partial y} (\sum_{i=1}^{\infty} \frac{x^iy}{1+x^iy} - 1)}{(1-\sum_{i=1}^{\infty} \frac{x^iy}{1+x^iy})^2}) |_{y=1} )$
$\displaystyle = [x^N] (\frac{ \sum_{i=1}^{\infty} \frac{x^i}{(1+x^iy)^2}}{(1-\sum_{i=1}^{\infty} \frac{x^iy}{1+x^iy})^2}) |_{y=1} )$
$\displaystyle = [x^N] \frac{ \sum_{i=1}^{\infty} \frac{x^i}{(1+x^i)^2}}{(1-\sum_{i=1}^{\infty} \frac{x^i}{1+x^i})^2}$
然而我不懂题解写成这样要干嘛，这样看上去并不好计算(但是够简洁), 还是直接处理G就足够计算了
$\displaystyle = [x^N] \frac{ \frac{\partial}{\partial y} G(x,y) |_{y=1}}{(1-G(x,y=1))^2}$
代码
https://atcoder.jp/contests/abc297/submissions/42048626
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
| #include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
namespace CMM{
template<class T,int MOD>
class InvFacBinom{
std::vector<T> _inv;
int _n;
public:
std::vector<T> fac;
std::vector<T> ifac;
InvFacBinom(int n):_n(n){
fac = std::vector<T> (n+1,1);
_inv = std::vector<T> (n+1,1);
ifac = std::vector<T> (n+1,1);
for(int i=1;i<=n;i++) fac[i] = fac[i-1] * i;
for(int i=2;i<=n;i++) _inv[i] = (MOD-MOD/i) * _inv[MOD%i];
for(int i=1;i<=n;i++) ifac[i] = ifac[i-1] * _inv[i];
}
T inv(int v)const{
assert(v > 0 && v <= _n && v < MOD);
return _inv[v];
}
T binom(int n,int m)const{ return (m>n||m<0)?0:fac[n] * ifac[m] * ifac[n-m]; }
};
}
namespace CMM{
template<class T>
class Poly{
std::vector<T>_d;
public:
Poly(const std::vector<T> &d={}):_d(d){};
friend Poly operator+(const Poly&p0,const Poly&p1){
std::vector<T>r=p0._d;
if(p1._d.size()>r.size())r.resize(p1._d.size());
for(int i=0;i<(int)p1._d.size();i++)r[i]+=p1._d[i];
return r;
}
friend Poly operator-(const Poly&p0,const Poly&p1){
std::vector<T>r=p0._d;
if(p1._d.size()>r.size())r.resize(p1._d.size());
for(int i=0;i<(int)p1._d.size();i++)r[i]-=p1._d[i];
return r;
}
friend Poly operator*(const Poly&p0,const Poly&p1){
return atcoder::convolution(p0._d,p1._d);
}
std::vector<T> coef()const{
return _d;
}
void Print() const{
for(auto v:_d) printf("%d ",v.val());
printf("\n");
}
template<int MOD>
static Poly PolyEX(const InvFacBinom<T,MOD>&ifb,int n){
std::vector<T> p(n+1,0);
for(int i=0;i<=n;i++)p[i]=ifb.ifac[i];
return p;
}
template<int MOD>
static Poly PolyENegX(const InvFacBinom<T,MOD>&ifb,int n){
std::vector<T> p(n+1,0);
for(int i=0;i<=n;i++)p[i]=ifb.ifac[i]*(i%2?-1:1);
return p;
}
Poly Rev(int n) const{
std::vector<T>r=_d;
if(n+1>(int)r.size())r.resize(n+1);
for(int i=0;i<(int)r.size()/2;i++)std::swap(r[i],r[r.size()-1-i]);
return r;
}
Poly Modn(int n) const{
std::vector<T>r=_d;
if((int)r.size()>n) r.resize(n);
return r;
}
Poly Inv(int n) const{
assert(_d[0] != 0);
Poly r = std::vector<T>{_d[0].inv()};
for(int pwr=1;pwr<n;pwr*=2){
r = r.Modn(pwr);
r = r * (Poly({2}) - r * _d);
}
return r.Modn(n);
}
Poly Norm() const{
std::vector<T>r=_d;
while(r.size() > 1 && r.back()==0)r.pop_back();
return r;
}
std::pair<Poly,Poly> Div(const Poly<T>& B) const{
const Poly& A=*this;
int m=B._d.size()-1;
int n=std::max(A._d.size()-1,B._d.size()-1);
auto C=(A.Rev(n)*(B.Rev(m)).Inv(n-m+1)).Modn(n-m+1).Rev(n-m);
auto D=(A-B*C).Norm();
return {C,D};
}
std::vector<T> MPE(const std::vector<T>& a) const{
int sz=a.size();
std::vector<std::vector<Poly > > tree = {{}};
for(auto v:a)tree[0].push_back(std::vector<T>{-v,1});
while((tree[0].size() & (tree[0].size()-1)))tree[0].push_back(std::vector<T>{1});
while(tree.back().size() > 1){
std::vector<Poly >row={};
const auto&b=tree.back();
for(int i=0;i<(int)b.size()/2;i++) row.push_back(b[i*2]*b[i*2+1]);
tree.push_back(row);
}
std::vector<Poly > h = {Poly(_d)};
for(int i=tree.size()-1;i>=0;i--){
std::vector<Poly > nexth = {};
for(int j=0;j<(int)tree[i].size();j++) nexth.push_back(h[j/2].Div(tree[i][j]).second);
h = nexth;
}
std::vector<T> res;
for(int i=0;i<sz;i++) res.push_back(h[i]._d[0]);
return res;
}
};
};
using namespace CMM;
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 main(){
using namespace std;
using mint=atcoder::modint998244353;
const int MOD=998244353;
using poly=CMM::Poly<mint>;
int n=read();
InvFacBinom<mint,MOD> ifb(n+1);
vector<mint> g(n + 1);
vector<mint> dg(n + 1);
rep(i,1,n+1) rep(j,1,n/i+1){
dg[i * j] = dg[i * j] + ((j & 1) ? 1 : -1) * j;
g[i * j] = g[i * j] + ((j & 1) ? 1 : -1);
}
g[0] -= 1;
poly h = poly{dg} * (poly{g} * poly{g}).Inv(n);
printf("%d\n",h.coef()[n].val());
return 0;
}
|
总结
Ex
哦，双变量生成函数，学过没用过，第一次用
学了属性容斥，把最简单的容斥忘记了。。。
没有很懂, $F(x)=\frac{1}{1-C(x)}$有什么快速可见的逻辑吗，感觉我上面推半天，题解就一句话
后面这些偏导数，正着想没想到，反过来看也挺自然，第一次见
参考
官方题解