想了一下(LCT)维护虚实子树最大深度发现不太可写（可能是我马力弱吧/kk）
可以根据树的直径的性质得出两颗树链接之后直径的端点是原来的四个端点之二
用并查集维护联通块所代表的的集合，维护每个联通块的直径端点
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l+r)>>1)
#define y1 qwq
#define id(x,y) (((x)-1)*m+(y))
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=3e5+10,inf=0x3f3f3f3f;
int opt,ret,n,m;
int fa[N],t1[N],t2[N];
int son[N][2],f[N],st[N],str[N],tag[N];
inline int find(int k)
{
return fa[k]==k?k:fa[k]=find(fa[k]);
}
inline void pushup(int x)
{
str[x]=str[son[x][0]]+str[son[x][1]]+1;
}
inline void pushr(int x)
{
swap(son[x][0],son[x][1]);
tag[x]^=1;
}
inline void pushdown(int x)
{
if(!tag[x]) return;
if(son[x][0]) pushr(son[x][0]);
if(son[x][1]) pushr(son[x][1]);
tag[x]=0;
}
inline bool nroot(int x)
{
return son[f[x]][0]==x||son[f[x]][1]==x;
}
inline int ident(int x)
{
return son[f[x]][1]==x;
}
inline void rotate(int x)
{
int y=f[x],z=f[y],k=son[y][1]==x,w=son[x][!k];
if(nroot(y)) son[z][son[z][1]==y]=x;son[x][!k]=y,son[y][k]=w;
if(w) f[w]=y;f[y]=x,f[x]=z;
pushup(y);
}
inline void splay(int x)
{
int y=x,z=0;
st[++z]=y;
while(nroot(y)) st[++z]=y=f[y];
while(z) pushdown(st[z--]);
while(nroot(x))
{
y=f[x];
if(nroot(y)) rotate(ident(x)==ident(y)?y:x);
rotate(x);
}
pushup(x);
}
inline void access(int x)
{
for(int y=0;x;x=f[y=x])
splay(x),son[x][1]=y;
}
inline void makeroot(int x)
{
access(x);splay(x);
pushr(x);
}
inline int dis(int x,int y)
{
if(!x&&!y) return 0;
if(!x||!y) return 1;
makeroot(x);access(y);splay(y);
return str[y];
}
inline void link(int x,int y)
{
makeroot(x);
f[x]=y;
x=find(x),y=find(y);
int ans=-1,t,px,py;
if(ans<(t=dis(t1[x],t2[x]))) ans=t,px=t1[x],py=t2[x];
if(ans<(t=dis(t1[y],t2[y]))) ans=t,px=t1[y],py=t2[y];
if(ans<(t=dis(t1[x],t1[y]))) ans=t,px=t1[x],py=t1[y];
if(ans<(t=dis(t2[x],t2[y]))) ans=t,px=t2[x],py=t2[y];
if(ans<(t=dis(t1[x],t2[y]))) ans=t,px=t1[x],py=t2[y];
if(ans<(t=dis(t1[y],t2[x]))) ans=t,px=t1[y],py=t2[x];
fa[x]=y;
t1[y]=px,t2[y]=py;
}
inline void main()
{
opt=read();
n=read(),m=read();
for(int i=1;i<=n;++i) str[i]=1,fa[i]=t1[i]=i;
for(int op,x,y,i=1;i<=m;++i)
{
op=read(),x=read();
if(op==1)
{
y=read();
x=x^(ret*opt);y=y^(ret*opt);
link(x,y);
}
else
{
x=x^(ret*opt);
int tx=find(x);
printf("%d
",ret=(max(dis(x,t1[tx]),dis(x,t2[tx]))-1));
}
}
}
}
signed main()
{
red::main();
return 0;
}
一个背包问题，我们知道背包是(NP)问题，所以肯定要从那个(300)和(50000)下手
对于相同价钱的物品，先选价值最大的最优，每种物品按价值从大到小排序，然后做前缀和
(f[i][j])表示物品为(1-i)的物品中总花费为(j)时的最大价值
我们可以得到一个(O(ck^2))的(dp)
for(int i=1;i<=300;++i)
{
int sum=val[i].size();
for(int j=m;j>=i;--j)
{
for(int k=1;j-k*i>=0&&k<=sum;++k)
{
f[j]=max(f[j],f[j-k*i]+val[i][k-1]);
}
}
}
}
然后再考虑优化，想象一下每种价值的函数，应该是一个斜率单调递减的类似根号的函数
这种函数可以决策单调性优化
如果二分栈的话可能不好处理物品上限的问题，还是写分治吧
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l+r)>>1)
#define y1 qwq
#define id(x,y) (((x)-1)*m+(y))
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=3e5+10,inf=0x3f3f3f3f;
int n,m,tot;
int a[50010];
vector<int> val[310];
int f[310][50010];
inline bool cmp(int x,int y)
{
return x>y;
}
inline void solve(int l,int r,int tl,int tr,int id)
{
if(l>r) return;
int sum=val[id].size(),pos=tl;
for(int i=max(tl,mid-sum);i<=min(mid,tr);++i)
{
if(f[id-1][a[i]]+(i==mid?0:val[id][mid-i-1])>f[id][a[mid]])
{
f[id][a[mid]]=f[id-1][a[i]]+(i==mid?0:val[id][mid-i-1]);
pos=i;
}
}
solve(l,mid-1,tl,pos,id);solve(mid+1,r,pos,tr,id);
}
inline void main()
{
n=read(),m=read();
for(int x,y,i=1;i<=n;++i)
{
x=read(),y=read();
val[x].push_back(y);
}
for(int i=1;i<=300;++i) sort(val[i].begin(),val[i].end(),cmp);
for(int i=1;i<=300;++i)
{
int sum=val[i].size();
for(int j=1;j<sum;++j) val[i][j]+=val[i][j-1];
}
for(int i=1;i<=300;++i)
{
for(int j=0;j<i;++j)
{
tot=0;
for(int k=j;k<=m;k+=i) a[++tot]=k;
solve(1,tot,1,tot,i);
}
}
for(int i=1;i<=m;++i) printf("%lld ",f[300][i]);
}
}
signed main()
{
red::main();
return 0;
}
完全不会线性代数啊哭唧唧
假设我们枚举(A)
首先知道(C)一定在(A)的线性空间内
我们设(A)的秩为(x)，那么(B)的合法数量为((2^{n-x})^n) （因为(A)线性空间外(B)可以随意安排）
我们并不知道为什么(C)秩相同的答案都是一样的也许我以后会回来填坑的
直接引用了上面的结论，我们可以算出秩相同的(C)的答案然后除以相同的个数
假设(C)的秩为(r)，可以高斯消元得到
(f[i][j])表示(i×n)的矩阵中秩为(j)的方案数，转移如下：
(f[i][j]=f[i][j]+f[i-1][j-1]*(2^n-2^{j-1}))
因为行秩等于列秩，所以我们不能只选那些已经有秩的列，要减去(2^{j-1})
(f[i][j]=f[i][j]+f[i-1][j]*2^j)
这里就可以在已经有秩的列中选择了
然后枚举(A)的秩(x),秩为(x)的矩阵有(f[n][x])个，而满足条件的(C)有(f[x][r])个
那么答案是
[sumlimits_{x=r}^{n}f[n][x]*f[x][r]*(2^{n-x})^n
]
然后再除以秩为(r)的矩阵个数(f[n][r])
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l+r)>>1)
#define lowbit(i) ((i)&(-i))
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=2010,p=1e9+7;
int n,m;
int f[N][N],pw[N];
bitset<N> a[N];
inline int fast(int x,int k)
{
int ret=1;
while(k)
{
if(k&1) ret=ret*x%p;
x=x*x%p;
k>>=1;
}
return ret;
}
inline void main()
{
n=read();
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
a[i][j]=read();
int r=0;
for(int i=1;i<=n;++i)
{
int p=r+1,l=p;
for(;l<=n&&!a[l][i];++l);
if(l>n) continue;
if(l!=p) swap(a[l],a[p]);
for(int j=p+1;j<=n;++j) if(a[j][i]) a[j]^=a[p];
++r;
}
for(int i=pw[0]=1;i<=n;++i) pw[i]=pw[i-1]*2%p;
f[0][0]=1;
for(int i=1;i<=n;++i)
{
for(int j=0;j<=i;++j)
{
if(j) (f[i][j]+=f[i-1][j-1]*(pw[n]-pw[j-1]+p)%p)%=p;
(f[i][j]+=f[i-1][j]*pw[j]%p)%=p;
}
}
int ans=0;
for(int x=r;x<=n;++x)
{
(ans+=f[n][x]*f[x][r]%p*fast(pw[n-x],n)%p)%=p;
}
printf("%lld
",ans*fast(f[n][r],p-2)%p);
}
}
signed main()
{
red::main();
return 0;
}