CF1731F Function Sum
The main idea of the topic
for a length of
no
no
sequence of n
a
a
a.
definition
l
i
l_i
li? means
i
i
i left than
a
i
a_i
ai? The number of small numbers, namely
l
i
=
∑
j
=
1
i
?
1
[
a
j
<
a
i
]
l_i=\sum\limits_{j=1}^{i-1}[a_j definition r i r_i ri? means i i i right than a i a_i ai? The number of large numbers, namely r i = ∑ j = i + 1 no [ a j > a i ] r_i=\sum\limits_{j=i + 1}^{n}[a_j>a_i] ri?=j=i + 1∑n?[aj?>ai?]
We call a position good if and only if
l
i
<
r
i
l_i for sequence a a a, define the function f ( a ) = ∑ i = 1 no a i [ a i i the s g o o d ] f(a)=\sum\limits_{i=1}^na_i[a_i \ is \ good] f(a)=i=1∑n? ai? [ai? is good]. Now given two integers no , k n,k n, k, please find out for all lengths no no and 1 ≤ a i ≤ k 1\leq a_i\leq k 1≤ai?≤k sequence a a a f ( a ) f(a) What is the sum of f(a). set up f i , j f_{i,j} fi,j? means the first i i i number is j j j is the contribution of the position to the answer. enumerated in i i i was less than a i a_i the number of numbers in ai? x x x and in i i after i is less than a i a_i the number of numbers in ai? the y the y y, then f i , j = j x ∑ x = 1 i ? 1 C i ? 1 x x ( j ? 1 ) x ( k ? j + 1 ) i ? 1 ? x ∑ the y = x + 1 no ? i C no ? i the y ( k ? j ) the y j no ? i ? the y f_{i,j}=j\times \sum\limits_{x=1}^{i-1}C_{i-1}^x\times (j-1)^x(k-j + 1 )^{i-1-x}\sum\limits_{y=x + 1}^{n-i}C_{n-i}^y(k-j)^yj^{n-i-y} fi,j?=j×x=1∑i?1?Ci?1x?×(j?1)x(k?j + 1)i?1?xy=x + 1∑n?i?Cn?iy ?(k?j)yjn?i?yProblem solution
then the answer is
∑
i
=
1
no
∑
j
=
1
k
f
i
,
j
\sum\limits_{i=1}^n\sum\limits_{j=1}^{k}f_{i,j}
i=1∑n?j=1∑k?fi,j?.
But such time complexity is too big, so we consider optimization.
observe above
f
i
,
j
f_{i,j}
fi,j?, which can be regarded as about
j
j
j in a polynomial, we find that the highest degree of this polynomial is
no
no
n.
set up
f
j
=
∑
i
=
1
no
f
i
,
j
F_j=\sum\limits_{i=1}^nf_{i,j}
Fj?=i=1∑n?fi,j?,
G
i
=
∑
j
=
1
i
f
j
G_i=\sum\limits_{j=1}^iF_j
Gi?=j=1∑i?Fj?. Then the answer is
G
k
G_{k}
Gk?.
because
f
i
,
j
f_{i,j}
fi,j?
j
j
The degree of the highest order term of j is
no
no
n, so
G
i
G_i
Gi?
i
i
The highest order term of i is
no
+
1
n + 1
n+1. We can use Lagrangian interpolation to find
no
+
2
n + 2
n + 2
G
G
The value of G can be found
G
(
k
)
G(k)
The value of G(k) is up.
The time complexity is
o
(
no
4
log
?
no
)
O(n^4\log n)
O(n4logn).
code
#include <bits/stdc++.h>
using namespace std;
const int N=55;
long long jc[105],ny[105],f[105];
long long mod=998244353;
long long mi(long long t,long long v){<!-- -->
if(!v) return 1;
long long re=mi(t,v/2);
re=re*re%mod;
if(v & amp;1) re=re*t%mod;
return re;
}
long long C(int x,int y){<!-- -->
return jc[x]*ny[y]%mod*ny[x-y]%mod;
}
void init(){<!-- -->
jc[0]=1;
for(int i=1;i<=N;i + + ) jc[i]=jc[i-1]*i%mod;
ny[N]=mi(jc[N],mod-2);
for(int i=N-1;i>=0;i--) ny[i]=ny[i + 1]*(i + 1)%mod;
}
long long dd(long long n, long long k){<!-- -->
long long re=0;
for(int i=1;i<=n;i + + ){<!-- -->
long long p=f[i],q=1;
for(int j=1;j<=n;j + + ){<!-- -->
if(i!=j){<!-- -->
p=p*(k-j)%mod;q=q*(i-j+mod)%mod;
}
}
re=(re + p*mi(q,mod-2)%mod)%mod;
}
return re;
}
int main()
{<!-- -->
long long n,k;
init();
scanf("%lld%lld", &n, &k);
for(int t=1;t<=min(n + 2,k);t ++ ){<!-- -->
for(int i=1;i<=n;i + + ){<!-- -->
for(int x=0;x<=i-1;x + + ){<!-- -->
for(int y=x + 1;y<=n-i;y + + ){<!-- -->
f[t]=(f[t] + C(i-1,x)*mi(t-1,x)%mod*mi(k-t+1,i-1-x)%mod
*C(n-i,y)%mod*mi(k-t,y)%mod*mi(t,n-i-y)%mod)%mod;
}
}
}
f[t]=t*f[t]%mod;
}
for(int i=1;i<=n + 2;i + + ) f[i]=(f[i] + f[i-1])%mod;
if(k<=n + 2) printf("%lld",f[k]);
else printf("%lld",dd(n + 2,k));
return 0;
}