JZOJ 6977 去南极

又是 dirty works……(

首先有 DP fn=sn+1(n3)ni=1(i1)(ni)(fk+fnk)

随便化一下可得 (n3)fn=(n3)sn+2ni=1(ni1)ifi

写成生成函数的形式就是 F(3)(x)=S(3)(x)+12(1x)2F(x)(1x)3F(3)12(1x)F=S(3)

我也不知道为什么定义算子 θF(x)=(1x)F(x)

(注意这里的定义和题解不一样)

然后可以发现 θ2F=(1x)2F(1x)Fθ3F=(1x)3F(3)3(1x)2F+(1x)F

因此 (θ3+3θ210θ)F=S(3)θ(θ2)(θ+5)F=(1x)3S(3)

Q=(θ+5)F,P=(θ2)Q,则有 {θP=(1x)3S(3)(θ2)Q=P(θ+5)F=Q

提取系数得 {(n+1)pn+1=npn+3sn+3(n+3)3_(n+1)qn+1=(n+2)qn+pn(n+1)fn=(n5)fn+qn

从第一条式子有 npn=2sn+2(n+2)3_

再代入第二条式子,展开得 qn+1n+2=qm+1m+2+n+1i=m+32si

再代入第三条式子,展开得 (n6)fn=(m+16)fm+1+qm+1m+2ni=m+2(i6)+ni=m+2(i6)ij=m+32sj

显然有 fm+1=sm+1,fm+2=sm+2

然后 pm+1=(m+2)fm+2(m4)fm+1

再一通乱算可以得到 fn=sn+12(n6)n1i=m+1fi(i+1)(i+2)((n+17)(i+27))

使用线段树维护即可。

代码:

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
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
const int N = 2e5 + 1;
const int mod = 998244353;
int L,q;
int a[N + 5],inv[N + 5];
int s1[N + 5],s2[N + 5];
namespace SEG
{
#define ls (p << 1)
#define rs (ls | 1)
struct node
{
int sum1,sum2;
int tag;
} seg[(N << 2) + 5];
inline void push(int p,int tl,int tr)
{
int mid = tl + tr >> 1;
if(seg[p].tag)
{
seg[ls].sum1 = (seg[ls].sum1 + (long long)seg[p].tag * (s1[mid] - s1[tl - 1] + mod)) % mod,
seg[ls].sum2 = (seg[ls].sum2 + (long long)seg[p].tag * (s2[mid] - s2[tl - 1] + mod)) % mod,
seg[ls].tag = (seg[ls].tag + seg[p].tag) % mod;
seg[rs].sum1 = (seg[rs].sum1 + (long long)seg[p].tag * (s1[tr] - s1[mid] + mod)) % mod,
seg[rs].sum2 = (seg[rs].sum2 + (long long)seg[p].tag * (s2[tr] - s2[mid] + mod)) % mod,
seg[rs].tag = (seg[rs].tag + seg[p].tag) % mod;
seg[p].tag = 0;
}
}
void update(int l,int r,int k,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
{
seg[p].sum1 = (seg[p].sum1 + (long long)k * (s1[tr] - s1[tl - 1] + mod)) % mod,
seg[p].sum2 = (seg[p].sum2 + (long long)k * (s2[tr] - s2[tl - 1] + mod)) % mod,
seg[p].tag = (seg[p].tag + k) % mod;
return ;
}
push(p,tl,tr);
int mid = tl + tr >> 1;
l <= mid && (update(l,r,k,ls,tl,mid),1);
r > mid && (update(l,r,k,rs,mid + 1,tr),1);
seg[p].sum1 = (seg[ls].sum1 + seg[rs].sum1) % mod,
seg[p].sum2 = (seg[ls].sum2 + seg[rs].sum2) % mod;
}
inline pair<int,int> operator+(const pair<int,int> &a,const pair<int,int> &b)
{
return make_pair((a.first + b.first) % mod,(a.second + b.second) % mod);
}
pair<int,int> query(int l,int r,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
return make_pair(seg[p].sum1,seg[p].sum2);
push(p,tl,tr);
int mid = tl + tr >> 1;
pair<int,int> ret(0,0);
l <= mid && (ret = ret + query(l,r,ls,tl,mid),1);
r > mid && (ret = ret + query(l,r,rs,mid + 1,tr),1);
return ret;
}
}
namespace BIT
{
#define lowbit(x) ((x) & -(x))
int c[N + 5];
inline void update(int x,int k)
{
for(;x <= L;x += lowbit(x))
c[x] = (c[x] + k) % mod;
}
inline void update(int l,int r,int k)
{
update(l,k),update(r + 1,(mod - k) % mod);
}
inline int query(int x)
{
int ret = 0;
for(;x;x -= lowbit(x))
ret = (ret + c[x]) % mod;
return ret;
}
}
int ans;
int main()
{
freopen("space.in","r",stdin),freopen("space.out","w",stdout);
scanf("%d%d",&L,&q),inv[1] = 1;
for(register int i = 2;i <= N;++i)
inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
for(register int i = 1;i <= L;++i)
scanf("%d",a + i),
s1[i] = (s1[i - 1] + (long long)inv[i + 1] * inv[i + 2]) % mod,
s2[i] = (s2[i - 1] + (long long)i * (i - 1) % mod * (i - 2) % mod * (i - 3) % mod * (i - 4) % mod * inv[5040]) % mod;
for(register int i = 1;i <= L;++i)
SEG::update(i,i,a[i],1,1,L),
BIT::update(i,i,a[i]);
for(int op,l,r,k,n,m;q;--q)
{
scanf("%d",&op);
if(!op)
scanf("%d%d%d",&l,&r,&k),
SEG::update(l,r,k,1,1,L),
BIT::update(l,r,k);
else
{
scanf("%d%d",&n,&m);
if(n <= max(m,5))
printf("%d\n",BIT::query(n));
else
{
pair<int,int> temp = SEG::query(m + 1,n - 1,1,1,L);
ans = (long long)temp.first * (n + 1) % mod * n % mod * (n - 1) % mod * (n - 2) % mod * (n - 3) % mod * (n - 4) % mod * (n - 5) % mod * inv[5040] % mod,
ans = (ans - temp.second + mod) % mod,
ans = (12LL * 720 * ans % mod * inv[n] % mod * inv[n - 1] % mod * inv[n - 2] % mod * inv[n - 3] % mod * inv[n - 4] % mod * inv[n - 5] + BIT::query(n)) % mod;
printf("%d\n",ans);
}
}
}
}

0 comments
Anonymous
Markdown is supported

Be the first person to leave a comment!