Opening T2, this tarjan shrinks a little funny? Same status in SCC? Then I thought for two hours and was hack ed as soon as I finished writing. It is found that the guarantee diagram is SCC, and the points in SCC will affect each other.
Or too naive, too arbitrary, write what you think. In the end, you often waste a lot of time on fake practices.
This is the last game before the winter vacation training. I feel that the whole person is in a weaker state now. Now let me test the league and maybe retire.
Although the League was in this state at the beginning of training, it was still very uncomfortable. I hope the winter vacation will be better.
T1 sequence
If it is difficult, it is difficult. The general scheme is easy to seek. If it is illegal, it shall be discussed in three cases.
\(1.\) \(a \) itself is a \ (colorful \) sequence. There is no illegality at this time.
\(2.\) \(a \) has no duplicate color, but the length is less than \ (k \):
At this time, the number of \ (a \) is actually the number of substrings in the parent sequence with a length of \ (m \) and arranged, and then divided by \ (k^{\underline m} \), so consider finding the number of substrings.
Let \ (f_{i,j} \) be the number of non \ (colorful \) sequences with a length of \ (i \) and an extremely long permutation substring with a length of \ (j \), and \ (g_{i,j} \) be the number of permutation substrings with a length of \ (m \) in these sequences\ (f {i, j} \) can be transferred from \ (f {i-1, j-1} \) to select a new color that does not appear, or from \ (f {i-1, q}, Q \ GEQ, j \) to select a new color that appears. It is not difficult to find that this transfer can be suffix and optimized to \ (O(1) \)\ The transfer of (g {i, j} \) is similar, but it can also be transferred from \ (f {i, j} \) when \ (j\geq m \), counting the arranged substrings ending in \ (i \). Finally \ (\ sum {i = 0} ^ {k-1}g {n, i} \) is the result.
\(3.\) \(a \) has duplicate colors and is not a \ (colorful \) sequence:
You can extract the extremely long array prefix and suffix of \ (a \), make the same DP as in \ (f \) in 2, and finally enumerate the positions of \ (a \) for statistics.
\(code:\)
T1#include<bits/stdc++.h>
using namespace std;
namespace IO{
#define int LL
typedef double DB;
typedef long long LL;
LL read(){
LL x=0,f=0; char ch=getchar();
while(ch>'9'||ch<'0'){ f|=(ch=='-'); ch=getchar(); }
while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return f?-x:x;
} char output[50];
void write(LL x,char sp){
int len=0;
if(x<0) putchar('-'), x=-x;
do{ output[len++]=x%10+'0'; x/=10; }while(x);
for(int i=len-1;~i;i--) putchar(output[i]); putchar(sp);
}
void ckmax(int& x,int y){ x=x>y?x:y; }
void ckmin(int& x,int y){ x=x<y?x:y; }
} using namespace IO;
const int NN=25010,KK=410,mod=1e9+7;
int n,m,k,l,r,ans,a[NN];
bool vis[KK];
void pls(int& x,int y){ (x+=y)>=mod?(x-=mod):(x<0?(x+=mod):0); }
int qpow(int a,int b=mod-2,int res=1){
for(;b;b>>=1,a=a*a%mod)
if(b&1) res=res*a%mod;
return res;
}
bool colorful(){
for(int i=1;i<=m-k+1;i++){
memset(vis,0,sizeof(vis));
for(int j=i;j<=i+k-1;vis[a[j]]=1,j++) if(vis[a[j]]) goto skip;
return 1; skip:;
}
return 0;
}
void getpos(){
l=m; r=1;
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;vis[a[i]]=1,i++) if(vis[a[i]]){ l=i-1; break; }
memset(vis,0,sizeof(vis));
for(int i=m;i>=1;vis[a[i]]=1,i--) if(vis[a[i]]){ r=i+1; break; }
r=m-r+1;
}
namespace DPrograming{
int f[NN][KK],g[NN][KK];
int diff(int res=0){
f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<k;j++){
pls(f[i][j]=f[i-1][j],(k-j+1)*(f[i-1][j-1]-f[i-1][j])%mod);
pls(g[i][j]=g[i-1][j],(k-j+1)*(g[i-1][j-1]-g[i-1][j])%mod);
if(j>=m) pls(g[i][j],f[i][j]);
}
for(int j=k-1;~j;j--) pls(f[i][j],f[i][j+1]), pls(g[i][j],g[i][j+1]);
}
res=g[n][0];
for(int i=0;i<m;i++) res=res*qpow(k-i)%mod;
return res;
}
int same(int res=0){
for(int i=0;i<=l;i++) f[0][i]=1;
for(int i=0;i<=r;i++) g[0][i]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<k;j++){
pls(f[i][j]=f[i-1][j],(k-j+1)*(f[i-1][j-1]-f[i-1][j])%mod);
pls(g[i][j]=g[i-1][j],(k-j+1)*(g[i-1][j-1]-g[i-1][j])%mod);
}
for(int j=k-1;~j;j--) pls(f[i][j],f[i][j+1]), pls(g[i][j],g[i][j+1]);
}
for(int i=0;i<=n-m;i++) pls(res,f[i][0]*g[n-i-m][0]%mod);
return res;
}
} using namespace DPrograming;
signed main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
n=read(); k=read(); m=read();
ans=(n-m+1)*qpow(k,n-m)%mod;
for(int i=1;i<=m;i++) a[i]=read();
if(colorful()){ return write(ans,'\n'),0; }
getpos();
pls(ans,l==m?(-diff()):(-same()));
write(ans,'\n');
return 0;
}
T2 directed graph
The topic deliberately mentioned "at least \ (20 \% \) interesting points", which can make people think of randomization.
When the problem on the general graph is not easy to solve, you can consider building a DFS tree transformation problem. This problem ensures that the graph is a SCC and also inspires the DFS tree to a certain extent.
A point is interesting if and only if there is no cross edge in the DFS tree with it as the root. So rand gives a root and considers the determination of non root points.
It is not difficult to find a non root point interesting if and only if there is at most one atavistic edge pointing to its ancestor in its subtree, and the ancestor pointed to by this edge is an interesting point. The sufficiency is very good.
So there was a difference in the tree.
\(code:\)
T2#include<bits/stdc++.h>
using namespace std;
namespace IO{
typedef double DB;
typedef long long LL;
LL read(){
LL x=0,f=0; char ch=getchar();
while(ch>'9'||ch<'0'){ f|=(ch=='-'); ch=getchar(); }
while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return f?-x:x;
} char output[50];
void write(LL x,char sp){
int len=0;
if(x<0) putchar('-'), x=-x;
do{ output[len++]=x%10+'0'; x/=10; }while(x);
for(int i=len-1;~i;i--) putchar(output[i]); putchar(sp);
}
void ckmax(int& x,int y){ x=x>y?x:y; }
void ckmin(int& x,int y){ x=x<y?x:y; }
} using namespace IO;
mt19937 zxsty((unsigned long long)(new int));
const int NN=100010,MM=NN<<1;
int t,n,m,cnt,root,c[NN],pos[NN],dep[NN],mnd[NN];
bool flag,vis[NN],tag[NN],instk[NN];
vector<int>e[NN];
void check(int u){
instk[u]=vis[u]=1;
for(int v:e[u])
if(!vis[v]) check(v);
else if(!instk[v]) flag=1;
instk[u]=0;
}
void clear(){
root=cnt=0;
for(int i=1;i<=n;i++){
tag[i]=c[i]=dep[i]=0;
e[i].clear();
}
}
void update(int x,int v,int p){ if(mnd[x]>v) mnd[x]=v, pos[x]=p; }
void dfs(int u,int d,int p){
mnd[u]=dep[u]=d; pos[u]=u;
for(int v:e[u])
if(!dep[v]) dfs(v,d+1,u), c[u]+=c[v], update(u,mnd[v],pos[v]);
else ++c[u], --c[v], update(u,dep[v],v);
}
void query(int u,int p){
vis[u]=1;
if(!c[u]||(tag[pos[u]]&&c[u]==1)) tag[u]=1,++cnt;
for(int v:e[u]) if(!vis[v]) query(v,u);
}
signed main(){
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
t=read();
while(t--){
n=read(); m=read(); clear();
for(int u,i=1;i<=m;i++)
u=read(), e[u].push_back(read());
for(int i=1;i<=50&&!root;i++){
memset(vis,0,sizeof(vis)); flag=0;
int pos=zxsty()%n+1; check(pos);
if(!flag) root=pos;
}
if(!root){ puts("-1"); continue; }
dfs(root,1,0); memset(vis,0,sizeof(vis)); query(root,0);
if(cnt<0.2*n){ puts("-1"); continue; }
for(int i=1;i<=n;i++) if(tag[i]) write(i,' ');
puts("");
}
return 0;
}
T3 graphics
A very important transformation is to transform the convex hull scheme into a selection scheme, which has the following limitations:
That's right
Because the convex hull has been formed after determining the vector set, this transformation is correct.
What we need to determine now is how many vectors to choose. When there are few types of re vectors and the limited range is large, it can be considered to disassemble the digital DP. Enumerate each binary bit of each vector selection number.
Similar to NOIP2021T2, the number of carry is recorded. More than NOIP2021T2, it is designed in seven-dimensional super large state.
Record which bit is currently considered, the carry digits of positive x, positive y, negative X and negative y, and whether the selected X and Y in the considered position are less than m, from low to high DP, enumerate this bit and select those vectors each time.
\(code:\)
T3#include<bits/stdc++.h>
using namespace std;
namespace IO{
typedef double DB;
typedef long long LL;
LL read(){
LL x=0,f=0; char ch=getchar();
while(ch>'9'||ch<'0'){ f|=(ch=='-'); ch=getchar(); }
while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return f?-x:x;
} char output[50];
void write(LL x,char sp){
int len=0;
if(x<0) putchar('-'), x=-x;
do{ output[len++]=x%10+'0'; x/=10; }while(x);
for(int i=len-1;~i;i--) putchar(output[i]); putchar(sp);
}
void ckmax(int& x,int y){ x=x>y?x:y; }
void ckmin(int& x,int y){ x=x<y?x:y; }
} using namespace IO;
const int mod=998244353;
int n,m,x[10],y[10],f[31][23][23][23][23][2][2];
void pls(int& x,int y){ (x+=y)>=mod?(x-=mod):(x<0?(x+=mod):0); }
int st(int x,int y,int t){ return (x^y)?(x>y):t; }
int dfs(int p,int px,int py,int nx,int ny,int lx,int ly){
if(p==30) return (!px)&(!py)&(!nx)&(!ny)&(!lx)&(!ly);
if(~f[p][px][py][nx][ny][lx][ly]) return f[p][px][py][nx][ny][lx][ly];
int b=(m>>p)&1,res=0;
for(int s=0;s<(1<<n);s++){
int tpx=px,tpy=py,tnx=nx,tny=ny;
for(int i=1;i<=n;i++) if(s&(1<<i-1)){
(x[i]>0)?(tpx+=x[i]):(tnx-=x[i]);
(y[i]>0)?(tpy+=y[i]):(tny-=y[i]);
}
int bpx=tpx&1,bpy=tpy&1,bnx=tnx&1,bny=tny&1;
if(bpx==bnx&&bpy==bny)
pls(res,dfs(p+1,tpx>>1,tpy>>1,tnx>>1,tny>>1,st(bpx,b,lx),st(bpy,b,ly)));
}
return f[p][px][py][nx][ny][lx][ly]=res;
}
signed main(){
freopen("shape.in","r",stdin);
freopen("shape.out","w",stdout);
n=read(); m=read();
for(int i=1;i<=n;i++) x[i]=read(),y[i]=read();
memset(f,-1,sizeof(f));
write((dfs(0,0,0,0,0,0,0)-1+mod)%mod,'\n');
return 0;
}