Preface
Why am I so disheartened now...
A B has been hanging for a long time, CWA has not passed a whole page (brain convulsion), the brain convulsion belongs to yes
A - Continuous 1
Damn, I read the title wrong at the beginning. It's too stupid to directly enumerate each interval with a length of \(k \). It needs to satisfy that there is no \(1\) outside the interval and no \(0\) in the interval. Such an interval there can only be one
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=300005;
int t,n,k,pfx1[N],pfx0[N],c; char s[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d%d%s",&n,&k,s+1),i=1;i<=n;++i)
pfx0[i]=pfx0[i-1]+(s[i]=='0'),pfx1[i]=pfx1[i-1]+(s[i]=='1');
for (c=0,i=1;i<=n-k+1;++i)
if (pfx1[i-1]==0&&pfx1[n]-pfx1[i+k-1]==0&&pfx0[i+k-1]-pfx0[i-1]==0) ++c;
puts(c==1?"Yes":"No");
}
return 0;
}
B - Make Divisible
I didn't know why at first, I thought that the range of \(x\) must be very small, so I enumerated a \(10^6\), and I made two white WA shots.
First, we can convert \(A+x|B+y\) into \(B+n=(A+m)\times k\), where \(n<A+m\), the final contribution is\(n+m\)
Now we consider changing the value of \(n\) by adjusting the value of \(m\). It is not difficult to find that when \(m\) becomes larger, if the value of \(k\) does not change, then \( n\) is obviously increasing, and these cases must not be optimal
Therefore, every time we change \(m\), we require \(k\) to change until \(n=0\), the complexity of a single set of data is about \(O(\log n)\) level
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,a,b,ans;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
scanf("%d%d",&a,&b); int m=(b-1)/a+1,n=m*a-b,pa=a; ans=n;
while (n>0&&a<=b)
{
int d=(a-n-1)/m; a+=d; m=(b-1)/a+1; n=m*a-b; ans=min(ans,n+a-pa);
++a; m=(b-1)/a+1; n=m*a-b; ans=min(ans,n+a-pa);
}
printf("%d\n",ans);
}
return 0;
}
C - Path and Subsequence
At first, I thought that DFS could pass, but I found out that I wrote a layered diagram to find the shortest path, but I didn't expect 01-BFS.
It is not difficult to find that we can set \(f_i\) to indicate that the point \(i\) matches the first item of the \(B\) sequence, consider walking from \(i\) to its neighbor \(j\ ), then\(f_j=\min_\limits{i\to j}(f_i+[a_j=b_{f_i+1}])\)
At this time, the problem becomes a shortest path problem. It is not difficult to find that since the edge weight can only be \(0/1\), it can be solved by 01-BFS
#include<cstdio>
#include<iostream>
#include<vector>
#include<deque>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,m,k,x,y,a[N],b[N],f[N]; vector <int> v[N]; deque <int> q; bool vis[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d%d",&n,&m,&k),i=1;i<=m;++i)
scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
for (i=1;i<=n;++i) scanf("%d",&a[i]),f[i]=k+1;
for (i=1;i<=k;++i) scanf("%d",&b[i]);
f[1]=a[1]==b[1]; vis[1]=1; q.push_back(1);
while (!q.empty())
{
int now=q.front(); q.pop_front(); vis[now]=0;
for (int to:v[now])
{
int d=a[to]==b[f[now]+1];
if (f[now]+d<f[to])
{
vis[to]=1; f[to]=f[now]+d;
if (d) q.push_back(to); else q.push_front(to);
}
}
}
return puts(f[n]<k?"No":"Yes"),0;
}
D - Removing Gacha (NTT practice)
First set \(X_k\) to represent the expected number of steps from the first occurrence of \(k\) black dots to the first occurrence of \(k+1\) black dots, the final answer is \(\sum_{ k=0}^{N-1} X_k\)
Consider that when there are \(k\) black points, the number of good points is \(m\). Obviously, the probability of selecting a white point to transfer the state to \(k+1\) is \(\ frac{N-k}{N-m}\), the expected number of steps is \(\frac{N-m}{N-k}\)
Let \(p_{k,m}\) indicate that when there are \(k\) black points, the number of good points is the probability of \(m\), then there is \(E_k=\sum_ {m=0}^N \frac{p_{k,m}\times(N-m)}{N-k}=\frac{N}{N-k}-\frac{1}{N-k}\times \sum_{m= 0}^N (p_{k,m}\times m)\)
It is not difficult to find that \(\sum_{m=0}^N (p_{k,m}\times m)\) is the expectation of good points when \(k\) black points appear for the first time
Consider setting \(q_{k,i}\) to represent the probability that the point \(i\) is good when \(k\) black points appear for the first time, so \(\sum_{m=0} ^N (p_{k,m}\times m)=\sum_{i=1}^N q_{k,i}\)
Let \(dep_i\) represent the number of nodes from the root node to the \(i\) point. Obviously, the problem at this time becomes, select \(k\) points from the \(N\) points to become black, And these \(k\) points contain exactly \(dep_i\) given points, it is not difficult to find that the probability of this part is \(\frac{C_{N-dep_i}^{k-dep_i}} {C_N^k}=\frac{k!(N-dep_i)!}{N!(k-dep_i)!}\)
So now the problem turns into finding \(\frac{k!}{N!}\times \sum_\limits{1\le i\le N,dep_i\le k} \frac{(N-dep_i)!}{( k-dep_i)!}\), considering that \(c_i\) is the number of \(v\) of \(dep_v=i\), then \(\sum_\limits{1\le i\le N, dep_i\le k} \frac{(N-dep_i)!}{(k-dep_i)!}=\sum_{i=1}^k c_i\times \frac{(N-i)!}{(k-i)!} \)
Consider setting \(A_i=c_i\times (N-i)!,B_i=\frac{1}{i!}\), obviously what we require is \(A\star B\), and it can be solved directly by NTT
Complexity\(O(N\log N)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,mod=998244353;
int n,dep[N],c[N],fa,lim,fac[N],ifac[N],A[N<<2],B[N<<2],ans;
inline int sum(CI x,CI y)
{
return x+y>=mod?x+y-mod:x+y;
}
inline int sub(CI x,CI y)
{
return x-y<0?x-y+mod:x-y;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
RI i; for (fac[0]=i=1;i<=n;++i) fac[i]=1LL*fac[i-1]*i%mod;
for (ifac[n]=quick_pow(fac[n]),i=n-1;~i;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
namespace Poly
{
int p,rev[N<<2];
inline void init(CI n)
{
for (lim=1,p=0;lim<=n;lim<<=1,++p);
for (RI i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<p-1);
}
inline void NTT(int *f,CI opt)
{
RI i,j,k; for (i=0;i<lim;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);
for (i=1;i<lim;i<<=1)
{
int D=quick_pow(3,~opt?(mod-1)/(i<<1):mod-1-(mod-1)/(i<<1));
for (j=0;j<lim;j+=(i<<1))
{
int W=1; for (k=0;k<i;++k,W=1LL*W*D%mod)
{
int x=f[j+k],y=1LL*f[i+j+k]*W%mod; f[j+k]=sum(x,y); f[i+j+k]=sub(x,y);
}
}
}
if (!~opt)
{
int Div=quick_pow(lim); for (i=0;i<lim;++i) f[i]=1LL*f[i]*Div%mod;
}
}
};
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n),dep[1]=1,i=2;i<=n;++i) scanf("%d",&fa),dep[i]=dep[fa]+1;
for (init(n),i=1;i<=n;++i) ++c[dep[i]];
for (i=0;i<=n;++i) A[i]=1LL*c[i]*fac[n-i]%mod,B[i]=ifac[i];
for (Poly::init(n<<1),Poly::NTT(A,1),Poly::NTT(B,1),i=0;i<lim;++i) A[i]=1LL*A[i]*B[i]%mod;
for (Poly::NTT(A,-1),i=0;i<n;++i) ans=sum(ans,1LL*sub(n,1LL*A[i]*fac[i]%mod*ifac[n]%mod)*quick_pow(n-i)%mod);
return printf("%d",ans),0;
}
D - Removing Gacha (easy way)
We consider directly finding the number of times the point\(i\) is expected to be dyed\(x_i\), the answer is\(\sum_{i=1}^N x_i\)
Consider looking at a point \(i\) alone, obviously just consider the operation of this chain from the root node to the point \(i\), and continue to operate until all points on this chain turn black
The difficulty of finding the problem is that only one non-good point can be selected for operation at a time, and according to the previous practice, we know that it is very troublesome to consider this situation
Then we can now assume that operations can also be performed on all points on this chain (including good points), but we ignore these operations
Specifically, because we only care how many times it is expected to be selected when the last \(i\) becomes good, and only count \(x_i\), we can completely assume that the operation is also performed on the good points on the chain. , no matter how other points operate, it will not affect the state of this chain and the answer of \(i\)
So now the problem is very simple, there are \(k\) points on a chain, all of them are white at first, and each time any point is selected to be dyed black, when all the points are turned black, one of the points is dyed the expected number of times
Considering the expectation of directly finding the total number of operations, when there are \(i\) white points at this time, the probability of selecting a white point next time is \(\frac{i}{k}\), and the expected number of steps is \(\frac{k}{i}\), then there will be \(i-1\) white dots next time, and so on, the expectation of this part is \(\sum_{i=1}^k \frac{k}{i}\)
So the expectation of each point is\(\sum_{i=1}^k\frac{1}{i}\), the code is very concise, the complexity\(O(n)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,mod=998244353;
int n,dep[N],fa,lim,fac[N],ifac[N],g[N],ans;
inline int sum(CI x,CI y)
{
return x+y>=mod?x+y-mod:x+y;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
RI i; for (fac[0]=i=1;i<=n;++i) fac[i]=1LL*fac[i-1]*i%mod;
for (ifac[n]=quick_pow(fac[n]),i=n-1;~i;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n),dep[1]=1,i=2;i<=n;++i)
scanf("%d",&fa),dep[i]=dep[fa]+1;
for (init(n),i=1;i<=n;++i) g[i]=sum(g[i-1],1LL*ifac[i]*fac[i-1]%mod);
for (i=1;i<=n;++i) ans=sum(ans,g[dep[i]]);
return printf("%d",ans),0;
}