Zhu Guosha
Problem solution
Why are there always * * questions? People like to name the questions with the names of some cancer questions.
It's easy to think of passing this kind of question
d
p
dp
dp to transfer it.
Let's first consider how to choose cards if we want to choose cards so that we can get as many cards as possible. Obviously, choosing from a small time will make the total number of our cards as large as possible.
In order to avoid the de duplication, inclusion and exclusion operation of lifting cards, we can consider determining the order of our card selection, that is, selecting smaller cards, and determining the sequence of our whole card according to each card selection scheme.
We can add cards in the order from small to large to construct the sequence of cards we choose.
We define
d
p
i
,
j
dp_{i,j}
dpi,j ， indicates selected
i
i
i cards, total
j
j
j number of schemes.
The transfer is obvious if we have chosen to add to the weight
x
x
x cards, enumerating the number of cards added
k
k
k，
d
p
i
+
k
,
j
+
k
x
+
=
(
i
+
k
i
)
d
p
i
,
j
dp_{i+k,j+kx}+=\binom{i+k}{i}dp_{i,j}
dpi+k,j+kx+=(ii+k)dpi,j
Of course, if we add the card we choose, its total is greater than
m
m
m, the sequence of its selection card has been fixed. We can add this situation to the answer.
However, it should be noted that there may be multiple cards added at last, but we will only select some of them, but we still have to enumerate how many cards are selected.
We remember
t
=
⌊
m
−
j
x
⌋
t=\left\lfloor\frac{m-j}{x}\right\rfloor
t = ⌊ xm − j ⌋, obviously, the last card we choose will only be
t
t
t add the answer, then calculate
d
p
i
,
j
dp_{i,j}
When dpi,j ， contribute, we can enumerate the number of cards selected,
A
n
s
+
=
∑
k
=
t
+
1
n
−
i
(
i
+
t
)
(
n
i
)
(
n
−
i
k
)
(
A
−
x
)
n
−
i
−
k
d
p
i
,
j
A
n
Ans+=\frac{\sum_{k=t+1}^{n-i}(i+t)\binom{n}{i}\binom{n-i}{k}(A-x)^{n-i-k}dp_{i,j}}{A^n}
Ans+=An∑k=t+1n−i(i+t)(in)(kn−i)(A−x)n−i−kdpi,j
Obviously, in addition to the selection weights we enumerated
x
x
The position of x and the weight of other positions are higher than
x
x
x is big, so there is
(
A
−
x
)
(A-x)
(A − x) options.
So we have
d
p
i
,
j
dp_{i,j}
The transfer of dpi,j +
k
⩽
t
k\leqslant t
Transfer to when k ⩽ t
d
p
i
+
k
,
j
+
k
x
dp_{i+k,j+kx}
dpi+k,j+kx, when
k
>
t
k>t
k> T contributes to the answer.
In this case, the time complexity is
O
(
n
2
m
A
)
O\left(n^2mA\right)
O(n2mA), considering optimization.
Obviously, it can be found that we contribute to the part of the answer
d
p
i
,
j
dp_{i,j}
Coefficient of dpi,j +
(
i
+
t
)
(
n
i
)
(
n
−
i
k
)
(
A
−
x
)
n
−
i
−
k
(i+t)\binom{n}{i}\binom{n-i}{k}(A-x)^{n-i-k}
(i+t)(in) (kn − i) (A − x)n − i − k can actually be divided into two sections,
(
i
+
t
)
(i+t)
(i+t), for each
j
j
j is independent and can be enumerated to
j
j
j hour
O
(
1
)
O\left(1\right)
O(1) is calculated.
(
n
i
)
(
n
−
i
k
)
(
A
−
x
)
n
−
i
−
k
\binom{n}{i}\binom{n-i}{k}(A-x)^{n-i-k}
(in) (kn − i) (A − x)n − i − k only with
i
i
i and
k
k
k relevant.
We can enumerate the second part
i
i
i will calculate its prefix and, enumeration
j
j
j is obtained
t
t
t can distinguish the sum of this paragraph.
So the part we contribute to the answer is actually OK
O
(
1
)
O\left(1\right)
O(1).
And contribute to
d
p
dp
Part of dp for each
d
p
i
,
j
dp_{i,j}
dpi,j # yes
O
(
t
)
O\left(t\right)
O(t).
because
t
t
t is from
1
1
1 enumerate to
m
m
m is obviously in the form of a harmonic series, so each
d
p
i
,
j
dp_{i,j}
dpi,j# will contribute
A
ln
m
−
j
A\ln m-j
Alnm − j times.
Total time complexity O ( n m A ln m ) O\left(nmA\ln m\right) O(nmAlnm), Kaka often passes.
Source code
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define debug(x) cerr<<#x<<"="<<x<<'\n'
typedef long long LL;
typedef unsigned long long uLL;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int mo=998244353;
const int inv2=499122177;
const int jzm=2333;
const int n1=50;
const int zero=10000;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
typedef pair<LL,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
_T f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
x*=f;
}
template<typename _T>
void print(_T x){putchar('\n');while(x>9){putchar((x%10)|'0');x/=10;}putchar(x|'0');}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1LL)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1LL;}return t;}
int n,m,A,dp[2][105][MAXN],ans,fac[MAXN],inv[MAXN],f[MAXN],pw[105][MAXN],C[105][105],sum[1005];
void init(){
fac[0]=fac[1]=inv[0]=inv[1]=f[1]=1;
for(int i=2;i<=n;i++)
fac[i]=1ll*i*fac[i-1]%mo,
f[i]=1ll*(mo-mo/i)*f[mo%i]%mo,
inv[i]=1ll*f[i]*inv[i-1]%mo;
for(int i=0;i<=n;i++){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++)
C[i][j]=add(C[i-1][j-1],C[i-1][j],mo);
}
for(int i=0;i<=A;i++)pw[0][i]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=A;j++)
pw[i][j]=1ll*j*pw[i-1][j]%mo;
}
signed main(){
freopen("legend.in","r",stdin);
freopen("legend.out","w",stdout);
read(n);read(m);read(A);init();dp[0][0][0]=1;
for(int x=1;x<=A;x++){
int now=x&1,las=now^1;
for(int i=0;i<=n;i++)
for(int j=i;j<=m;j++)dp[now][i][j]=0;
for(int i=0;i<=n;i++){
sum[0]=0;
for(int k=1;k<=n-i;k++)
sum[k]=add(sum[k-1],1ll*C[n-i][k]*pw[n-i-k][A-x]%mo,mo);
for(int j=max(i,m-x+1);j<=m;j++)
Add(ans,1ll*i*C[n][i]%mo*dp[las][i][j]%mo*pw[n-i][A-x+1]%mo,mo);
for(int j=i;j<=m-x;j++)if(dp[las][i][j]){
int t=(m-j)/x;
for(int k=1,tp=x;k<=min(t,n-i);k++,tp+=x)
Add(dp[now][i+k][j+tp],1ll*C[i+k][k]*dp[las][i][j]%mo,mo);
if(n-i>t)Add(ans,1ll*add(sum[n-i],mo-sum[t],mo)*C[n][i]%mo*(i+t)%mo*dp[las][i][j]%mo,mo);
Add(dp[now][i][j],dp[las][i][j],mo);
}
}
}
for(int i=0;i<=m;i++)Add(ans,1ll*n*dp[A&1][n][i]%mo,mo);
printf("%d\n",1ll*ans*qkpow(qkpow(A,n,mo),mo-2,mo)%mo);
return 0;
}