多校省选模拟 1
T1 序列
首先发现一个性质，就是一些元素是什么不重要，而是否相同才是重要的
然后可以在给定的a序列上左右添加元素，满足不是彩色序列同时计算方案数
f[i][j]表示生成了长度为 i ，互不相同的最长后缀长度为 j 的非彩色序列数
转移就考虑i+1从这 j 个中挑还是从k-j个中挑
计算答案时若a两两不同，枚举左边加了 i 个，右边加了n-m-i个，然后方案数乘起来
否则将问题转化，求所有长度为n的非彩序列中，连续m个互不相同元素的出现个数
转移与 f 类似，最后除掉\(A_{k}^{m}\)
T2 有向图
这个20%挺奇怪的，然后作用是能大概率找出有趣点，O(n)判断有趣点，满足dfs树只有树边和返祖边
这个东西我一直以为凡是dfs树就只有树边和返祖边，模了几个发现还有前向边，码完调了会儿发现还有横叉边，，，因为是有向图，就挺淦
回到题解，然后以找到的有趣点dfs，x是有趣点条件是x子树内只有一条边伸到x的祖先v，且v是有趣点
然后拿个multiset维护子树内的返祖边就行了
T3 图形
条件是\(\sum x_ic_i=0,\sum y_ic_i=0\)
还有\(\sum_{x_i>0} x_ic_i<=m,\sum_{y_i>0}y_ic_i<=m\)
然后不好维护，但是n和给的坐标都很小，所以可以二进制拆分\(\sum x_ic_i\)，然后维护进位
\(dp_{d,px,py,nx,ny,p,q}\)表示第 d 位,x>0进到这一位大小为px，y>0进到这一维是py，对应的负数是nx，ny，然后\(\sum_{x_i>0} x_ic_i\)前i位是否不大于m，q同理是y
然后转移的时候状压枚举选的向量，满足选的正数和负数与各自的进位之和在第i位相等
然后凸包不能S=0，所以最后-1
代码
T1
#include
using namespace std;
#define il inline
#define ll long long
const int N=1e3+5;
const int mod=1e9+7;
il int read()
{
int s=0;
char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
struct cz1{
int n,m,k;
int a[N],nxt[N];
int tran[N][5];
int f[N][N][5][5][5],g[N][N][5][5][5];
il int min_(int x,int y){return x>y?y:x;}
il void md(int &x){if(x>=mod)x-=mod;return;}
void kmp()
{
int i=0,j=-1;
nxt[0]=-1;
while(i<=m&&j<=m)
{
if(j==-1||a[j+1]==a[i+1]) nxt[++i]=++j;
else j=nxt[j];
}
return;
}
void solve()
{
if(k==1){cout<1);x<=k;++x)
for(int y=(i>0);y<=k;++y)
{
if(!g[i][j][x][y][0]) continue;
for(int h=1;h<=k;++h)
{
if(x&&y&&h&&x!=y&&y!=h&&x!=h) continue;
if(tran[j][h]==m) md(f[i+1][m][y][h][0]+=g[i][j][x][y][0]+f[i][j][x][y][0]);
else md(f[i+1][tran[j][h]][y][h][0]+=f[i][j][x][y][0]);
md(g[i+1][tran[j][h]][y][h][0]+=g[i][j][x][y][0]);
}
}
int ans=0;
for(int i=0;i<=m;++i)
for(int x=1;x<=k;++x) for(int y=1;y<=k;++y)
md(ans+=f[n][i][x][y][0]);
cout<<(mi-ans+mod)%mod<2);x<=k;++x)
for(int y=(i>1);y<=k;++y)
for(int z=(i>0);z<=k;++z)
{
if(!g[i][j][x][y][z]) continue;
for(int h=1;h<=k;++h)
{
if(x&&y&&z&&h)if(x!=y&&x!=z&&x!=h&&y!=z&&y!=h&&z!=h)continue;
if(tran[j][h]==m) md(f[i+1][m][y][z][h]+=(g[i][j][x][y][z]+f[i][j][x][y][z])%mod);
else md(f[i+1][tran[j][h]][y][z][h]+=f[i][j][x][y][z]);
md(g[i+1][tran[j][h]][y][z][h]+=g[i][j][x][y][z]);
}
}
int ans=0;
for(int i=0;i<=m;++i)
for(int x=1;x<=k;++x) for(int y=1;y<=k;++y) for(int z=1;z<=k;++z)
md(ans+=f[n][i][x][y][z]);
cout<<(mi-ans+mod)%mod<y?y:x;}
il void md(int &x){x=(x>=mod)?x-mod:x;return;}
bool jud[402];
int n,k,m,num;
int a[25011],g[25011],h[25011];
int f[25011][402],sum[25011][402],gg[25011][402];
int fm(int x,int y){int ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
void solve2(int ans)
{
f[1][1]=k;
for(int i=1;i=m) md(gg[i][j]+=f[i][j]);
md(sum[i][j]=sum[i][j-1]+gg[i][j]);
}
int s=0;
for(int i=1;i T2
#include
using namespace std;
#define il inline
const int N=2e5+11;
bool jd;
bool vis[N];
int n,m;
int f[N],dep[N];
struct st_{int u,v;friend bool operator<(st_ a,st_ b){return dep[a.v] vct[N];
multiset st[N];
multiset::iterator it;
il int read()
{
int s=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
void dfs(int x)
{
vis[x]=1;
for(int v : vct[x])
{
if(!dep[v]) dep[v]=dep[x]+1,dfs(v);
else if(!vis[v]) jd=1;
if(jd) return;
}
vis[x]=0;
return;
}
bool jud(int x)
{
for(int i=1;i<=n;++i) dep[i]=0;
dep[x]=1,jd=0,dfs(x);
return !jd;
}
void get_f(int x)
{
int sn=x;
for(int v : vct[x])
if(dep[v]>dep[x])
{get_f(v);if(st[v].size()>st[sn].size()) sn=v;}
st[x].swap(st[sn]);
for(int v : vct[x])
if(dep[v]>dep[x]&&v!=sn)
while(st[v].size()) st[x].insert(*st[v].begin()),st[v].erase(st[v].begin());
for(int v : vct[x]) if(dep[v]v]v;
++it;if(it!=st[x].end())if(dep[it->v]dep[x])
{
if(!vis[v]) vis[v]=vis[f[v]];
get_ans(v);
}
return;
}
int main()
{
FILE *p=freopen("graph.in","r",stdin);
p=freopen("graph.out","w",stdout);
// srand(time(0));
int t=read();
while(t--)
{
for(int i=1;i<=n;++i) f[i]=0,vct[i].clear(),vis[i]=0,st[i].clear();
n=read(),m=read();
for(int x,i=1;i<=m;++i)x=read(),vct[x].push_back(read());
// for(int i=1;i<=n;++i)if(jud(i)) printf("%d ",i);
for(int x,i=1;i<=100;++i){x=rand()%n+1;if(jud(x)){solve(x);get_ans(x);break;}}
for(int i=1;i<=n;++i) if(vis[i]) printf("%d ",i);
printf("\n");
}
return 0;
}
T3
#include
using namespace std;
#define il inline
#define int long long
const int N=10;
const int mod=998244353;
int n,m;
int x[N],y[N];
int f[32][21][21][21][21][2][2];
il void md(int &x){if(x>=mod)x-=mod;return;}
bool check(bool jd,int x){return ((x&1)==(m&1))?jd:((x&1)<(m&1));}
signed main()
{
FILE* p=freopen("shape.in","r",stdin);
p=freopen("shape.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>x[i]>>y[i];
f[0][0][0][0][0][1][1]=1;
for(int vx1,vx2,vy1,vy2,i=0;i<31;++i,m>>=1)for(int px=0;px<=20;++px)for(int py=0;py<=20;++py)
for(int nx=0;nx<=20;++nx)for(int ny=0;ny<=20;++ny)
for(int p=0;p<=1;++p)for(int q=0;q<=1;++q)
{
if(!f[i][px][py][nx][ny][p][q]) continue;
for(int sta=0;sta<(1<0)vx1+=x[j];else vx2-=x[j];}
if(((vx1+px)&1)!=((vx2+nx)&1))continue;
vy1=vy2=0;
for(int j=1;j<=n;++j) if((1<0)vy1+=y[j];else vy2-=y[j];}
if(((vy1+py)&1)!=((vy2+ny)&1))continue;
md(f[i+1][(px+vx1)>>1][(py+vy1)>>1][(nx+vx2)>>1][(ny+vy2)>>1][check(p,vx1+px)][check(q,vy1+py)]+=f[i][px][py][nx][ny][p][q]);
}
}
cout<<(f[31][0][0][0][0][1][1]-1+mod)%mod<