There are $N$ Takahashi. The $i$-th Takahashi has an integer $A_i$ and $B_i$ balls. An integer $x$ between $1$ and $K$, inclusive, will be chosen uniformly at random, and they will repeat the following operation $x$ times. Beware that all $N$ Takahashi simultaneously perform this operation. For each $i=1,2,\ldots,N$, find the expected value, modulo $998244353$, of the number of balls the $i$-th Takahashi has at the end of the operations. It can be proved that the sought probability is always a rational number. Additionally, the constraints of this problem guarantee that if the sought probability is represented as an irreducible fraction \(\frac{y}{x}\), then \(x\) is not divisible by \(998244353\). Here, there is a unique \(0\leq z\lt998244353\) such that \(y\equiv xz\pmod{998244353}\), so report this \(z\).Problem Statement
How to find a expected value modulo $998244353$
Constraints
Input
The input is given from Standard Input in the following format:
$N$ $K$ $A _ 1$ $A _ 2$ $\cdots$ $A _ N$ $B _ 1$ $B _ 2$ $\cdots$ $B _ N$
Output
Print the expected value of the number of balls the $i$-th Takahashi has at the end of the operations for $i=1,2,\ldots,N$, separated by spaces, in a single line.
Sample Input 1
5 2 3 1 4 1 5 1 1 2 3 5
Sample Output 1
3 0 499122179 499122178 5
During two operations, the five Takahashi have the following number of balls.
If $x=1$ is chosen, the five Takahashi have $4,0,1,2,5$ balls.
If $x=2$ is chosen, the five Takahashi have $2,0,4,1,5$ balls.
Thus, the sought expected values are $3,0,\dfrac52,\dfrac32,5$. Print these values modulo $998244353$, that is, $3,0,499122179,499122178,5$, separated by spaces.
Sample Input 2
3 1000 1 1 1 1 10 100
Sample Output 2
111 0 0
After one or more operations, the first Takahashi gets all balls.
Sample Input 3
16 1000007 16 12 6 12 1 8 14 14 5 7 6 5 9 6 10 9 719092922 77021920 539975779 254719514 967592487 476893866 368936979 465399362 342544824 540338192 42663741 165480608 616996494 16552706 590788849 221462860
Sample Output 3
817852305 0 0 0 711863206 253280203 896552049 935714838 409506220 592088114 0 413190742 0 363914270 0 14254803
Sample Input 4
24 100000000007 19 10 19 15 1 20 13 15 8 23 22 16 19 22 2 20 12 19 17 20 16 8 23 6 944071276 364842194 5376942 671161415 477159272 339665353 176192797 2729865 676292280 249875565 259803120 103398285 466932147 775082441 720192643 535473742 263795756 898670859 476980306 12045411 620291602 593937486 761132791 746546443
Sample Output 4
918566373 436241503 0 0 0 455245534 0 356196743 0 906000633 0 268983266 21918337 0 733763572 173816039 754920403 0 273067118 205350062 0 566217111 80141532 0
期望是假的，其实题目是让 \(x\) 走 \(i(i\le k)\) 步后的点加上 \(a_i\)
容易发现是一棵基环树，环上树上分开考虑。
树上的点长剖计算就好，复杂度 \(O(n)\)，关键是环上的点。
对每个树上的点，考虑他给环上的点带来的贡献，破环成链，差分计算即可。注意按照距离的不同，走的时候他有可能没走到。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,P=998244353;
typedef long long LL;
int n,q[N],l=1,r,a[N],b[N],e_num,hd[N],ans[N],inv,c[N<<1],in[N],s[N],dp[N],dfn[N],tme,son[N];
struct edge{
int v,nxt;
}e[N];
LL k;
int read()
{
char ch=getchar();
int s=0;
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s;
}
int pown(int x,int y)
{
if(!y)
return 1;
int t=pown(x,y>>1);
if(y&1)
return 1LL*t*t%P*x%P;
return 1LL*t*t%P;
}
void add_edge(int u,int v)
{
e[++e_num]=(edge){v,hd[u]};
hd[u]=e_num;
}
void doit(int x,int op)
{
if(son[x])
doit(son[x],1),ans[x]=(ans[son[x]]+b[son[x]])%P;
for(int i=hd[x];i;i=e[i].nxt)
{
if(e[i].v==son[x])
continue;
doit(e[i].v,1);
(ans[x]+=(ans[e[i].v]+b[e[i].v])%P)%=P;
for(int j=0;j<dp[e[i].v];j++)
(s[dfn[x]+j+1]+=s[dfn[e[i].v]+j])%=P;
}
if(k+1<dp[x])
(ans[x]+=P-s[dfn[x]+k+1])%=P;
if(!op)
ans[x]=0;
}
void init(int x,int fa)
{
s[dfn[x]=++tme]=b[x];
if(son[x])
init(son[x],x);
for(int i=hd[x];i;i=e[i].nxt)
if(e[i].v^son[x])
init(e[i].v,x);
}
void dfs(int x,int dep,int fr)
{
for(int i=hd[x];i;i=e[i].nxt)
dfs(e[i].v,dep+1,fr);
for(int i=hd[x];i;i=e[i].nxt)
if(dp[e[i].v]>dp[son[x]])
son[x]=e[i].v;
dp[x]=dp[son[x]]+1;
if(dep<=k)
{
LL p=(k-dep)%r,q=(k-dep)/r%P;
(c[fr]+=1LL*(q+1)*b[x]%P)%=P;
(c[fr+p+1]+=(P-b[x])%P)%=P;
(c[fr+r]+=(P-1LL*q*b[x]%P)%P)%=P;
}
}
void solve(int x)
{
q[r=1]=x;
int p=a[x];
while(p^x)
{
q[++r]=p;
p=a[p];
}
for(int i=1;i<=r;i++)
{
dfs(q[i],in[q[i]]=0,i);
init(q[i],0);
doit(q[i],0);
}
for(int i=1;i<=2*r;i++)
(c[i]+=c[i-1])%=P,(ans[q[(i-1)%r+1]]+=c[i])%=P;
for(int i=1;i<=r;i++)
(ans[q[i]]+=(P-b[q[i]])%P)%=P;
for(int i=1;i<=2*r;i++)
c[i]=0;
}
int main()
{
scanf("%d%lld",&n,&k),inv=pown(k%P,P-2);
for(int i=1;i<=n;i++)
a[i]=read(),in[a[i]]++;
for(int i=1;i<=n;i++)
b[i]=read();
for(int i=1;i<=n;i++)
if(!in[i])
q[++r]=i;
while(l<=r)
{
in[a[q[l]]]--;
add_edge(a[q[l]],q[l]);
if(!in[a[q[l]]])
q[++r]=a[q[l]];
l++;
}
for(int i=1;i<=n;i++)
if(in[i])
solve(i);
for(int i=1;i<=n;i++)
printf("%lld ",1LL*ans[i]*inv%P);
}