ABC256G
题意：
给定一个边长为\(d\)的正\(n\)边形，每条边上每隔一个单位长度可以染黑或白色（恰有\(d+1\)个位置），问有多少种方法使得每条边上染的白色的数量都相同
\(n\leq 10^{12},d\leq 10^4\)
例：
\(n=3,d=2:\)
题解：
好吧一开始以为是和 \(d\)有关的数学公式，但是只是矩阵快速幂优化\(dp\)
考虑一个不优化的状压\(dp\)。
因为不好决定每条边到底有几个白点，不妨直接枚举一条边上有\(k\)个白点的方案数。
\(dp[i][0/1][0/1]\)表示到第\(i\)条边，最开始的点是白或黑，这条边的终点是白或黑。
因为这其实是个环，所以最后只有\(dp[n][0][0]\)和\(dp[n][1][1]\)才会有贡献。
这样就可以通过组合数来转移了。
\(dp[i+1][0][0]=dp[i][0][0]*\dbinom{d-1}{k}+dp[i][0][1]*\dbinom{d-1}{k-1}\)
\(dp[i+1][0][1]=dp[i][0][0]*\dbinom{d-1}{k-1}+dp[i][0][1]*\dbinom{d-1}{k-2}\)
\(dp[i+1][1][0]=dp[i][1][0]*\dbinom{d-1}{k}+dp[i][1][1]*\dbinom{d-1}{k-1}\)
\(dp[i+1][1][1]=dp[i][1][0]*\dbinom{d-1}{k-1}+dp[i][1][1]*\dbinom{d-1}{k-2}\)
然后用快速幂优化就可以了
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=998244353,inv2=5e8+4,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int n,m;
cin>>n>>m;
auto fast=[&](int x,int k) -> int
{
int ret=1;
while(k)
{
if(k&1) ret=ret*x%mod;
x=x*x%mod;
k>>=1;
}
return ret;
};
vector<int> fac(m+1),inv(m+1);
fac[0]=inv[0]=1;
for(int i=1;i<=m;++i) fac[i]=fac[i-1]*i%mod;
inv[m]=fast(fac[m],mod-2);
for(int i=m-1;i>=1;--i) inv[i]=inv[i+1]*(i+1)%mod;
auto C=[&](int n,int m) -> int
{
if(n<m||m<0) return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
};
struct matrix
{
int g[2][2];
void clear()
{
memset(g,0,sizeof(g));
}
void init()
{
memset(g,0,sizeof(g));
g[0][0]=g[1][1]=1;
}
matrix operator * (const matrix &t) const
{
matrix ret;
ret.clear();
for(int i=0;i<=1;++i)
{
for(int j=0;j<=1;++j)
{
for(int k=0;k<=1;++k)
{
ret.g[i][j]=(ret.g[i][j]+g[i][k]*t.g[k][j])%mod;
}
}
}
return ret;
}
matrix operator ^ (int k) const
{
matrix ret;
ret.init();
matrix x=*this;
while(k)
{
if(k&1) ret=ret*x;
x=x*x;
k>>=1;
}
return ret;
}
}st;
int ans=0;
for(int k=0;k<=m+1;++k)
{
matrix t;
t.g[0][0]=C(m-1,k);
t.g[0][1]=C(m-1,k-1);
t.g[1][0]=C(m-1,k-1);
t.g[1][1]=C(m-1,k-2);
t=t^n;
ans=(ans+t.g[0][0]+t.g[1][1])%mod;
//cout<<k<<' '<<ans<<endl;
}
cout<<ans<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/
ABC257G
题意：
给定两个字符串\(S,T\)
每次选中\(S\)的一个前缀，拼接起来，最少拼接几次才能得到\(T\)
\(|S|,|T|\leq 5*10^5\)
题解：
其实是一个串串题伪装的动态规划XD
设\(dp[i]\)表示把\(T\)的前\(i\)个字符拼接出来需要的最少次数。
那么可以从\(T\)的第i个字符开始，和\(S\)的前缀开始匹配，能匹配上的前缀的位置都可以通过一次拼接获得，用线段树更新一下区间最小值。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,base=233,inf=2e15;
const int mod[2]={1000000000+7,998244353};
void __init(int n=2000) {}
inline void main()
{
string s,t;cin>>s>>t;
int n=s.length(),m=t.length();
vector hs(n+1,vector<int>(2));
vector ht(m+1,vector<int>(2));
vector pw(n+m+1,vector<int>(2));
for(int k=0;k<=1;++k)
{
pw[0][k]=1;
for(int i=1;i<=n+m;++i) pw[i][k]=pw[i-1][k]*base%mod[k];
}
hs[0][0]=hs[0][1]=s[0];
ht[0][0]=ht[0][1]=t[0];
for(int i=1;i<n;++i)
{
for(int k=0;k<=1;++k)
{
hs[i][k]=(hs[i-1][k]*base+s[i])%mod[k];
}
}
for(int i=1;i<m;++i)
{
for(int k=0;k<=1;++k)
{
ht[i][k]=(ht[i-1][k]*base+t[i])%mod[k];
}
}
vector<int> ans(4*m+1,inf),tag(4*m+1,inf);
auto pushdown=[&](int l,int r,int p) -> void
{
ans[ls(p)]=min(ans[ls(p)],tag[p]);
ans[rs(p)]=min(ans[rs(p)],tag[p]);
tag[ls(p)]=min(tag[ls(p)],tag[p]);
tag[rs(p)]=min(tag[rs(p)],tag[p]);
tag[p]=inf;
};
function<void(int,int,int,int,int,int)> update=[&](int tl,int tr,int l,int r,int p,int k) -> void
{
if(tl>tr) return;
if(tl<=l&&r<=tr)
{
ans[p]=min(ans[p],k);
tag[p]=min(tag[p],k);
return;
}
if(tag[p]!=inf) pushdown(l,r,p);
if(tl<=mid) update(tl,tr,l,mid,ls(p),k);
if(tr>mid) update(tl,tr,mid+1,r,rs(p),k);
ans[p]=min(ans[ls(p)],ans[rs(p)]);
};
function<int(int,int,int,int)> query=[&](int pos,int l,int r,int p) ->int
{
if(l==r) return ans[p];
if(tag[p]!=inf) pushdown(l,r,p);
if(pos<=mid) return query(pos,l,mid,ls(p));
return query(pos,mid+1,r,rs(p));
};
auto gets=[&](int l,int r,int k) -> int
{
if(l>r) return -1;
if(l==0) return hs[r][k];
int tmp=(hs[r][k]-hs[l-1][k]*pw[r-l+1][k]%mod[k]+mod[k])%mod[k];
return tmp;
};
auto gett=[&](int l,int r,int k) -> int
{
if(l>r) return -1;
if(l==0) return ht[r][k];
int tmp=(ht[r][k]-ht[l-1][k]*pw[r-l+1][k]%mod[k]+mod[k])%mod[k];
return tmp;
};
auto check=[&](int st) -> int
{
int l=0,r=min(n,m-st);
while(l<=r)
{
if(gets(0,mid-1,0)==gett(st,st+mid-1,0)&&gets(0,mid-1,1)==gett(st,st+mid-1,1)) l=mid+1;
else r=mid-1;
}
return l-1;
};
int len=check(0);
//cout<<len<<"!!"<<endl;
update(1,len,1,m,1,1);
for(int i=1;i<m;++i)
{
int tmp=query(i,1,m,1);
if(tmp>m) continue;
int len=check(i);
//cout<<i<<' '<<len<<"!!"<<endl;
update(i+1,i+len,1,m,1,tmp+1);
}
int tmp=query(m,1,m,1);
if(tmp>m) cout<<"-1\n";
else cout<<tmp<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/
ABC255E
题意：
给定长度为\(n-1\)的序列\(S\)，构造序列\(A\)，满足
\(A_i+A_{i+1}=S_i\)
且序列\(A\)中的数字在集合\(S\)中的个数最多，求最多个数
\(n\leq 10^5,|S|\leq 10\)，其他数字\(\leq 10^9\)
题解：
其实可以发现，只要确定了\(A_1\)，整个序列就是固定的。
那么如果\(A_1+1\)，相应的，\(A_2\)就要\(-1\)，\(A_3\)就要再\(+1\)……递推下去，奇数位置\(+1\)，那么偶数位置就要\(-1\)
可以开一个桶，表示\(q[x]\)表示给奇数位置\(+x\)，会有多少个位置上的数字变成集合\(S\)中的数字。
偶数位置只要相应的变成减号就可以了。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inv2=5e8+4,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int n,m;
cin>>n>>m;
vector<int> s(n),a(n+1);
vector<int> lucy(m);
for(int i=1;i<n;++i) cin>>s[i];
for(int i=0;i<m;++i)
{
cin>>lucy[i];
}
a[1]=0;
for(int i=2;i<=n;++i)
{
a[i]=s[i-1]-a[i-1];
}
map<int,int> q;
int ans=0;
for(int i=1;i<=n;++i)
{
for(int j=0;j<m;++j)
{
int x=a[i]-lucy[j];
if(i&1) x=-x;
++q[x];
ans=max(ans,q[x]);
}
}
cout<<ans<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/
ABC255G
题意：
给定\(n\)堆石子玩\(Nim\)游戏，但是有\(m\)个限制，每个表示当一堆石子还剩\(x_i\)个的时候，不能从里面拿走\(y_i\)个。
问先手胜负情况。
\(n,m\leq 2*10^5\)，其他数字小于等于\(10^9\)
题解：
考虑单堆石子的\(sg\)函数，多堆石子用异或和。
先考虑有限制的点，考虑\(sg\)函数的一个特性，在没有限制的范围内，\(sg\)值是\(0,1,2,3……\)这样连续上升的。
有限制的点会破坏这里，比如一个点不能转移到\(sg\)比较小的点去，那么就有可能他能到的位置恰好没有了这个点，它的\(sg\)就变成了这个点的值。
这种点不超过\(m\)个。
而跳过这种点之后，剩下的非限制点又会继续变成前面的最大值\(+1\)。
所以从小到大对限制点进行处理，顺便统计到这个点为止停顿了多少次增长，就可以算出每个点的\(sg\)值了。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inv2=5e8+4,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int n,m;
cin>>n>>m;
map<int,vector<int> > q;
vector<int> a(n);
for(int i=0;i<n;++i) cin>>a[i];
vector<int> c(m);
for(int i=1;i<=m;++i)
{
int x,y;
cin>>x>>y;
c[i-1]=x;
q[x].emplace_back(x-y);
}
sort(c.begin(),c.end());
c.erase(unique(c.begin(),c.end()),c.end());
map<int,int> e,sg,ss;
int tot=0;
auto getsg=[&](int x) -> int
{
int t=upper_bound(c.begin(),c.end(),x)-c.begin()-1;
if(t==-1) return x;
if(x==c[t]) return sg[c[t]];
return x-ss[c[t]];
};
for(int x:c)
{
int ret=x-tot;
//cout<<x<<"!!!!!!!!"<<endl;
map<int,int> cnt;
bool flag=0;
for(int y:q[x])
{
int tmp=getsg(y);
++cnt[tmp];
if(e.find(tmp)==e.end()||cnt[tmp]==e[tmp]+1)
{
flag=1;
ret=min(ret,tmp);
}
//if(x==7) cout<<y<<' '<<tmp<<' '<<e[3]<<"!!!"<<endl;
}
//cout<<x<<' '<<ret<<"!!!!!!!!!!!!!!!!"<<endl;
if(ret!=x-tot) ++tot;
ss[x]=tot;
sg[x]=ret;
if(flag)
{
++e[ret];
}
}
int ans=0;
for(int i=0;i<n;++i)
{
//cout<<a[i]<<' '<<getsg(a[i])<<'\n';
ans^=getsg(a[i]);
}
if(ans) cout<<"Takahashi\n";
else cout<<"Aoki\n";
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/
ABC256Ex
题意：
给定长度\(n\)的一个序列，有\(m\)次三种操作：
\(1.\)区间除法（下取整）
\(2.\)区间赋值
\(3.\)区间求和
\(n,m\leq 5*10^5\)
题解：
势能线段树。
考虑第一种操作，一个数组最多被除以\(log\)次就会都变成\(0\)，然后就不用再除了，这部分势能是\(nlogn\)
但是赋值会把刚刚变成\(0\)的数字变回去。
好在我们发现，如果一段区间都是同一个数字，那么做区间除法就可以快速实现了。
区间赋值的时候，我们最多把\(2log\)个区间变成不是同一个数字（两个端点所在的为止），其他位置的情况不会被改变，所以这部分给了\(2mlogn\)的势能。
总的思路就是如果区间里是同一段数字，做除法就打标记，否则直接暴力。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inv2=5e8+4,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int n,m;
cin>>n>>m;
vector<int> a(n+1);
vector<int> ans(4*n+1),tag(4*n+1);
vector<int> vis(4*n+1);
auto pushup=[&](int p) -> void
{
if(vis[ls(p)]==vis[rs(p)]&&vis[ls(p)]>=0&&vis[rs(p)]>=0)
{
vis[p]=vis[ls(p)];
}
else vis[p]=-1;
ans[p]=ans[ls(p)]+ans[rs(p)];
};
function<void(int,int,int)> build=[&](int l,int r,int p) -> void
{
tag[p]=-1;
if(l==r)
{
vis[p]=a[l];
ans[p]=a[l];
return;
}
build(l,mid,ls(p));
build(mid+1,r,rs(p));
pushup(p);
};
auto pushdown=[&](int l,int r,int p) -> void
{
vis[ls(p)]=tag[p];
vis[rs(p)]=tag[p];
tag[ls(p)]=tag[rs(p)]=tag[p];
ans[ls(p)]=(mid-l+1)*tag[p];
ans[rs(p)]=(r-mid)*tag[p];
tag[p]=-1;
return;
};
function<void(int,int,int,int,int,int)> update=[&](int tl,int tr,int l,int r,int p,int k)-> void
{
if(tl<=l&&r<=tr)
{
if(vis[p]==-1)
{
if(~tag[p]) pushdown(l,r,p);
update(tl,tr,l,mid,ls(p),k);
update(tl,tr,mid+1,r,rs(p),k);
pushup(p);
}
else
{
vis[p]/=k;
ans[p]=(r-l+1)*vis[p];
tag[p]=vis[p];
}
return;
}
if(~tag[p]) pushdown(l,r,p);
if(tl<=mid) update(tl,tr,l,mid,ls(p),k);
if(tr>mid) update(tl,tr,mid+1,r,rs(p),k);
pushup(p);
};
function<void(int,int,int,int,int,int)> update2=[&](int tl,int tr,int l,int r,int p,int k)-> void
{
if(tl<=l&&r<=tr)
{
vis[p]=tag[p]=k;
ans[p]=(r-l+1)*k;
return;
}
if(~tag[p]) pushdown(l,r,p);
if(tl<=mid) update2(tl,tr,l,mid,ls(p),k);
if(tr>mid) update2(tl,tr,mid+1,r,rs(p),k);
pushup(p);
};
function<int(int,int,int,int,int)> query=[&](int tl,int tr,int l,int r,int p) -> int
{
if(tl<=l&&r<=tr) return ans[p];
if(~tag[p]) pushdown(l,r,p);
int sum=0;
if(tl<=mid) sum+=query(tl,tr,l,mid,ls(p));
if(tr>mid) sum+=query(tl,tr,mid+1,r,rs(p));
return sum;
};
for(int i=1;i<=n;++i)
{
cin>>a[i];
}
build(1,n,1);
for(int i=1;i<=m;++i)
{
int opt,l,r,x;
cin>>opt>>l>>r;
if(opt==1)
{
cin>>x;
update(l,r,1,n,1,x);
}
if(opt==2)
{
cin>>x;
update2(l,r,1,n,1,x);
}
if(opt==3)
{
cout<<query(l,r,1,n,1)<<'\n';
}
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/