洛谷的评测地
循环位移
- 哈希，已知开头和长度，利用哈希相减得出该段是否为一个A串的循环
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
using i64 = long long;
using pii = pair<int,int>;
const int m1 = 1e9 + 7, m2 = 1e9 + 9;
struct Hash{
i64 x, y;
Hash(): x(0), y(0) {}
Hash(i64 x, i64 y): x(x), y(y) {}
Hash(char x, char y): x(x), y(y) {}
bool operator < (const Hash &t) const{
return x < t.x || (x == t.x && y < t.y);
}
bool operator == (const Hash &t) const{
return x == t.x && y == t.y;
}
bool operator != (const Hash &t) const{
return x != t.x || y != t.y;
}
};
Hash operator + (const Hash & a, const Hash &b){
return Hash((a.x + b.x) % m1, (a.y + b.y) % m2);
}
Hash operator - (const Hash &a, const Hash &b){
return Hash((a.x - b.x + m1) % m1, (a.y - b.y + m2) % m2);
}
Hash operator * (const Hash &a, const Hash &b){
return Hash(a.x * b.x % m1, a.y * b.y % m2);
}
Hash base;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;
//T=1;
std::cin>>T;
for(;T>0;--T){
std::srand(time(0));
base = Hash(1LL * rand() % m1, 1LL * rand() % m2 );
string a;std::cin>>a;
string b;std::cin>>b;
std::vector<Hash> bs(b.length()+5),pw(b.length()+5);
pw[0] = Hash(1LL, 1LL);
for(int i=1;i<=b.length();++i){
pw[i]=pw[i-1]*base;
bs[i]=bs[i-1]*base+Hash(1LL*b[i-1],1LL*b[i-1]);
}
Hash as;
std::set<Hash> hs;
for(int i=0,l=0;i<2*a.length()-1;++i){
if(i>=a.length()){
as=as-Hash(1LL*a[l],1LL*a[l])*pw[a.length()-1];
as=as*base+Hash(1LL*a[l],1LL*a[l]);
l++;
hs.insert(as);
}else {
as=as*base+Hash(1LL*a[i],1LL*a[i]);
if(i==a.length()-1)hs.insert(as);
}
// std::cout<<as.x<<" "<<as.y<<std::endl;
}
auto get=[&](int l,int r){
return bs[r]-bs[l-1]*pw[r-l+1];
};
int ans=0;
for(int i=1;i<=b.length();++i){
if(i+a.length()-1>b.length())break;
Hash check=get(i,i+a.length()-1);
if(hs.contains(check))ans++;
}
std::cout<<ans<<"\n";
}
return 0;
}
树
- 根据题意，若向一个集合中加入一个新点
- 对于大于点值的为mx*(mx-v)=mx^2-mx*v
- 对于小于点值的为v*(v-mi)=v^2-v*mi
- 总贡献为Sum{mx^2}+v^2*Num(mi)-v*Sum{集合}+v^2*Num(v)
- 即Sum{u^2(u>=v)}+v^2*Num(mi)-v*Sum{集合}
- 找出大于等于v的数平方和，集合的大小，小于v的数的个数，用值域线段树维护
- 往集合中加入，考虑dsu on tree
- 每次只将轻儿子加入集合中
- 轻儿子自己计算完后，撤销在线段树上的记录
- 重儿子不撤销记录，访问到轻儿子时，把轻儿子及其子树全一个个加入
- 由于轻儿子最多访问logn次，复杂度保证O(nlog^2)
- 注意模数为2^64，要开__int128
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int,int>;
struct Tr{
i64 sum1,sum2;int cnt;
Tr(): sum1(0),sum2(0),cnt(0) {}
Tr(i64 x,i64 y,int z): sum1(x),sum2(y),cnt(z) {}
};
Tr operator + (const Tr &a,const Tr &b){
return Tr(a.sum1+b.sum1,a.sum2+b.sum2,a.cnt+b.cnt);
}
struct Tree{
std::vector<Tr> tr;
int siz;
#define ls p<<1
#define rs p<<1|1
void init(int n){
siz=n*6;
tr.resize(siz);
}
void pushup(int p){
tr[p]=tr[ls]+tr[rs];
}
void build(int rt, int l, int r){
if (l == r){
// 初始化信息
return;
}
int m = (l + r) >> 1;
build(rt << 1, l, m);
build(rt << 1 | 1, m+1, r);
pushup(rt);
}
void update(int p,int l,int r,int k,const Tr &x){
if(l==r){
tr[p]=tr[p]+x;
return;
}
int mid=(l+r)>>1;
if(k<=mid)update(ls,l,mid,k,x);
else update(rs,mid+1,r,k,x);
pushup(p);
}
Tr query(int p,int l,int r,int ql,int qr){
if(ql==l&&r==qr){
return tr[p];
}
int mid=(l+r)>>1;
if(qr<=mid)return query(ls,l,mid,ql,qr);
else if(ql>mid)return query(rs,mid+1,r,ql,qr);
else return query(ls,l,mid,ql,mid)+ query(rs,mid+1,r,mid+1,qr);
}
Tr query(int ql,int qr){
if(ql>qr)return Tr();
return query(1,1,1e6,ql,qr);
}
};
inline void read(__int128 &n){
__int128 x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
n=x*f;
}
inline void print(__int128 n){
if(n<0){
putchar('-');
n*=-1;
}
if(n>9) print(n/10);
putchar(n % 10 + '0');
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
// long long md=(long long)998244353;
// i64 mx=LONG_LONG_MAX/2;
Tree tree;
tree.init(1e6);
tree.build(1,1,1e6);
int n;std::cin>>n;
std::vector<std::vector<int>> G(n+5);
for(int i=1;i<n;++i){
int u,v;std::cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
std::vector<int> a(n+5);
for(int i=1;i<=n;++i)std::cin>>a[i];
std::vector<int> son(n+5,0),sz(n+5,0);
auto dfs1=[&](auto self,int x,int fa)->void{
sz[x]=1;
for(auto v:G[x]){
if(v==fa)continue;
self(self,v,x);
sz[x]+=sz[v];
if(!son[x]||sz[son[x]]<sz[v])son[x]=v;
}
};
__int128 res=0;
__int128 base=1;
__int128 ans=0;
__int128 md=1;
for(int i=1;i<=64;++i)md=md*2;md=md-1;
auto mk=[&](int x,int op){
if(op){
Tr u=tree.query(a[x]+1,1e6);
Tr v=tree.query(1,a[x]);
Tr w=tree.query(1,1e6);
__int128 ress=base*u.sum2+base*a[x]*a[x]*v.cnt-base*w.sum1*a[x];
res+=ress;
tree.update(1,1,1e6,a[x],Tr(a[x],1LL*a[x]*a[x],1));
}else{
tree.update(1,1,1e6,a[x],Tr(-a[x],-1LL*a[x]*a[x],-1));
Tr u=tree.query(a[x]+1,1e6);
Tr v=tree.query(1,a[x]);
Tr w=tree.query(1,1e6);
__int128 ress=base*u.sum2+base*a[x]*a[x]*v.cnt-base*w.sum1*a[x];
res-=ress;
}
};
auto calc=[&](auto self,int x,int fa,int op)->void{
mk(x,op);
for(auto v:G[x]){
if(v!=fa)self(self,v,x,op);
}
};
auto dfs2=[&](auto self,int x,int fa)->void{
for(auto v:G[x]){
if(v==son[x]||v==fa)continue;
self(self,v,x);
calc(calc,v,x,0);
}
if(son[x])self(self,son[x],x);
for(auto v:G[x]){
if(v==fa||v==son[x])continue;
calc(calc,v,x,1);
}
mk(x,1);
ans=ans&md;
ans^=(res*2);
};
dfs1(dfs1,1,0);
dfs2(dfs2,1,0);
ans=ans&md;
print(ans);
}
博弈
- 考虑n种颜色全为偶数个
- 对于一种颜色，其个数为偶数t
- 选取方案数为t!
- 可以分为t/2组
- 对于已经分好组的各个颜色
- 共进行Sum/2=m轮
- 则分好的组往里放的方案数为
- C(m,t1)*C(m-t1,t2)*C(m-t1-t2,t3)……=》
- m!*inv[t1]*inv[m-t1]*(m-t1)!*inv[t2]*inv[m-t1-t2]*…… =》
- m!*inv[t1]*inv[t2]*inv[3]……
- 所以平局数为h1!*h2!*h3!*……*(Sum/2)!*inv[h1/2]*inv[h2/2]*inv[h3/2]……
- 总方案数为Sum!
- 所以平局的概率为h1!*h2!*h3!*……*(Sum/2)!*inv[h1/2]*inv[h2/2]*inv[h3/2]……*inv[Sum]
- 记作p
- 所以A赢的概率为(i-p)/2
- 现考虑有一种颜色为奇数个
- 先考虑将多的一个丢去
- 平局概率依旧为p，A赢为(1-p)/2
- 此时在平局后A再拿多的那个，A变为了赢
- 所以A赢概率为(1-p)/2+p
- 再考虑有多个奇数的
- 此时AB一定是能分出胜负的（等于个数全为1个）
- 且胜负可以调换，概率一定为1/2
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
using i64 = long long;
using pii = pair<int,int>;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
i64 md=998244353;
int N=1e7;
std::vector<i64> fac(N+5);
fac[0]=fac[1]=1;
for(int i=2;i<=N;++i){
fac[i]=fac[i-1]*i%md;
}
auto pow=[&](i64 a,i64 b){
i64 res=1;
while(b>0){
if(b&1)res=res*a%md;
a=a*a%md;
b>>=1;
}
return res;
};
i64 two=pow(2,md-2);
int T;
// T=1;
std::cin>>T;
for(;T>0;--T){
int n;std::cin>>n;
std::vector<int> h(n+5);
int sum=0;
int odd=0;
for(int i=1;i<=n;++i){
char x;std::cin>>x;
std::cin>>h[i];
if(h[i]&1)odd++;
sum+=h[i];
}
if(odd>1){
std::cout<<two<<std::endl;
continue;
}
i64 p=1;
i64 b=1;
for(int i=1;i<=n;++i){
p*=fac[h[i]]%md;p%=md;
}
b*=fac[sum]%md;b%=md;sum=0;
for(int i=1;i<=n;++i){
h[i]/=2;
sum+=h[i];
b*=fac[h[i]]%md;b%=md;
}
p*=fac[sum]%md;p%=md;
p*=pow(b,md-2)%md;p%=md;
// p*=fac[sum/2]%md*inv[sum]%md;
if(odd){
std::cout<<((md+1-p)%md*two%md+p)%md<<"\n";
}else std::cout<<(md+1-p)%md*two%md<<"\n";
}
return 0;
}
序列平方
- 若一种子序列有k个
- 则答案为K*k*k
- 从所有子序列中选出该种序列，有k种
- 独立的选3次，则组合起来有k*k*k种
- 定义 f i j k
- 表示第一次选的序列结尾为i，第二次选的结尾为j，第三次为k
- 此时3个序列相同的方案数
- 初始f[0][0][0]=1
- 考虑到子序列不连续
- 若当前ai=aj=ak,则可以由之前的任意一组相同的一步转移
- 暴力枚举达到n^6
- 考虑高维前缀和
- 容斥，前一维的-前两维的+前三维的
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
using i64 = long long;
using pii = pair<int,int>;
const i64 md=998244353;
void add(i64 &a,const i64 &b){
a=(a+b)%md;
}
void del(i64 &a,const i64 &b){
a=(md+a-b)%md;
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;
T=1;
// std::cin>>T;
for(;T>0;--T){
int n;std::cin>>n;
std::vector<int> a(n+5);
for(int i=1;i<=n;++i)std::cin>>a[i];
std::vector<std::vector<std::vector<i64>>> f(n+5,std::vector<std::vector<i64>>(n+5,std::vector<i64>(n+5,0LL)));
f[0][0][0]=1;//直接跳到长度为1的相同序列
i64 ans=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
for(int k=1;k<=n;++k){
add(f[i][j][k],f[i-1][j][k]);
add(f[i][j][k],f[i][j-1][k]);
add(f[i][j][k],f[i][j][k-1]);
del(f[i][j][k],f[i-1][j-1][k]);
del(f[i][j][k],f[i][j-1][k-1]);
del(f[i][j][k],f[i-1][j][k-1]);
add(f[i][j][k],f[i-1][j-1][k-1]);
if(a[i]==a[j]&&a[i]==a[k]){
add(ans,f[i][j][k]);
add(f[i+1][j+1][k+1],f[i][j][k]);//出现新的跳板
}
}
}
}
std::cout<<ans<<std::endl;
}
return 0;
}
并
- 一个矩阵有多个小正方形组成
- 考虑小正方形的贡献
- 若该小正方形被i个矩阵覆盖
- 想要消去其对答案的影响
- 则需要不选择覆盖其的i个矩阵
- 所以答案里有该小正方形的概率为 1-C(n-i,k)/C(n,k) (总-不选i个矩阵的任意一个))
- 由于x,y较大，考虑离散化
- 对于计算每个小正方形被多少个矩阵覆盖
- 用二维前缀和
- 给的是点坐标,要统计小正方形
- 转为格点坐标计算二维前缀和，x++,y++
- 例读入为点坐标，左上角为（1，1），即该格为(2,2)
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
using i64 = long long;
using pii = pair<int,int>;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
const i64 md=998244353;
const int N=4e3;
std::vector<i64> fac(N+5),inv(N+5),f0(N+5);//md为奇数
fac[1]=inv[1]=f0[1]=fac[0]=inv[0]=f0[0]=1;
for(int i=2;i<=N;++i){
fac[i]=fac[i-1]*i%md;
f0[i]=(md-md/i)*f0[md%i]%md;
inv[i]=inv[i-1]*f0[i]%md;
}
auto Cal=[&](i64 n,i64 m){
if(n<0||m<0||n<m)return 0LL;
return fac[n]*inv[m]%md*inv[n-m]%md;
};
int T;
T=1;
// std::cin>>T;
for(;T>0;--T){
struct M{
i64 x,y,x2,y2;
};
int n;std::cin>>n;
std::vector<M> ku(n+5);
std::vector<i64> a,b;
for(int i=1;i<=n;++i){
std::cin>>ku[i].x>>ku[i].y>>ku[i].x2>>ku[i].y2;
a.push_back(ku[i].x);a.push_back(ku[i].x2);
b.push_back(ku[i].y);b.push_back(ku[i].y2);
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
std::vector<i64> x(a.size()+5),y(b.size()+5);
std::map<i64,int> mpx,mpy;
int cntx=0,cnty=0;
for(int i=0;i<a.size();++i){
if(i==0) x[++cntx]=a[i];
else if(a[i]!=a[i-1])x[++cntx]=a[i];
}
for(int i=1;i<=cntx;++i){
mpx[x[i]]=i;
}
for(int i=0;i<b.size();++i){
if(i==0)y[++cnty]=b[i];
else if(b[i]!=b[i-1])y[++cnty]=b[i];
}
for(int i=1;i<=cnty;++i){
mpy[y[i]]=i;
}
std::vector<std::vector<int>> sum(cntx+5,std::vector<int>(cnty+5,0));
auto mk=[&](M now){
auto[x1,y1,x2,y2]=now;
x1=mpx[x1];x2=mpx[x2];
y1=mpy[y1];y2=mpy[y2];
x1++;y1++;
sum[x1][y1]++;
sum[x1][y2+1]--;
sum[x2+1][y1]--;
sum[x2+1][y2+1]++;
};
for(int i=1;i<=n;++i){
mk(ku[i]);
}
std::vector<i64> tot(n+5,0);
for(int i=1;i<=cntx;++i){
for(int j=1;j<=cnty;++j){
i64 tmp=(sum[i-1][j]+sum[i][j-1])%md;
tmp-=sum[i-1][j-1];tmp%=md;
sum[i][j]+=tmp;sum[i][j]%=md;
tot[sum[i][j]]+=1LL*(x[i]-x[i-1])*(y[j]-y[j-1])%md;
tot[sum[i][j]]%=md;
}
}
auto pow=[&](i64 a,i64 b){
i64 res=1;
while(b>0){
if(b&1)res=res*a%md;
a=a*a%md;
b>>=1;
}
return res;
};
std::vector<i64> ans(n+5,0);
for(int k=1;k<=n;++k){
i64 p=pow(Cal(n,k),md-2);
for(int i=1;i<=n;++i){
ans[k]+=tot[i]*(md+1-Cal(n-i,k)*p%md)%md;
ans[k]%=md;
}
}
for(int i=1;i<=n;++i)std::cout<<ans[i]<<"\n";
}
return 0;
}
三元环
- 有向图，任意两个点之间有唯一一条确认方向的边
- 所以生成图为竞赛图
- 有向三元环，环上三点之间的边，加上后，每个点的入度为1
- 答案为总方案-不合法
- 总方案为C(n,3)
- 对于一个点，若其在图中入度大于等于2
- 选择两个指向其的点，可以构成一个不合法的方案
- 所以不合法的方案为Sum i { C(in[i],2) }
- 由于点数很多，不能枚举建边
- 又因为i->j有边，满足i < j&&fi < fj&&gi < gj
- 所以考虑三维偏序
- 对于一点i，指向其的边个数为
- 加：
i<j && (fj <= fi ||gk <= gi ) 即i<-j,solve1
j<i && (fj < fi &&gj < gi ) 即j->i,solve2
- 减：
i<j && (fj <= fi &&gk <= gi ) 即i<-j,solve3
- 对于三维偏序
- 先将i排序
- 对于第二维做归并排序，CDQ分治
- 对于(l,mid),(mid+1,r)，其中第二维单调不降
- (l,mid)中fi,(mid+1,r)中fj
- fi fj满足偏序关系，则 gi入树状数组，可能对j有贡献，i往后走
- fi fj不满足，则i往后都不满足，j统计树状数组中g满足的个数，j往后走
- 注意清空树状数组，回退一遍标记即可
- (f,g,id)不会有重的，不用考虑去重
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int,int>;
const i64 md=998244353;
struct Tr{
int siz;
std::vector<i64> tr;
void init(int n){
siz=n;
tr.assign(n+5,0);
}
#define lowbit(x) (x&-x)
void update(int x,int k){
for(int i=x;i<=siz;i+=lowbit(i)){
tr[i]+=k;
}
}
int query(int x){
i64 res=0;
for(int i=x;i;i-=lowbit(i)){
res+=tr[i];
}
return res;
}
int query(int l,int r){
if(r>l)return 0;
else return query(r)-query(l-1);
}
};
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;std::cin>>n;
std::vector<int> f(n+5),g(n+5),in(n+5,0);
Tr tree;tree.init(n+5);
for(int i=1;i<=n;++i)std::cin>>f[i];
for(int i=1;i<=n;++i)std::cin>>g[i];
auto solve1=[&](){
for(int i=n;i>=1;--i)in[i]+=tree.query(f[i]),tree.update(f[i],1);
for(int i=n;i>=1;--i)tree.update(f[i],-1);
for(int i=n;i>=1;--i)in[i]+=tree.query(g[i]),tree.update(g[i],1);
for(int i=n;i>=1;--i)tree.update(g[i],-1);
};
solve1();
struct M{
int f,g,id;
bool operator<(const M&other)const{
return f<other.f;
}
};
std::vector<M> p(n+5);
auto solve2=[&](auto self,int l,int r)->void{
if(l>=r)return;
int mid=(l+r)>>1;
self(self,l,mid);self(self,mid+1,r);
sort(p.begin()+l,p.begin()+mid+1);
sort(p.begin()+mid+1,p.begin()+r+1);
int i,j;
for(i=l,j=mid+1;j<=r;++j){
while(i<=mid&&p[i].f<p[j].f)tree.update(p[i++].g,1);
in[p[j].id]+=tree.query(p[j].g-1);
}
//用了(l,i-1)
for(j=l;j<i;++j)tree.update(p[j].g,-1);
};
auto solve3=[&](auto self,int l,int r)->void{
if(l>=r)return;
int mid=(l+r)>>1;
self(self,l,mid);self(self,mid+1,r);
sort(p.begin()+l,p.begin()+mid+1);
sort(p.begin()+mid+1,p.begin()+r+1);
int i,j;
for(i=l,j=mid+1;i<=mid;++i){
while(j<=r&&p[j].f<=p[i].f)tree.update(p[j++].g,1);
in[p[i].id]-=tree.query(p[i].g);
}
for(i=mid+1;i<j;++i)tree.update(p[i].g,-1);
};
for(int i=1;i<=n;++i)p[i].f=f[i],p[i].g=g[i],p[i].id=i;
solve2(solve2,1,n);
for(int i=1;i<=n;++i)p[i].f=f[i],p[i].g=g[i],p[i].id=i;
solve3(solve3,1,n);
i64 ans=1LL*n*(n-1)*(n-2)/6LL;
for(int i=1;i<=n;++i)ans-=1LL*in[i]*(in[i]-1)/2LL;
std::cout<<ans<<std::endl;
return 0;
}
