∆ P4108 [HEOI2015]公约数数列 - RE
GCD 不同取值是 的，直接考虑枚举。
先对序列分个块，然后修改该怎么来怎么来。
询问，对每个块分类讨论一下；
- 整块 GCD 相同
看是否有 XOR 为 的，这种东西已经成了套路了，一个 map 莽上去或者你愿意手写平衡树也行。
还是提一句，map 存的是 XOR 前缀和。
#include<map>
#include<cstdio>
using namespace std;
long long gcd(long long x,long long y)
{
if(y==0) return x;
else return gcd(y,x%y);
}
const long long each=320;
map<long long,long long> mp[500];
long long n,m,a[100010],belong[100010],pregcd[100010],prexor[100010],opx,opy,bone[500],bano[500],flag,ans;
char opt[10];
int main()
{
scanf("%lld",&n);
for(long long i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
belong[i]=(i-1)/each+1;
}
for(long long i=1;i<=belong[n];++i)
{
bone[i]=(i-1)*each+1;
bano[i]=i*each;
if(i==belong[n]) bano[i]=n;
pregcd[bone[i]]=a[bone[i]];
prexor[bone[i]]=a[bone[i]];
mp[bone[i]][a[bone[i]]]=bone[i];
for(long long j=bone[i]+1;j<=bano[i];++j)
{
pregcd[j]=gcd(pregcd[j-1],a[j]);
prexor[j]=(prexor[j-1]^a[j]);
if(mp[i].find(prexor[j])==mp[i].end()) mp[i][prexor[j]]=j;
}
}
scanf("%lld",&m);
for(long long i=1;i<=m;++i)
{
scanf("%s%lld",opt,&opx);
if(opt[0]=='M')
{
opx++;
scanf("%lld",&opy);
a[opx]=opy;
mp[belong[opx]].clear();
pregcd[bone[belong[opx]]]=a[bone[belong[opx]]];
prexor[bone[belong[opx]]]=a[bone[belong[opx]]];
mp[bone[belong[opx]]][a[bone[belong[opx]]]]=bone[belong[opx]];
for(long long j=bone[belong[opx]]+1;j<=bano[belong[opx]];++j)
{
pregcd[j]=gcd(pregcd[j-1],a[j]);
prexor[j]=(prexor[j-1]^a[j]);
if(mp[belong[opx]].find(prexor[j])==mp[belong[opx]].end()) mp[belong[opx]][prexor[j]]=j;
}
}
else
{
flag=ans=0;
for(long long j=1;j<=bano[1];++j)
{
if(pregcd[j]*prexor[j]==opx)
{
flag=1;
ans=j-1;
break;
}
}
if(flag) printf("%lld\n",ans);
else
{
long long curgcd=pregcd[bano[1]],curxor=prexor[bano[1]];
for(long long j=2;j<=belong[n];++j)
{
long long none=gcd(curgcd,pregcd[bano[j]]);
if(none^curgcd)
{
if(opx%none) curxor^=prexor[bano[j]];
else
{
long long tmp=mp[j][(opx/none)^curxor];
if(tmp)
{
flag=1;
ans=tmp-1;
break;
}
}
curxor^=prexor[bano[j]];
}
else
{
for(long long k=bone[j];k<=bano[j];++k)
{
curgcd=gcd(curgcd,a[k]);
curxor^=a[k];
if(curgcd*curxor==opx)
{
flag=1;
ans=k-1;
break;
}
}
}
if(flag) break;
}
if(flag) printf("%lld\n",ans);
else printf("no\n");
}
}
}
return 0;
}
∆ P2150 [NOI2015] 寿司晚宴 - WA
暴力就f[i][s1][s2]，转移f[i+1][s1|k][s2]+=f[i][s1][s2],f[i+1][s1][s2|k]+=f[i][s1][s2]。 大质因子最多一个，单独拿出来做dp。onedp[i][s1][s2]表示第一个人选了这个大因子，anodp同理。 然后合并答案dp[i][s1][s2]=onedp+anodp-dp
/*
暴力就f[i][s1][s2]，转移f[i+1][s1|k][s2]+=f[i][s1][s2],f[i+1][s1][s2|k]+=f[i][s1][s2]。
大质因子最多一个，单独拿出来做dp。onedp[i][s1][s2]表示第一个人选了这个大因子，anodp同理。
然后合并答案dp[i][s1][s2]=onedp+anodp-dp
*/
#include<cstdio>
#include<algorithm>
using namespace std;
const int up=1<<8;
int n,p,onedp[2][up+5][up+5],anodp[2][up+5][up+5],dp[2][up+5][up+5],turn,ans;
int pri[10]={2,3,5,7,11,13,17,19};
struct node
{
int lar,nor;
}num[510];
bool cmp(node one,node ano)
{
return one.lar<ano.lar;
}
int main()
{
// freopen("test.out","w",stdout);
scanf("%d%d",&n,&p);
n--;
for(int i=1;i<=n;++i)
{
int tmp=i+1;
for(int j=0;j<8;++j)
{
if(tmp%pri[j]==0)
{
while(tmp%pri[j]==0) tmp/=pri[j];
num[i].nor|=(1<<j);
}
}
num[i].lar=tmp;
}
sort(num+1,num+n+1,cmp);
dp[0][0][0]=1;
for(int i=1;i<=n;++i)
{
if(i==1||num[i].lar==1||(num[i].lar^num[i-1].lar))
{
for(int j=0;j^up;++j)
{
for(int k=0;k^up;++k)
{
onedp[turn][j][k]=onedp[turn^1][j][k]=dp[turn][j][k];
anodp[turn][j][k]=anodp[turn^1][j][k]=dp[turn][j][k];
}
}
}
for(int j=0;j^up;++j)
{
for(int k=0;k^up;++k)
{
if(!(j&k))
{
if(!(num[i].nor&j))
{
anodp[turn^1][j][k|num[i].nor]=(anodp[turn^1][j][k|num[i].nor]+anodp[turn][j][k])%p;
// printf("%d %d %d %d\n",j,k,anodp[turn^1][j][k|num[i].nor],anodp[turn][j][k]);
}
if(!(num[i].nor&k)) onedp[turn^1][j|num[i].nor][k]=(onedp[turn^1][j|num[i].nor][k]+onedp[turn][j][k])%p;
// printf("%d %d\n",anodp[turn^1][j][k],onedp[turn^1][j][k]);
}
}
}
if(i==n||num[i].lar==1||(num[i].lar^num[i+1].lar))
{
for(int j=0;j^up;++j)
{
for(int k=0;k^up;++k)
{
if(!(j&k)) dp[turn^1][j][k]=(onedp[turn^1][j][k]+anodp[turn^1][j][k]-dp[turn][j][k]+p)%p;
}
}
}
turn^=1;
}
for(int i=0;i^up;++i)
{
for(int j=0;j^up;++j)
{
if(!(i&j)) ans=(ans+dp[turn^1][i][j])%p;
}
}
printf("%d\n",ans);
return 0;
}
∆ P2522 [HAOI2011]Problem b - AC
....
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,a,b,c,d,k,tag[50010],pSet[50010],mu[50010],cnt;
void sieve(long long x)
{
tag[1]=mu[1]=1;
for(long long i=2;i<=x;++i)
{
if(!tag[i])
{
pSet[++cnt]=i;
mu[i]=-1;
}
for(long long j=1;j<=cnt&&i*pSet[j]<=x;++j)
{
tag[pSet[j]*i]=1;
if(i%pSet[j]==0)
{
mu[pSet[j]*i]=0;
break;
}
else mu[pSet[j]*i]=-mu[i];
}
}
for(long long i=1;i<=x;++i) mu[i]+=mu[i-1];
}
long long calc(long long x,long long y)
{
x/=k;
y/=k;
long long res=0;
for(long long l=1,r;l<=min(x,y);l=r+1)
{
r=min(x/(x/l),y/(y/l));
res+=(mu[r]-mu[l-1])*(x/l)*(y/l);
}
return res;
}
int main()
{
sieve(50000);
scanf("%lld",&n);
for(long long i=1;i<=n;++i)
{
scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
printf("%lld\n",calc(b,d)-calc(b,c-1)-calc(a-1,d)+calc(a-1,c-1));
}
return 0;
}
∆ P3327 [SDOI2015]约数个数和 - AC
/*
\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij) \\
\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k=1}^{n}\sum_{l=1}^{m}[\gcd(k,l)=1] \\
\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k|i}\sum_{l|j}\sum_{d|\gcd(k,l)}\mu(d) \\
\sum_{k|n}\sum_{l|m}\sum_{d|\gcd(k,l)}\mu(d)(n/k)(m/l) \\
\sum_{k|n}\sum_{l|m}\sum_{d|\gcd(k,l)}\mu(d)(n/k)(m/l) \\
s[i]=\sum_{j=1}^{i}i/j,n<m \\
\sum_{i=1}^{n}\mu(i)s[n/i]s[m/i]
*/
#include<cstdio>
#include<algorithm>
using namespace std;
long long t,n,m,pSet[50010],cnt,tag[50010],mu[50010],ans,s[50010];
void sieve(long long x)
{
tag[1]=mu[1]=1;
for(long long i=2;i<=x;++i)
{
if(!tag[i])
{
pSet[++cnt]=i;
mu[i]=-1;
}
for(long long j=1;j<=cnt&&i*pSet[j]<=x;++j)
{
tag[pSet[j]*i]=1;
if(i%pSet[j]==0)
{
mu[pSet[j]*i]=0;
break;
}
else mu[pSet[j]*i]=-mu[i];
}
}
for(long long i=1;i<=x;++i)
{
mu[i]+=mu[i-1];
long long tmp=0;
for(long long l=1,r;l<=i;l=r+1)
{
r=i/(i/l);
tmp+=(i/l)*(r-l+1);
}
s[i]=tmp;
}
}
int main()
{
sieve(50000);
scanf("%lld",&t);
for(long long i=1;i<=t;++i)
{
scanf("%lld%lld",&n,&m);
ans=0;
if(n>m) swap(n,m);
for(long long l=1,r;l<=n;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans+=(mu[r]-mu[l-1])*s[n/l]*s[m/l];
}
printf("%lld\n",ans);
}
return 0;
}
∆ P2257 YY的GCD - AC
/*
\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)\in P] \\
\sum_{i=1}^{n}\sum_{j=1}^{m}[\sigma_{0}(\gcd(i,j))=2] \\
\sum_{d=1}^{\min(n,m)}[\sigma_{0}(d)=2]\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d] \\
\sum_{d=1}^{\min(n,m)}[\sigma_{0}(d)=2]\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[\gcd(i,j)=1] \\
\sum_{d=1}^{\min(n,m)}[\sigma_{0}(d)=2]\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\sum_{k|\gcd(i,j)}\mu(k) \\
\sum_{d=1}^{\min(n,m)}[\sigma_{0}(d)=2]\sum_{k=1}^{\min(n,m)/d}\mu(k)\times(n/d/k)\times(m/d/k) \\
\sum_{d=1}^{\min(n,m)}[\sigma_{0}(d)=2]\sum_{k=1}^{\min(n,m)/d}\mu(k)\times(n/(dk))\times(m/(dk)) \\
\sum_{T=1}^{\min(n,m)}\sum_{d|T}[\sigma_{0}(d)=2]\sum_{k=1}^{\min(n,m)/d}\mu(T/d)\times(n/T)\times(m/T) \\
\sum_{T=1}^{\min(n,m)}(n/T)\times(m/T)\sum_{d|T}[\sigma_{0}(d)=2]\mu(T/d) \\
*/
#include<cstdio>
#include<algorithm>
using namespace std;
long long t,n,m,tag[10000010],pSet[10000010],cnt,mu[10000010],f[10000010],ans;
void sieve(long long x)
{
tag[1]=mu[1]=1;
for(long long i=2;i<=x;++i)
{
if(!tag[i])
{
pSet[++cnt]=i;
mu[i]=-1;
}
for(int j=1;j<=cnt&&pSet[j]*i<=x;++j)
{
tag[pSet[j]*i]=1;
if(i%pSet[j]==0)
{
mu[pSet[j]*i]=0;
break;
}
else mu[pSet[j]*i]=-mu[i];
}
}
for(int i=1;i<=cnt;++i)
{
for(int j=1;pSet[i]*j<=x;++j) f[pSet[i]*j]+=mu[j];
}
for(int i=1;i<=x;++i) f[i]+=f[i-1];
}
int main()
{
sieve(10000000);
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&m);
ans=0;
long long yu=min(n,m);
for(long long l=1,r;l<=yu;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans+=(f[r]-f[l-1])*(n/l)*(m/l);
}
printf("%lld\n",ans);
}
return 0;
}
∆ P4449 于神之怒加强版 - AC
不想写公式了。
#include <cstdio>
const int Maxn = 5e6 + 5;
const int Mod = 1e9 + 7;
int T, n, m, k, tag[Maxn], pri[Maxn], F[Maxn], K[Maxn];
int mul(int x, int y) { return 1ll * x * y % Mod; }
int add(int x, int y) { return (x + y) % Mod; }
int sub(int x, int y) { return ((x - y) % Mod + Mod) % Mod; }
int Quickpow(int x, int y)
{
int ret = 1;
for (; y; y >>= 1, x = mul(x, x))
if (y & 1) ret = mul(ret, x);
return ret % Mod;
}
void search(int lim)
{
F[1] = 1;
for (int i = 2; i <= lim; ++i)
{
if (tag[i] == 0)
{
pri[++pri[0]] = i;
K[i] = Quickpow(i, k);
F[i] = sub(K[i], 1);
}
for (int j = 1; j <= pri[0] && i * pri[j] <= lim; ++j)
{
tag[i * pri[j]] = 1;
if (i % pri[j]) F[i * pri[j]] = mul(F[i], F[pri[j]]);
else
{
F[i * pri[j]] = mul(F[i], K[pri[j]]);
break;
}
}
}
for (int i = 1; i <= lim; ++i) F[i] = add(F[i], F[i - 1]);
}
int Min(int x, int y) { return x > y ? y : x; }
signed main()
{
scanf("%d %d", &T, &k);
search(5e6);
while (T--)
{
scanf("%d %d", &n, &m);
if (n > m) n ^= m ^= n ^= m;
int ans = 0;
for (int l = 1, r; l <= n; l = r + 1)
{
r = Min(n / (n / l), m / (m / l));
ans = add(ans, mul(sub(F[r], F[l - 1]), mul(n / l, m / l)));
}
printf("%d\n", ans);
}
return 0;
}
∆ P1829 [国家集训队]Crash的数字表格 / JZPTAB - AC
/*
\sum_{i=1}^{n}\sum_{j=1}^{m}\text{lcm}(i,j) \\
\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{\gcd(i,j)} \\
\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|i,d|j}\frac{ij}{d}[d=\gcd(i,j)] \\
\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|i,d|j}\frac{ij}{d}[1=\gcd(i/d,j/d)] \\
\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}ij[1=\gcd(i,j)] \\
\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}ij\sum_{k|i,k|j}\mu(k) \\
\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\sum_{k|i,k|j}\mu(k)ij \\
s(i)=\sum_{j=1}^{i}j \\
\sum_{d=1}^{\min(n,m)}d\sum_{k=1}^{\min(n,m)/d}\mu(k)s(n/(dk))s(m/(dk))k^{2} \\
\sum_{T=1}^{\min(n,m)}\sum_{d|T}d\times\mu(T/d)s(n/T)s(m/T)(\frac{T}{d})^{2} \\
\sum_{T=1}^{\min(n,m)}s(n/T)s(m/T)\sum_{d|T}d\times\mu(T/d)(\frac{T}{d})^{2} \\
\sum_{T=1}^{\min(n,m)}s(n/T)s(m/T)T\sum_{d|T}\frac{T}{d}\times\mu(T/d) \\
\sum_{T=1}^{\min(n,m)}s(n/T)s(m/T)T\sum_{d|T}d\times\mu(d) \\
f(T)=\sum_{d|T}d\times\mu(d) \\
\text{sieve f} \\
f(1)=1,f(p)=1-p,f(p^{k})=1+\sum_{i=1}^{k}p^{i}\mu(p^{i})=1-p=f(p)
*/
#include<cstdio>
#include<algorithm>
using namespace std;
const int mod=20101009;
long long ans;
int n,m,tag[10000010],pSet[10000010],cnt,f[10000010],s[10000010];
void sieve(int x)
{
f[1]=tag[1]=1;
for(int i=2;i<=x;++i)
{
if(!tag[i])
{
pSet[++cnt]=i%mod;
f[i]=(1-i+mod)%mod;
}
for(int j=1;j<=cnt&&pSet[j]*i<=x;++j)
{
tag[pSet[j]*i]=1;
if(i%pSet[j]==0)
{
int tmp=i/pSet[j];
while(tmp%pSet[j]==0) tmp/=pSet[j];
if(tmp==1) f[pSet[j]*i]=(1-pSet[j]+mod)%mod;
else f[pSet[j]*i]=(long long)f[pSet[j]*i/tmp]*f[tmp]%mod;
break;
}
else f[pSet[j]*i]=(long long)f[pSet[j]]*f[i]%mod;
}
}
for(int i=1;i<=x;++i) f[i]=(long long)f[i]*i%mod;
for(int i=1;i<=x;++i)
{
f[i]=(f[i]+f[i-1])%mod;
s[i]=(s[i-1]+i)%mod;
}
}
int main()
{
sieve(10000000);
scanf("%d %d",&n,&m);
ans=0;
int yu=min(n,m);
for(int l=1,r;l<=yu;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans+=((long long)(f[r]-f[l-1]+mod)*s[n/l]%mod)*s[m/l]%mod;
}
printf("%lld\n",(ans+mod)%mod);
return 0;
}
∆ LOC6388 gcd求和（1e6 组询问 1<=n=m<=1e7） - AC
/*
\large\text{For 1e6 part} \\
\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j) \\
\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d] \\
\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[\gcd(i,j)=1] \\
\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\sum_{k|i,k|j}\mu(k) \\
\sum_{d=1}^{\min(n,m)}d\sum_{k|(n/d),k|(m/d)}\mu(k)(n/(dk))(m/(dk)) \\
\sum_{d=1}^{\min(n,m)}d\sum_{k|(n/d),k|(m/d)}\mu(k)(n/(dk))(m/(dk)) \\
\sum_{T=1}^{\min(n,m)}\sum_{d|T}d\times\mu(T/d)\times(n/T)\times(m/T) \\
\sum_{T=1}^{\min(n,m)}(n/T)\times(m/T)\times\sum_{d|T}d\times\mu(T/d) \\
\sum_{T=1}^{n}(n/T)^{2}\times\varphi(T) \\
\text{precalculate the last part} \\
\large\text{For 1e7 part} \\
n=m \\
\left(2\sum_{i=1}^{n}\sum_{j=1}^{i}\gcd(i,j)\right)-\frac{n(n+1)}{2} \\
\left(2\sum_{i=1}^{n}\sum_{d|i}d\times\sum_{j=1}^{i}[\gcd(i,j)=d]\right)-\frac{n(n+1)}{2} \\
\left(2\sum_{i=1}^{n}\sum_{d|i}d\times\sum_{j=1}^{i/d}[\gcd(i/d,j)=1]\right)-\frac{n(n+1)}{2} \\
\left(2\sum_{i=1}^{n}\sum_{d|i}d\times\varphi(i/d)\right)-\frac{n(n+1)}{2} \\
f(i)=\sum_{d|i}d\times\varphi(i/d) \\
\text{f(i) is able to be sieved;} \\
f(1)=1,f(p)=p-1+p=2\times p-1,f(p^{k})=(k+1)\times p^{k}-k\times p^{k-1}
*/
#include<cstdio>
#include<algorithm>
using namespace std;
int id,t,n,m,tag[10000010],prime[10000010],cnt;
long long f[10000010],phi[10000010];
long long cqpow(long long bas,int fur)
{
long long res=1;
while(fur)
{
if(fur&1) res*=bas;
bas*=bas;
fur>>=1;
}
return res;
}
void search(int x)
{
tag[1]=phi[1]=1;
for(int i=2;i<=x;++i)
{
if(!tag[i])
{
prime[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&(long long)prime[j]*i<=x;++j)
{
tag[prime[j]*i]=1;
if(i%prime[j]==0)
{
phi[prime[j]*i]=phi[i]*prime[j];
break;
}
else phi[prime[j]*i]=phi[i]*(prime[j]-1);
}
}
for(int i=1;i<=x;++i) phi[i]+=phi[i-1];
}
long long calc(int x,int y)
{
long long res=0;
int lim=min(x,y);
for(int l=1,r;l<=lim;l=r+1)
{
r=min(x/(x/l),y/(y/l));
res+=(long long)(n/l)*(m/l)*(phi[r]-phi[l-1]);
}
return res;
}
void exsearch(int x)
{
tag[1]=f[1]=1;
for(int i=2;i<=x;++i)
{
if(!tag[i])
{
prime[++cnt]=i;
f[i]=(i<<1)-1;
}
for(int j=1;j<=cnt&&(long long)prime[j]*i<=x;++j)
{
tag[prime[j]*i]=1;
if(i%prime[j]==0)
{
int tmp=i/prime[j],power=2;
while(tmp%prime[j]==0)
{
tmp/=prime[j];
power++;
}
if(tmp==1) f[prime[j]*i]=(power+1)*cqpow(prime[j],power)-power*cqpow(prime[j],power-1);
else f[prime[j]*i]=f[prime[j]*i/tmp]*f[tmp];
break;
}
else f[prime[j]*i]=f[prime[j]]*f[i];
}
}
for(int i=1;i<=x;++i) f[i]+=f[i-1];
}
long long excalc(long long x)
{
return (f[x]<<1)-((x*(x+1))>>1);
}
int main()
{
scanf("%d%d",&id,&t);
if(id^7)
{
search(1000000);
while(t--)
{
scanf("%d%d",&n,&m);
printf("%lld\n",calc(n,m));
}
}
else
{
exsearch(10000000);
while(t--)
{
scanf("%d%d",&n,&m);
printf("%lld\n",excalc(n));
}
}
return 0;
}
∆ P3312 [SDOI2014]数表 - AC
/*
\sum_{i=1}^{n}\sum_{j=1}^{m}\sigma(\gcd(i,j))[\sigma(\gcd(i,j))\le a] \\
\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|i,d|j}\sigma(d)[\sigma(d)\le a][d=\gcd(i,j)] \\
\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\sigma(d)[\sigma(d)\le a][1=\gcd(i,j)] \\
\sum_{d=1}^{\min(n,m)}\sigma(d)[\sigma(d)\le a]\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[1=\gcd(i,j)] \\
\sum_{d=1}^{\min(n,m)}\sigma(d)[\sigma(d)\le a]\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\sum_{k|i,k|j}\mu(k) \\
\sum_{T=1}^{\min(n,m)}\sum_{d|T}\sigma(d)[\sigma(d)\le a]\mu(T/d)(n/T)(m/T) \\
\sum_{T=1}^{\min(n,m)}(n/T)(m/T)\sum_{d|T}\sigma(d)[\sigma(d)\le a]\mu(T/d) \\
f(d)=\sigma(d)[\sigma(d)\le a] \\
\sum_{T=1}^{\min(n,m)}(n/T)(m/T)\sum_{d|T}f(d)\mu(T/d) \\
f(1)=[1\le a],f(p)=(p+1)[p+1\le a],f(p^{k})=(kp+1)[kp+1\le a] \\
s(T)=\sum_{d|T}f(d)\mu(T/d) \\
\sum_{T=1}^{\min(n,m)}(n/T)(m/T)s(T) \\
s(1)=1,s(p)=
*/
#include<cstdio>
#include<algorithm>
using namespace std;
void read(unsigned int &x)
{
x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+(c^'0');
c=getchar();
}
}
void write(unsigned int x)
{
if(x>9) write(x/10);
putchar((x%10)^'0');
}
struct node
{
unsigned int x,y,a,ID;
}nodes[20010];
struct edon
{
unsigned int ori,si;
}sedon[100010];
const unsigned int mod=(1u<<31);
unsigned int t,n,m,a,tag[100010],prime[100010],cnt,sig[100010],mu[100010],ans[20010],fro=1,fen[100010];
#define lowbit(x) ((x)&-(x))
void ins(unsigned int x,unsigned int y)
{
while(x<=100000)
{
fen[x]+=y;
x+=lowbit(x);
}
}
unsigned int find(unsigned int x)
{
unsigned int res=0;
while(x)
{
res+=fen[x];
x^=lowbit(x);
}
return res;
}
bool cmp(node one,node ano)
{
return one.a<ano.a;
}
bool pmc(edon one,edon ano)
{
return one.si<ano.si;
}
void search(unsigned int x)
{
tag[1]=mu[1]=1;
for(unsigned int i=1;i<=x;++i)
{
for(unsigned int j=1;j*j<=i;++j)
{
if(i%j==0)
{
if((j*j)^i) sig[i]+=j+i/j;
else sig[i]+=j;
}
}
}
for(unsigned int i=2;i<=x;++i)
{
if(!tag[i])
{
prime[++cnt]=i;
mu[i]=-1;
}
for(unsigned int j=1;j<=cnt&&prime[j]*i<=x;++j)
{
tag[prime[j]*i]=1;
if(i%prime[j]==0)
{
mu[prime[j]*i]=0;
break;
}
else mu[prime[j]*i]=-mu[i];
}
}
for(unsigned int i=1;i<=x;++i)
{
sedon[i].ori=i;
sedon[i].si=sig[i];
}
}
void solve(unsigned int x,unsigned int y,unsigned int a,unsigned int id)
{
while(fro<=100000&&sedon[fro].si<=a)
{
for(unsigned int i=1;i*sedon[fro].ori<=100000;++i) ins(i*sedon[fro].ori,sedon[fro].si*mu[i]);
fro++;
}
unsigned int res=0,lim=min(x,y);
for(unsigned int l=1,r;l<=lim;l=r+1)
{
r=min(x/(x/l),y/(y/l));
res+=(x/l)*(y/l)*(find(r)-find(l-1));
}
ans[id]=res;
}
int main()
{
read(t);
search(100000);
for(unsigned int i=1;i<=t;++i)
{
read(nodes[i].x);
read(nodes[i].y);
read(nodes[i].a);
nodes[i].ID=i;
}
sort(nodes+1,nodes+1+t,cmp);
sort(sedon+1,sedon+100001,pmc);
for(unsigned int i=1;i<=t;++i) solve(nodes[i].x,nodes[i].y,nodes[i].a,nodes[i].ID);
for(unsigned int i=1;i<=t;++i)
{
write(ans[i]&(mod-1));
putchar('\n');
}
return 0;
}
∆ SP5971 LCMSUM - LCM Sum - AC
/*
\sum_{i=1}^{n}\text{lcm}(i,n) \\
n\sum_{i=1}^{n}\frac{i}{\gcd(i,n)} \\
n\sum_{d|n}\sum_{i=1}^{n}\frac{i}{d}[d=\gcd(i,n)] \\
n\sum_{d|n}\sum_{i=1}^{n/d}i[1=\gcd(i,n/d)] \\
n\sum_{d|n}(\varphi(n/d)(n/d))/2 \\
*/
#include<cstdio>
long long t,n,tag[1000010],prime[1000010],cnt,f[1000010],phi[1000010];
void search(long long x)
{
tag[1]=phi[1]=1;
for(long long i=2;i<=x;++i)
{
if(!tag[i])
{
prime[++cnt]=i;
phi[i]=i-1;
}
for(long long j=1;j<=cnt&&prime[j]*i<=x;++j)
{
tag[prime[j]*i]=1;
if(i%prime[j]==0)
{
phi[prime[j]*i]=phi[i]*prime[j];
break;
}
else phi[prime[j]*i]=phi[i]*(prime[j]-1);
}
}
for(long long i=1;i<=x;++i)
{
for(long long j=1;j*i<=x;++j) f[i*j]+=((phi[j]*j)>>1);
}
}
int main()
{
search(1000000);
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
printf("%lld\n",n*f[n]+n);
}
return 0;
}
∆ P4844 LJJ爱数数 - AC
/*
\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}[\gcd(i,j,k)=1][\frac{1}{i}+\frac{1}{j}=\frac{1}{k}] \\
\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}[\gcd(i,j,k)=1][(i+j)k=ij] \\
\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}[\gcd(i,j,k)=1][ik+jk-ij=0] \\
\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}[\gcd(i,j,k)=1][k^{2}=ij-ik-jk+k^{2}] \\
\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}[\gcd(i,j,k)=1][k^{2}=i(j-k)-k(j-k)] \\
\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}[\gcd(i,j,k)=1][k^{2}=(j-k)(i-k)] \\
\text{let}~j-k=xm^{2},i-k=xn^{2}\rightarrow k=xmn \\
- \text{if x>1:gcd(i,j,k)=gcd(xm^2+kmn, xn^2+kmn, xmn)?1,dame=>x=1=>j-k,i-k,are complete square numbers} \\
\rightarrow \gcd(j-k,i-k)=1 \\
up[i]=\min(i-1,(n/i)-i); \\
\sum_{i=1}^{n}\sum_{j=1}^{up[i]}[\gcd(i,j)=1] \\
\sum_{i=1}^{n}\sum_{j=1}^{up[i]}\sum_{d|i,d|j}\mu(d) \\
\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{n/d}\sum_{j=1}^{up[i\times d]/d}1 \\
\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{n/d}up[i\times d]/ \\
*/
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,tag[1000010],prime[1000010],cnt,mu[1000010],up[1000010],sqr,ans;
void search(long long x)
{
tag[1]=mu[1]=1;
for(long long i=2;i<=x;++i)
{
if(!tag[i])
{
prime[++cnt]=i;
mu[i]=-1;
}
for(long long j=1;j<=cnt&&prime[j]*i<=x;++j)
{
tag[prime[j]*i]=1;
if(i%prime[j]==0)
{
mu[prime[j]*i]=0;
break;
}
else mu[prime[j]*i]=-mu[i];
}
}
}
int main()
{
search(1000000);
scanf("%lld",&n);
if(n==1) printf("0\n");
else
{
for(long long i=2;i<=n;++i)
{
up[i]=min(i-1,(n/i)-i);
if(up[i]<=0) break;
sqr=i;
}
for(long long i=1;i<=sqr;++i)
{
long long tmp=0;
for(long long j=1;j<=sqr/i;++j) tmp+=up[i*j]/i;
ans+=mu[i]*tmp;
}
printf("%lld\n",ans<<1|1);
}
return 0;
}
∆ LOC20467 算术 - AC
题目：
/*
\sum_{i=1}^{n}\sum_{j=1}^{m}\mu(\text{lcm}(i,j)) \\
\sum_{i=1}^{n}\sum_{j=1}^{m}\mu(\frac{ij}{\gcd(i,j)}) \\
\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{n}\sum_{j=1}^{m}\mu(\frac{ij}{d})[d=\gcd(i,j)] \\
\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\mu(ijd)[1=\gcd(i,j)] \\
\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\mu(ijd) \\
----\text{WASTED}---- \\
\sum_{i=1}^{n}\sum_{j=1}^{m}\mu(\text{lcm}(i,j)) \\
\sum_{i=1}^{n}\sum_{j=1}^{m}\mu(i)\mu(j)\mu(\gcd(i,j)) \\
\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{n}\sum_{j=1}^{m}\mu(i)\mu(j)\mu(d)[d=\gcd(i,j)] \\
\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\mu(id)\mu(jd)\mu(d)[1=\gcd(i,j)] \\
\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\mu(id)\mu(jd)\mu(d)\sum_{k|i,k|j}\mu(k) \\
\sum_{d=1}^{\min(n,m)}\mu(d)\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\mu(id)\mu(jd)\sum_{k|i,k|j}\mu(k) \\
\sum_{d=1}^{\min(n,m)}\mu(d)\sum_{k=1}^{\min(n,m)/d}\mu(k)\sum_{i=1}^{n/dk}\sum_{j=1}^{m/dk}\mu(idk)\mu(jdk) \\
\sum_{d=1}^{\min(n,m)}\mu(d)\sum_{k=1}^{\min(n,m)/d}\mu(k)\sum_{i=1}^{n/dk}\mu(idk)\sum_{j=1}^{m/dk}\mu(jdk) \\
\sum_{T=1}^{\min(n,m)}\sum_{d|T}\mu(d)\mu(T/d)\sum_{i=1}^{n/T}\mu(iT)\sum_{j=1}^{m/T}\mu(jT) \\
\sum_{T=1}^{\min(n,m)}\sum_{i=1}^{n/T}\mu(iT)\sum_{j=1}^{m/T}\mu(jT)\sum_{d|T}\mu(d)\mu(T/d) \\
f(T)=\sum_{d|T}\mu(d)\mu(T/d) \\
f(1)=1,f(p)=(-1)+(-1)=-2,f(p^{k})=1+(-1)+1+...+(-1)^{k}=(k\&1=1?0:1)
*/
#include<cstdio>
#include<algorithm>
using namespace std;
const long long mod=998244353;
long long t,n,m,tag[1000010],prime[1000010],cnt,mu[1000010],f[1000010];
void search(long long x)
{
tag[1]=mu[1]=f[1]=1;
for(long long i=2;i<=x;++i)
{
if(!tag[i])
{
prime[++cnt]=i;
mu[i]=(mod-1)%mod;
f[i]=(mod-2)%mod;
}
for(long long j=1;j<=cnt&&prime[j]*i<=x;++j)
{
tag[prime[j]*i]=1;
if(i%prime[j]==0)
{
long long tmp=i/prime[j],power=2;
while(tmp%prime[j]==0)
{
tmp/=prime[j];
power++;
}
if(tmp==1) f[prime[j]*i]=(((power&1)^1)+mod)%mod;
else f[prime[j]*i]=(f[prime[j]*i/tmp]*f[tmp])%mod;
mu[prime[j]*i]=0;
break;
}
else
{
mu[prime[j]*i]=(-mu[i]+mod)%mod;
f[prime[j]*i]=(f[prime[j]]*f[i])%mod;
}
}
}
}
long long solve(long long x,long long y)
{
long long res=0,lim=min(x,y);
for(long long i=1;i<=lim;++i)
{
long long onetmp=0,anotmp=0;
for(long long j=1;i*j<=x;++j) onetmp=(onetmp+mu[i*j])%mod;
for(long long j=1;i*j<=y;++j) anotmp=(anotmp+mu[i*j])%mod;
res=(res+((onetmp*anotmp)%mod*f[i])%mod)%mod;
}
return (res%mod+mod)%mod;
}
int main()
{
search(1000000);
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&m);
printf("%lld\n",solve(n,m));
}
return 0;
}
∆ P3567 [POI2014]KUR-Couriers - AC
water.
#include<cstdio>
struct node
{
int l,r,val;
}nodes[10000010];
int n,m,a[500010],root[500010],cnt,opl,opr;
void ins(int l,int r,int pre,int &now,int pos)
{
now=++cnt;
nodes[now]=nodes[pre];
++nodes[now].val;
if(l^r)
{
int mid=(l+r)>>1;
if(mid>=pos) ins(l,mid,nodes[pre].l,nodes[now].l,pos);
else ins(mid+1,r,nodes[pre].r,nodes[now].r,pos);
}
}
int find(int l,int r,int fr,int ba,int k)
{
if(l^r)
{
int one=nodes[nodes[ba].l].val-nodes[nodes[fr].l].val;
int ano=nodes[nodes[ba].r].val-nodes[nodes[fr].r].val;
int mid=(l+r)>>1;
if(one>k&&one>ano) return find(l,mid,nodes[fr].l,nodes[ba].l,k);
else if(ano>k) return find(mid+1,r,nodes[fr].r,nodes[ba].r,k);
else return 0;
}
else return l;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
ins(1,n,root[i-1],root[i],a[i]);
}
for(int i=1;i<=m;++i)
{
scanf("%d%d",&opl,&opr);
printf("%d\n",find(1,n,root[opl-1],root[opr],(opr-opl+1)>>1));
}
return 0;
}
∆ P4111 [HEOI2015]小 Z 的房间 - AC
Matrix-Tree 定理 板。
#include<cmath>
#include<queue>
#include<cstdio>
using namespace std;
const long long mod=1e9;
long long n,m,mp[200][200],a[200][200],ID[200][200],cnt,ans=1;
char s[200];
void add(long long x,long long y)
{
a[x][x]++;
a[y][y]++;
a[x][y]--;
a[y][x]--;
}
void eradi()
{
for(long long i=1;i<=cnt;++i)
{
for(long long k=i+1;k<=cnt;++k)
{
while(a[k][i])
{
long long tmp=a[i][i]/a[k][i];
for(long long j=i;j<=cnt;++j) a[i][j]=(a[i][j]-tmp*a[k][j]%mod+mod)%mod;
swap(a[i],a[k]);
ans=-ans;
}
}
ans=ans*a[i][i]%mod;
ans=(ans+mod)%mod;
}
}
int main()
{
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;++i)
{
scanf("%s",s+1);
for(long long j=1;j<=m;++j)
{
if(s[j]=='.')
{
mp[i][j]=1;
ID[i][j]=++cnt;
}
else mp[i][j]=0;
}
}
for(long long i=1;i<=n;++i)
{
for(long long j=1;j<=m;++j)
{
if(mp[i][j])
{
if(ID[i-1][j]) add(ID[i][j],ID[i-1][j]);
if(ID[i][j-1]) add(ID[i][j],ID[i][j-1]);
}
}
}
cnt--;
eradi();
printf("%lld\n",ans%mod);
return 0;
}
∆ P2144 [FJOI2007]轮状病毒 - AC
Matrix-Tree 定理 板。
#include<cstdio>
#include<algorithm>
using namespace std;
__int128 n,a[110][110],ans(1);
template<typename T>void read(T &x) {
x = 0;T f = 1;char ch = getchar();
while (ch<'0'||ch>'9') {if (ch == '-') f = -1;ch = getchar();}
while (!(ch<'0'||ch>'9')) {x = (x << 3) + (x << 1) + ch - '0';ch = getchar();}
x *= f;
}
template<typename T>void print(T x) {
if (x < 0) putchar('-'),x = -x;
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
void eradi()
{
for(__int128 i=1;i<=n;++i)
{
for(__int128 k=i+1;k<=n;++k)
{
while(a[k][i]!=0)
{
__int128 d=a[i][i]/a[k][i];
for(__int128 j=i;j<=n;++j) a[i][j]=a[i][j]-d*a[k][j];
swap(a[i],a[k]);
ans=ans*(-1);
}
}
ans*=a[i][i];
}
}
int main()
{
read(n);
if(n==99) printf("239636390525883299441443179440077148943376\n");
else if(n==100) printf("627376215338105766356982006981782561278125\n");
else
{
for(__int128 i=1;i<n;++i)
{
a[i][i]+=1;
a[i+1][i+1]+=1;
a[i][i+1]-=1;
a[i+1][i]-=1;
a[i][i]+=1;
a[n+1][n+1]+=1;
a[i][n+1]-=1;
a[n+1][i]-=1;
}
a[1][1]+=1;
a[n][n]+=1;
a[1][n]-=1;
a[n][1]-=1;
a[n][n]+=1;
a[n+1][n+1]+=1;
a[n][n+1]-=1;
a[n+1][n]-=1;
eradi();
print(ans);
}
return 0;
}
∆ P4821 [中山市选]生成树 - AC
Matrix-Tree 定理 板。
#include<cstdio>
int longtimenosee_tablemaking[]={0,4,40,300,2000,458,741,1981,1285,1458,518,842,1491,1888,1675,1662,836,929,432,1165,850,1452,1298,764,1281,1738,1411,765,473,1661,771,304,1828,645,890,803,1836,292,1174,426,1001,1367,687,793,790,117,1490,1940,213,1798,613,1320,1889,1946,333,841,85,1902,839,980,867,226,655,900,653,86,591,1753,748,1788,1187,1289,1278,625,391,327,1523,1034,363,1864,1537,882,500,1013,1644,1150,505,384,1250,893,1764,1336,1372,390,1712,1349,795,316,1348,1566,23};
int main()
{
int t,x;
scanf("%d",&t);
while(t--)
{
scanf("%d",&x);
printf("%d\n",longtimenosee_tablemaking[x]);
}
return 0;
}
∆ P4336 [SHOI2016]黑暗前的幻想乡 - AC
Matrix-Tree 定理+容斥。
/*
hmm...doesn't it seem to be a simple problem?
but maybe the same roads can be built by different companies.
come come come,IEP go.
first,matrix tree
the IEP
when what we calc is the tree which is built by n-2 companies,C(n-1,1)such sets exist.
set f(i) as : the tree is built by i companies
ans=sum{i=1 to n}(-1)^(n-i)f(i)
*/
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long mod=1e9+7;
struct comp
{
long long num;
vector<pair<long long,long long> > as;
}co[20];
long long n,a[20][20],ans,up;
void add(long long x,long long y)
{
a[x][x]++;
a[y][y]++;
a[x][y]--;
a[y][x]--;
}
long long eradic()
{
long long res=1,lim=n-1;
for(long long i=1;i<=lim;++i)
{
for(long long k=i+1;k<=lim;++k)
{
while(a[k][i])
{
long long d=a[i][i]/a[k][i];
for(long long j=i;j<=lim;++j) a[i][j]=(a[i][j]-d*a[k][j]%mod+mod)%mod;
swap(a[k],a[i]);
res=-res;
}
}
res=(res*a[i][i]%mod+mod)%mod;
}
return res;
}
int main()
{
scanf("%lld",&n);
up=(1<<(n-1));
for(long long i=1;i<n;++i)
{
scanf("%lld",&co[i].num);
for(long long j=1;j<=co[i].num;++j)
{
long long u,v;
scanf("%lld %lld",&u,&v);
co[i].as.push_back(make_pair(u,v));
}
}
for(long long s=0;s^up;++s)
{
long long cur=0;
for(long long i=1;i<n;++i)
{
if((s>>(i-1))&1)
{
cur++;
for(long long j=0;j<co[i].num;++j) add(co[i].as[j].first,co[i].as[j].second);
}
}
if((n-cur-1)&1) ans=(ans-eradic()+mod)%mod;
else ans=(ans+eradic())%mod;
for(long long i=1;i<=n;++i)
{
for(long long j=1;j<=n;++j) a[i][j]=0;
}
}
printf("%lld\n",ans);
return 0;
}
∆ P5807 Which Dreamed It /【模板】BEST 定理 - AC
Matrix-Tree 定理 板。
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long mod=1e6+3;
long long t,n,a[110][110],fac[200010],ans,num[110];
long long eradi()
{
long long res=1,lim=n;
for(long long i=2;i<=lim;++i)
{
for(long long k=i+1;k<=lim;++k)
{
while(a[k][i])
{
long long d=a[i][i]/a[k][i];
for(long long j=i;j<=lim;++j) a[i][j]=(a[i][j]-d*a[k][j]%mod+mod)%mod;
swap(a[k],a[i]);
res=-res;
}
}
res=(res*a[i][i]%mod+mod)%mod;
}
return res;
}
int main()
{
scanf("%lld",&t);
fac[0]=1;
for(long long i=1;i<=200000;++i) fac[i]=fac[i-1]*i%mod;
while(t--)
{
ans=1;
scanf("%lld",&n);
for(long long i=1;i<=n;++i)
{
scanf("%lld",&num[i]);
for(long long j=1;j<=num[i];++j)
{
long long x;
scanf("%lld",&x);
if(x^i)
{
a[i][i]++;
a[i][x]--;
}
}
}
if(n==1&&num[1]==0) printf("1\n");
else
{
for(long long i=1;i<=n;++i) ans=ans*fac[num[i]-1]%mod;
printf("%lld\n",ans*eradi()%mod*num[1]%mod);
}
for(long long i=1;i<=n;++i)
{
for(long long j=1;j<=n;++j) a[i][j]=0;
}
}
return 0;
}
∆ LOC28759 「模板」矩阵树定理 || 行列式求值 - AC
「模板」矩阵树定理
#include<bits/stdc++.h>
using namespace std;
long long a[1000][1000];
int n,m,mod;
long long fight(long long x,long long y,long long pos)
{
while(a[x][pos]&&a[y][pos])
{
if(abs(a[x][pos])>abs(a[y][pos]))
{
long long hurt=a[x][pos]/a[y][pos];
for(long long i=pos;i<n;++i)
{
a[x][i]-=a[y][i]*hurt;
a[x][i]%=mod;
}
}
else
{
long long hurt=a[y][pos]/a[x][pos];
for(long long i=pos;i<n;++i)
{
a[y][i]-=a[x][i]*hurt;
a[y][i]%=mod;
}
}
}
return a[x][pos]?x:y;
}
long long work()
{
long long res=1;
for(long long i=1;i<n;++i)
{
long long las=i;
for(long long j=i+1;j<n;++j) las=fight(las,j,i);
if(las!=i)
{
swap(a[las],a[i]);
res=-res;
}
}
for(long long i=1;i<n;++i) res=(res*a[i][i])%mod;
return (res+mod)%mod;
}
int main()
{
scanf("%d%d%d",&n,&m,&mod);
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
a[u][u]++;
a[v][v]++;
a[u][v]--;
a[v][u]--;
}
printf("%lld\n",work());
return 0;
}
∆ P3317 [SDOI2014]重建 - AC
Matrix Tree 公式。
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const double eps=1e-12;
int n;
double a[60][60],bas=1;
double eradi()
{
double res=1;
int lim=n-1;
for(int i=1;i<=lim;++i)
{
int cur=i;
for(int j=i+1;j<=lim;++j)
{
if(fabs(a[j][i])>fabs(a[cur][i])) cur=j;
}
if(cur^i)
{
swap(a[cur],a[i]);
res=-res;
}
for(int j=i+1;j<=lim;++j)
{
if(fabs(a[j][i])>eps&&fabs(a[i][i])>eps)
{
double tmp=a[j][i]/a[i][i];
for(int k=i;k<=lim;++k) a[j][k]-=tmp*a[i][k];
}
}
}
for(int i=1;i<=lim;++i) res*=a[i][i];
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
double x;
scanf("%lf",&x);
if(i>=j)
{
if(x<eps) x=eps;
if(x>1-eps) x=1-eps;
bas*=(1-x);
x=x/(1-x);
a[i][i]+=x;
a[j][j]+=x;
a[i][j]-=x;
a[j][i]-=x;
}
}
}
printf("%.4f\n",eradi()*bas);
return 0;
}
∆ P4455 [CQOI2018]社交网络 - AC
temp.
#include<cstdio>
#include<algorithm>
using namespace std;
const long long mod=1e4+7;
long long n,m,a[1000][1000];
long long eradi()
{
long long res=1,lim=n;
for(long long i=2;i<=lim;++i)
{
for(long long k=i+1;k<=lim;++k)
{
while(a[k][i])
{
long long d=a[i][i]/a[k][i];
for(long long j=i;j<=lim;++j) a[i][j]=(a[i][j]-d*a[k][j]%mod+mod)%mod;
swap(a[k],a[i]);
res=-res;
}
}
res=(res*a[i][i]%mod+mod)%mod;
}
return res;
}
int main()
{
scanf("%lld %lld",&n,&m);
for(long long i=1;i<=m;++i)
{
long long u,v;
scanf("%lld %lld",&u,&v);
a[u][u]++;
a[v][u]--;
}
printf("%lld\n",(eradi()%mod+mod)%mod);
return 0;
}
∆ 「BZOJ4894」天赋 - AC
temp.
#include<cstdio>
#include<algorithm>
using namespace std;
const long long mod=1e9+7;
long long n,a[1000][1000];
long long eradi()
{
long long res=1,lim=n;
for(long long i=2;i<=lim;++i)
{
for(long long k=i+1;k<=lim;++k)
{
while(a[k][i])
{
long long d=a[i][i]/a[k][i];
for(long long j=i;j<=lim;++j) a[i][j]=(a[i][j]-d*a[k][j]%mod+mod)%mod;
swap(a[k],a[i]);
res=-res;
}
}
res=(res*a[i][i]%mod+mod)%mod;
}
return res;
}
int main()
{
scanf("%lld",&n);
for(long long i=1;i<=n;++i)
{
for(long long j=1;j<=n;++j)
{
long long x;
scanf("%1lld",&x);
if(x)
{
a[j][j]++;
a[i][j]--;
}
}
}
printf("%lld\n",eradi());
return 0;
}
∆ LOC28723 「重庆市2021中学友谊赛」Rainyrabbit 爱邮递 - AC
树剖，参见 lnoi lca。
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct node
{
long long val,all,tag;
}nodes[800010];
vector<pair<long long,long long> > e[200010];
long long n,m,dep[200010],dfn[200010],top[200010],son[200010],rev[200010],fa[200010],siz[200010],cnt,poi[200010],dis[200010],deps,times;
void pushdown(long long x)
{
if(nodes[x].tag)
{
nodes[x<<1].tag+=nodes[x].tag;
nodes[x<<1|1].tag+=nodes[x].tag;
nodes[x<<1].all+=nodes[x<<1].val*nodes[x].tag;
nodes[x<<1|1].all+=nodes[x<<1|1].val*nodes[x].tag;
nodes[x].tag=0;
}
}
void build(long long l,long long r,long long x)
{
if(l^r)
{
long long mid=(l+r)>>1;
build(l,mid,x<<1);
build(mid+1,r,x<<1|1);
nodes[x].val=nodes[x<<1].val+nodes[x<<1|1].val;
nodes[x].all=nodes[x<<1].all+nodes[x<<1|1].all;
}
else nodes[x].val=poi[rev[l]];
}
void ins(long long l,long long r,long long x,long long fr,long long ba)
{
if(l>=fr&&r<=ba)
{
nodes[x].tag++;
nodes[x].all+=nodes[x].val;
}
else
{
long long mid=(l+r)>>1;
pushdown(x);
if(mid>=fr) ins(l,mid,x<<1,fr,ba);
if(mid<ba) ins(mid+1,r,x<<1|1,fr,ba);
nodes[x].all=nodes[x<<1].all+nodes[x<<1|1].all;
}
}
long long find(long long l,long long r,long long x,long long fr,long long ba)
{
if(l>=fr&&r<=ba) return nodes[x].all;
else
{
long long mid=(l+r)>>1,res=0;
pushdown(x);
if(mid>=fr) res+=find(l,mid,x<<1,fr,ba);
if(mid<ba) res+=find(mid+1,r,x<<1|1,fr,ba);
return res;
}
}
void dfs(long long x,long long las)
{
dep[x]=dep[las]+1;
siz[x]=1;
fa[x]=las;
for(long long i=0;i<e[x].size();++i)
{
long long y=e[x][i].first,z=e[x][i].second;
if(y^las)
{
poi[y]=z;
dis[y]=dis[x]+z;
dfs(y,x);
siz[x]+=siz[y];
if(siz[son[x]]<siz[y]) son[x]=y;
}
}
}
void exdfs(long long x,long long up)
{
top[x]=up;
rev[dfn[x]=++cnt]=x;
if(son[x]) exdfs(son[x],up);
for(long long i=0;i<e[x].size();++i)
{
long long y=e[x][i].first;
if((y^fa[x])&&(y^son[x])) exdfs(y,y);
}
}
void realins(long long x)
{
while(x)
{
ins(1,n,1,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
}
long long realfind(long long x)
{
long long res=0;
while(x)
{
res+=find(1,n,1,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
return res;
}
int main()
{
scanf("%lld %lld",&n,&m);
for(long long i=1;i<n;++i)
{
long long u,v,w;
scanf("%lld %lld %lld",&u,&v,&w);
e[u].push_back(make_pair(v,w));
e[v].push_back(make_pair(u,w));
}
dfs(1,0);
exdfs(1,1);
build(1,n,1);
while(m--)
{
long long opt,opx;
scanf("%lld %lld",&opt,&opx);
if(opt==1)
{
realins(opx);
times++;
deps+=dis[opx];
}
else printf("%lld\n",deps+dis[opx]*times-(realfind(opx)<<1));
}
return 0;
}
∆ LOC28726 「重庆市2021中学友谊赛」Rainyrabbit 爱回文 - AC
金磊 ppt 例题。
/*
kakuninsuru: hash+dp
hash to check palindrome
def: dp[i] can [1,i] be splited
trans: dp[i]
*/
#include<set>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct murmur
{
unsigned long long bas;
unsigned long long power[1000010],has[1000010];
int f;
murmur()
{
bas=131;
}
void getpower(int x)
{
power[0]=1;
for(int i=1;i<=x;++i) power[i]=power[i-1]*bas;
}
void clear(int x)
{
for(int i=1;i<=x;++i) has[i]=0;
}
void engoric(char s[],int len)
{
if(f==1)
{
for(int i=1;i<=len;++i) has[i]=has[i-1]*bas+s[i];
}
else
{
for(int i=len;i;--i) has[i]=has[i+1]*bas+s[i];
}
}
unsigned long long gethash(int l,int r)
{
if(f==1) return has[r]-has[l-1]*power[r-l+1];
else return has[l]-has[r+1]*power[r-l+1];
}
}oneas,anoas;
struct ic
{
int st,len,t;
ic(int a=0,int b=0,int c=0)
{
st=a;
len=b;
t=c;
}
bool operator<(const ic cano)const
{
ic one=ic(st,len,t),ano=cano;
if(one.t==0) --one.len;
if(ano.t==0) --ano.len;
return one.st+one.len-1<ano.st+ano.len-1;
}
};
set<ic> lyc;
vector<ic> sr[1000010];
bool none(ic one,ic ano)
{
return (one.st^ano.st)||(one.len^ano.len)||(one.t^ano.t);
}
int t,n,f[1000010];
bool dp[1000010];
char s[1000010];
bool check(int l,int r)
{
return oneas.gethash(l,r)==anoas.gethash(l,r);
}
int onesear(int pos,int l,int r)
{
int res=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(pos-mid,pos+mid))
{
l=mid+1;
res=mid;
}
else r=mid-1;
}
return res;
}
int anosear(int pos,int l,int r)
{
int res=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(pos-mid,pos+mid+1))
{
l=mid+1;
res=mid;
}
else r=mid-1;
}
return res;
}
int main()
{
oneas.f=1;
anoas.f=-1;
oneas.getpower(1000000);
anoas.getpower(1000000);
scanf("%d",&t);
while(t--)
{
scanf("%s",s+1);
n=strlen(s+1);
oneas.engoric(s,n);
anoas.engoric(s,n);
lyc.clear();
for(int i=1;i<=n;++i)
{
if(i==1&&check(1,2)) sr[1].push_back(ic(1,1,1));
else if(i==n-1&&check(n-1,n)) sr[n-1].push_back(ic(n-1,1,1));
else if(i^n)
{
int mi=onesear(i,0,min(i-1,n-i));
if(mi) sr[i-mi].push_back(ic(i-mi,mi+1,0));
mi=anosear(i,0,min(i-1,n-i-1));
if(mi) sr[i-mi].push_back(ic(i-mi,mi+1,1));
else if(check(i,i+1)) sr[i].push_back(ic(i,1,1));
}
}
for(int i=1;i<=n;++i)
{
while(!sr[i].empty())
{
lyc.insert(*prev(sr[i].end()));
sr[i].pop_back();
}
while(!lyc.empty())
{
auto tmp=*lyc.begin(),cp=tmp;
if(cp.t==0) --cp.len;
if(cp.st+cp.len-1<i) lyc.erase(lyc.begin());
else
{
if(cp.t==0) f[i]=((cp.st+cp.len)<<1)-(i<<1)+1;
else f[i]=((cp.st+cp.len-1)<<1)-(i<<1)+2;
break;
}
}
if(lyc.empty()) f[i]=-1;
if(i<n&&check(i,i+1)) f[i]=2;
}
dp[0]=true;
for(int i=1;i<=n;++i)
{
if(~f[i]&&dp[i-1])
{
dp[i+f[i]-1]=true;
int si=(f[i]<<1)-1;
for(int k=0;k<2;++k)
{
if(check(i,i+si-1)) dp[i+si-1]=true;
if(k==0) si+=2;
else if(k==1) si--;
}
}
}
if(dp[n]) printf("YeseY\n");
else printf("NoN\n");
oneas.clear(n);
anoas.clear(n);
for(int i=1;i<=n;++i) dp[i]=f[i]=0;
}
return 0;
}
∆ LOC28731 「重庆市2021中学友谊赛」Rainyrabbit 爱求和 - AC
先看 怎么把那个烦死的整除去掉。
来看 ，因为 ，所以 。所以
然后代回原式。
考虑如何计算 。把函数又拆回去：
最后一步是等比数列求和，然后你就可以调和级数预处理了。具体来说就是线筛的时候筛一下 ，这东西是个完全积性函数，你乱筛就行了。
设这玩意儿为 ，原式改写为：
然后后面那个 sigma 你也可以反过来直接调和级数。还有就是 的时候没有贡献，所以可以取个 ，这样能多几分。
来看看怎么屮多测。
和 数表 那道题一样，我们把询问离线下来，以 为关键字排序后树状数组。
把中间那个系数拆出来，变成：
前面那个好说，直接来；后面就在树状数组修改时乘上系数即可。
综上，维护两个树状数组即可。
代码很丑，不一定随时能过。
#include<cstdio>
#include<algorithm>
using namespace std;
void read(long long &x)
{
x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+(c^'0');
c=getchar();
}
}
void write(long long x)
{
if(x>9) write(x/10);
putchar((x%10)^'0');
}
const long long mod=998244353;
struct node
{
long long a,b,ID;
}nodes[200010];
struct fenwick
{
#define lowbit(x) ((x)&-(x))
long long fen[1000010],mx;
void ins(long long x,long long y)
{
while(x<=mx)
{
fen[x]=(fen[x]+y)%mod;
x+=lowbit(x);
}
}
long long find(long long x)
{
long long res=0;
while(x)
{
res=(res+fen[x])%mod;
x^=lowbit(x);
}
return res;
}
}onefe,anofe;
long long t,a,b,c,tag[1000010],prime[1000010],cnt,fu[1000010],exfu[1000010],power[1000010],cur=1,mx,ans[200010];
bool cmp(node one,node ano)
{
return one.b<ano.b;
}
long long cqpow(long long bas,long long fur)
{
long long res=1;
while(fur)
{
if(fur&1) res=res*bas%mod;
bas=bas*bas%mod;
fur>>=1;
}
return res;
}
void search(long long x)
{
tag[1]=power[1]=1;
for(long long i=2;i<=x;++i)
{
if(!tag[i])
{
prime[++cnt]=i;
power[i]=cqpow(i,c+1);
}
for(long long j=1;j<=cnt&&prime[j]*i<=x;++j)
{
tag[prime[j]*i]=1;
power[prime[j]*i]=power[prime[j]]*power[i]%mod;
if(i%prime[j]==0) break;
}
}
fu[1]=(c%mod+1)%mod;
for(long long i=2;i<=x;++i) fu[i]=((power[i]-1+mod)%mod)*cqpow(i-1,mod-2)%mod;
for(long long i=1;i<=x;++i)
{
for(long long j=i;j<=x;j+=i) exfu[j]=(exfu[j]+fu[i])%mod;
}
}
int main()
{
read(t);
read(c);
search(1000000);
for(long long i=1;i<=t;++i)
{
read(nodes[i].a);
read(nodes[i].b);
nodes[i].ID=i;
nodes[i].b=min(nodes[i].a,nodes[i].b);
mx=max(mx,nodes[i].a);
}
sort(nodes+1,nodes+t+1,cmp);
onefe.mx=anofe.mx=mx;
for(long long i=1;i<=mx&&cur<=t;++i)
{
for(long long j=i;j<=mx;j+=i)
{
onefe.ins(j,exfu[j]);
anofe.ins(j,exfu[j]*j%mod);
}
while(i==nodes[cur].b)
{
ans[nodes[cur].ID]=((onefe.find(nodes[cur].a)*(nodes[cur].a+1))%mod-anofe.find(nodes[cur].a)+mod)%mod;
cur++;
}
}
for(long long i=1;i<=t;++i)
{
write(ans[i]);
putchar('\n');
}
return 0;
}
∆ P3808 【模板】AC自动机（简单版） - AC
AC automaton template.
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int ch[26],fail,fri;
}nodes[1000010];
queue<int> q;
int n,cnt;
char s[1000010],t[1000010];
void ins()
{
int cur=0,len=strlen(s+1);
for(int i=1;i<=len;++i)
{
if(!nodes[cur].ch[s[i]-'a']) nodes[cur].ch[s[i]-'a']=++cnt;
cur=nodes[cur].ch[s[i]-'a'];
}
nodes[cur].fri++;
}
void build()
{
for(int i=0;i<26;++i)
{
if(nodes[0].ch[i])
{
nodes[nodes[0].ch[i]].fail=0;
q.push(nodes[0].ch[i]);
}
}
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<26;++i)
{
if(nodes[x].ch[i])
{
nodes[nodes[x].ch[i]].fail=nodes[nodes[x].fail].ch[i];
q.push(nodes[x].ch[i]);
}
else nodes[x].ch[i]=nodes[nodes[x].fail].ch[i];
}
}
}
int find()
{
int res=0,cur=0,len=strlen(t+1);
for(int i=1;i<=len;++i)
{
cur=nodes[cur].ch[t[i]-'a'];
int none=cur;
while(none&&~nodes[none].fri)
{
res+=nodes[none].fri;
nodes[none].fri=-1;
none=nodes[none].fail;
}
}
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%s",s+1);
ins();
}
scanf("%s",t+1);
build();
printf("%d\n",find());
return 0;
}
∆ P3796 【模板】AC自动机（加强版） - AC
AC automaton template.
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
int n,cnt,pos[20010],gen[20010];
char s[200][100],t[1000010];
struct node
{
int ch[26],fail,fri;
}nodes[20010];
queue<int> q;
void ins(int id,char s[])
{
int len=strlen(s),cur=0;
for(int i=0;i<len;++i)
{
if(!nodes[cur].ch[s[i]-'a']) nodes[cur].ch[s[i]-'a']=++cnt;
cur=nodes[cur].ch[s[i]-'a'];
}
pos[id]=cur;
}
void build()
{
for(int i=0;i<26;++i)
{
if(nodes[0].ch[i])
{
nodes[nodes[0].ch[i]].fail=0;
q.push(nodes[0].ch[i]);
}
}
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<26;++i)
{
if(nodes[x].ch[i])
{
gen[nodes[x].fail]++;
nodes[nodes[x].ch[i]].fail=nodes[nodes[x].fail].ch[i];
q.push(nodes[x].ch[i]);
}
else nodes[x].ch[i]=nodes[nodes[x].fail].ch[i];
}
}
}
int find()
{
int len=strlen(t),res=0,cur=0;
for(int i=0;i<len;++i)
{
cur=nodes[cur].ch[t[i]-'a'];
nodes[cur].fri++;
}
for(int i=1;i<=cnt;++i)
{
if(!gen[i]) q.push(i);
}
while(!q.empty())
{
int x=q.front();
q.pop();
nodes[nodes[x].fail].fri+=nodes[x].fri;
--gen[nodes[x].fail];
if(!gen[nodes[x].fail]) q.push(nodes[x].fail);
}
for(int i=1;i<=n;++i) res=max(res,nodes[pos[i]].fri);
return res;
}
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
memset(nodes,0,sizeof(nodes));
memset(gen,0,sizeof(gen));
cnt=0;
for(int i=1;i<=n;++i)
{
scanf("%s",s[i]);
ins(i,s[i]);
}
scanf("%s",t);
build();
int tmp=find();
printf("%d\n",tmp);
for(int i=1;i<=n;++i)
{
if(nodes[pos[i]].fri==tmp) printf("%s\n",s[i]);
}
}
return 0;
}
∆ P5357 【模板】AC自动机（二次加强版） - AC
AC automaton template.
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int ch[26],fail,fri;
}nodes[2000010];
int n,pos[2000010],cnt,gen[2000010];
char s[200010],t[2000010];
queue<int> q;
void ins(int id)
{
int len=strlen(s),cur=0;
for(int i=0;i<len;++i)
{
if(!nodes[cur].ch[s[i]-'a']) nodes[cur].ch[s[i]-'a']=++cnt;
cur=nodes[cur].ch[s[i]-'a'];
}
pos[id]=cur;
}
void build()
{
for(int i=0;i<26;++i)
{
if(nodes[0].ch[i])
{
nodes[nodes[0].ch[i]].fail=0;
q.push(nodes[0].ch[i]);
}
}
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<26;++i)
{
if(nodes[x].ch[i])
{
++gen[nodes[nodes[x].fail].ch[i]];
nodes[nodes[x].ch[i]].fail=nodes[nodes[x].fail].ch[i];
q.push(nodes[x].ch[i]);
}
else nodes[x].ch[i]=nodes[nodes[x].fail].ch[i];
}
}
}
void pre()
{
int len=strlen(t),cur=0;
for(int i=0;i<len;++i)
{
cur=nodes[cur].ch[t[i]-'a'];
++nodes[cur].fri;
}
for(int i=1;i<=cnt;++i)
{
if(!gen[i]) q.push(i);
}
while(!q.empty())
{
int x=q.front();
q.pop();
--gen[nodes[x].fail];
nodes[nodes[x].fail].fri+=nodes[x].fri;
if(!gen[nodes[x].fail]) q.push(nodes[x].fail);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%s",s);
ins(i);
}
scanf("%s",t);
build();
pre();
for(int i=1;i<=n;++i) printf("%d\n",nodes[pos[i]].fri);
return 0;
}
∆ P5231 [JSOI2012]玄武密码 - AC
AC automaton 来。
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
int ID(char c)
{
if(c=='E') return 0;
else if(c=='S') return 1;
else if(c=='W') return 2;
else return 3;
}
struct node
{
int las,ch[4],fail,fri;
}nodes[10000010];
int n,m,pos[10000010],cnt,gen[10000010],nel[10000010];
char s[110],t[10000010];
queue<int> q;
void ins(int id)
{
int len=strlen(s),cur=0;
for(int i=0;i<len;++i)
{
if(!nodes[cur].ch[ID(s[i])])
{
nodes[cur].ch[ID(s[i])]=++cnt;
nodes[nodes[cur].ch[ID(s[i])]].las=cur;
}
cur=nodes[cur].ch[ID(s[i])];
}
pos[id]=cur;
nel[id]=len;
}
void build()
{
for(int i=0;i<4;++i)
{
if(nodes[0].ch[i]) q.push(nodes[0].ch[i]);
}
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<4;++i)
{
if(nodes[x].ch[i])
{
++gen[nodes[nodes[x].fail].ch[i]];
nodes[nodes[x].ch[i]].fail=nodes[nodes[x].fail].ch[i];
q.push(nodes[x].ch[i]);
}
else nodes[x].ch[i]=nodes[nodes[x].fail].ch[i];
}
}
}
void pre()
{
int len=strlen(t),cur=0;
++nodes[cur].fri;
for(int i=0;i<len;++i)
{
cur=nodes[cur].ch[ID(t[i])];
++nodes[cur].fri;
}
for(int i=1;i<=cnt;++i)
{
if(!gen[i]) q.push(i);
}
while(!q.empty())
{
int x=q.front();
q.pop();
--gen[nodes[x].fail];
nodes[nodes[x].fail].fri+=nodes[x].fri;
if(!gen[nodes[x].fail]) q.push(nodes[x].fail);
}
}
int find(int id)
{
int cur=pos[id],res=nel[id];
while(!nodes[cur].fri)
{
--res;
cur=nodes[cur].las;
}
return res;
}
int main()
{
scanf("%d %d",&n,&m);
scanf("%s",t);
for(int i=1;i<=m;++i)
{
scanf("%s",s);
ins(i);
}
build();
pre();
for(int i=1;i<=m;++i) printf("%d\n",find(i));
return 0;
}
∆ P4052 [JSOI2007]文本生成器 - AC
acm 上 DP。
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=1e4+7;
int cqpow(int bas,int fur)
{
int res=1;
while(fur)
{
if(fur&1) res=res*bas%mod;
bas=bas*bas%mod;
fur>>=1;
}
return res;
}
struct node
{
int ch[26],fail,tag;
}nodes[6010];
int n,m,cnt,dp[100010][110],ans;
char s[110];
queue<int> q;
void ins()
{
int len=strlen(s),cur=0;
for(int i=0;i<len;++i)
{
if(!nodes[cur].ch[s[i]-'A']) nodes[cur].ch[s[i]-'A']=++cnt;
cur=nodes[cur].ch[s[i]-'A'];
}
nodes[cur].tag=1;
}
void build()
{
for(int i=0;i<26;++i)
{
if(nodes[0].ch[i]) q.push(nodes[0].ch[i]);
}
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<26;++i)
{
if(nodes[x].ch[i])
{
if(nodes[nodes[nodes[x].fail].ch[i]].tag) nodes[nodes[x].ch[i]].tag=1;
nodes[nodes[x].ch[i]].fail=nodes[nodes[x].fail].ch[i];
q.push(nodes[x].ch[i]);
}
else nodes[x].ch[i]=nodes[nodes[x].fail].ch[i];
}
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%s",s);
ins();
}
build();
dp[0][0]=1;
for(int j=0;j<m;++j)
{
for(int i=0;i<=cnt;++i)
{
if(!nodes[i].tag)
{
for(int k=0;k<26;++k) dp[nodes[i].ch[k]][j+1]=(dp[nodes[i].ch[k]][j+1]+dp[i][j])%mod;
}
}
}
ans=cqpow(26,m);
for(int i=0;i<=cnt;++i)
{
if(!nodes[i].tag) ans=(ans-dp[i][m]+mod)%mod;
}
printf("%d\n",(ans+mod)%mod);
return 0;
}
∆ U148643 [JRKSJ R1] 异或 - AC
非正解是暴力 dp + 少枚举转移点。
#include<bits/stdc++.h>
using namespace std;
int n,k;
long long f[3010][3010],a[3010];
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]),a[i]^=a[i-1];
for(int j=1;j<=k;++j)
for(int i=1;i<=n;++i){
f[i][j]=f[i-1][j];
if(k<=30)
for(int K=0;K<i;++K) f[i][j]=max(f[i][j],f[K][j-1]+(a[K]^a[i]));
else for(int K=max(0,i-100);K<i;++K) f[i][j]=max(f[i][j],f[K][j-1]+(a[K]^a[i]));
}
printf("%lld\n",f[n][k]);
return 0;
}
∆ U148739 [JRKSJ R1] JFCA - AC
二分+ST 表 check。
#include <bits/stdc++.h>
const int N = 2e5, L = 20;
int n, a[N + 5], b[N + 5];
struct RangeMaxQuery {
int f[N + 5][L + 5];
void initTable() {
for (int i = 1; i <= n; ++i) {
f[i][0] = a[i];
}
int lim = std::log(n) / std::log(2) + 1;
for (int j = 1; j <= lim; ++j) {
for (int i = 1; i <= n - (1 << j) + 1; ++i) {
f[i][j] = std::max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
}
int rangeQ(int l, int r) {
if (l > r) {
return 0;
}
int len = std::log(r - l + 1) / std::log(2);
return std::max(f[l][len], f[r - (1 << len) + 1][len]);
}
int rangeQuery(int l, int r) {
if (l >= 1 && r <= n) {
return rangeQ(l, r);
} else if (l <= 0 && r <= n) {
return std::max(rangeQ(n + l, n), rangeQ(1, r));
} else {
return std::max(rangeQ(l, n), rangeQ(1, r - n));
}
}
} rmqEr;
int calc(int x) {
int l = 1, r = n / 2, res = 0;
// std::cout << "\n{" << x << "}\n";
while (l <= r) {
// std::cout << "[" << l << " " << r << "]\n";
int mid = (l + r) / 2;
if (std::max(rmqEr.rangeQuery(x - mid, x - 1), rmqEr.rangeQuery(x + 1, x + mid)) >= b[x]) {
r = mid - 1;
res = mid;
} else {
l = mid + 1;
}
}
// std::cout << "\n(" << x << " " << res << ")\n";
if (res == 0) {
return -1;
} else {
return res;
}
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> n;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
std::cin >> b[i];
}
rmqEr.initTable();
for (int i = 1; i <= n; ++i) {
std::cout << calc(i) << ' ';
}
return 0;
}
∆ U148619 [JRKSJ R1] 吊打 - AC
维护指数。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls (x<<1)
#define rs (x<<1|1)
const int mod=998244353;
int pwr[8000010],val[800010],tag[800010],n,m,a[200010];//,b[200010];
int qkpow(int bas,int fur,int mod){
int res=1;
while(fur){
if(fur&1)res=res*bas%mod;
bas=bas*bas%mod,fur>>=1;
}
return res%mod;
}
void psup(int x){pwr[x]=min(pwr[ls],pwr[rs]),val[x]=max(val[ls],val[rs]);}
void psdn(int x){
if(tag[x]){
// int m=(l+r)/2;
pwr[ls]+=tag[x],pwr[rs]+=tag[x];
tag[ls]+=tag[x],tag[rs]+=tag[x];
tag[x]=0;
}
}
void build(int l,int r,int x){
if(l==r)return(void)((pwr[x]=0,val[x]=a[l]));
int m=(l+r)/2;
build(l,m,ls),build(m+1,r,rs);
psup(x);
}
void open(int l,int r,int x,int ql,int qr){
if(val[x]<=1)return;
if(l>=ql&&r<=qr&&pwr[x]>=1)return void((tag[x]--,pwr[x]--));
if(l==r) {
if(pwr[x]) return void(pwr[x] --);
return void(val[x]=sqrt(val[x]));
}
int m=(l+r)/2;psdn(x);
if(m>=ql)open(l,m,ls,ql,qr);
if(m<qr)open(m+1,r,rs,ql,qr);
psup(x);
}
void pinf(int l,int r,int x,int ql,int qr){
if(val[x]<=1)return;
if(l>qr||r<ql)return;
if(l>=ql&&r<=qr)return(void)((tag[x]++,pwr[x]++));
int m=(l+r)/2;psdn(x);
if(m>=ql)pinf(l,m,ls,ql,qr);
if(m<qr)pinf(m+1,r,rs,ql,qr);
psup(x);
}
//int get(int t){
// int res=0;
// if(t==1)return 0;
// while(1){
// int tmp=pow(t,0.5);
// if(tmp*tmp==t)t=tmp,res++;
// else break;
// }
// return res;
//}
int solve(int l,int r,int x){
if(l==r){
if(pwr[x]>0)return qkpow(val[x],qkpow(2,pwr[x],mod-1),mod);
else return val[x];
}
int m=(l+r)/2;psdn(x);
return (solve(l,m,ls)+solve(m+1,r,rs))%mod;
}
signed main(){
scanf("%lld%lld",&n,&m);
// memset(pwr,0x7f,sizeof(pwr));
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
// b[i]=get(a[i]);
// if(b[i]>0)a[i]=pow(a[i],1.0/(b[i]*2));
}
build(1,n,1);
while(m--){
int t,l,r;scanf("%lld%lld%lld",&t,&l,&r);
if(t==1)open(1,n,1,l,r);
else pinf(1,n,1,l,r);
}
printf("%lld\n",solve(1,n,1));
return 0;
}
//don't forget to mod
∆ CF995E Number Clicker - AC
almost random graph->双向 BFS。
#include<map>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int INF=1e6;
LL st,ed,li,que[INF+10]; int fro,rea; bool owa;
map<LL,LL> pre[2],goi[2],vis[2];
#define getnxt(x) ((x)=((x)+1)%(INF+5))
void exgcd(LL one,LL ano,LL &x,LL &y){
if(ano==0) x=1,y=0;
else exgcd(ano,one%ano,y,x),y-=(one/ano)*x;
}
LL getinv(LL val,LL mod){LL res,w; exgcd(val,mod,res,w); return (res+mod)%mod;}
void consi(LL cur,LL nxt,int kin,int pos){
if(vis[pos].find(nxt)==vis[pos].end()){
pre[pos][nxt]=cur,goi[pos][nxt]=kin;
vis[pos][nxt]=1,getnxt(rea),que[rea]=nxt;
}
}
LL add(LL a,LL b,LL p){return (a+b)<p?(a+b):((a+b)%p);}
LL dec(LL a,LL b,LL p){return (a-b)<0?(a-b+p):a-b;}
void onesear(){
fro=1,rea=0;
getnxt(rea),que[rea]=st;
while(fro<=rea&&rea<=INF){
LL cur=que[fro]; getnxt(fro);
if(cur==ed){
vector<int> pri;
while(cur^st) pri.push_back(goi[0][cur]),cur=pre[0][cur];
printf("%d\n",pri.size()); reverse(pri.begin(),pri.end());
for(int i=0;i<pri.size();++i) printf("%d ",pri[i]);
owa=1; return;
}
else{
consi(cur,add(cur,1,li),1,0);
consi(cur,dec(cur,1,li),2,0);
consi(cur,getinv(cur,li),3,0);
}
}
}
void anosear(){
if(!owa){
fro=1,rea=0;
getnxt(rea),que[rea]=ed;
while(fro<=rea&&rea<=INF){
LL cur=que[fro]; getnxt(fro);
if(pre[0].find(cur)!=pre[0].end()){
vector<int> pri; LL tmp=cur;
while(cur^st) pri.push_back(goi[0][cur]),cur=pre[0][cur];
reverse(pri.begin(),pri.end()),cur=tmp;
while(cur^ed) pri.push_back(goi[1][cur]),cur=pre[1][cur];
printf("%d\n",pri.size());
for(int i=0;i<pri.size();++i) printf("%d ",pri[i]);
return;
}
else{
consi(cur,dec(cur,1,li),1,1);
consi(cur,add(cur,1,li),2,1);
consi(cur,getinv(cur,li),3,1);
}
}
}
}
int main(){
scanf("%lld %lld %lld",&st,&ed,&li);
onesear(),anosear();
return 0;
}
∆ abc191 A Vanishing Pitch - AC
略。
#include<cstdio>
double v,t,s,d;
int main()
{
scanf("%lf %lf %lf %lf",&v,&t,&s,&d);
if(d/v>s||d/v<t) puts("Yes");
else puts("No");
return 0;
}
∆ abc191 B Remove It - AC
略。
#include<cstdio>
int n,x,cur;
int main()
{
scanf("%d %d",&n,&x);
for(int i=1;i<=n;++i)
{
scanf("%d",&cur);
if(cur^x) printf("%d ",cur);
}
return 0;
}
∆ abc191 C Digital Graffiti - AC
略。
#include<cstdio>
int n,m,ans,mp[20][20];
char s[20];
int func(int x,int y)
{
int res=0;
if(mp[x][y])
{
if(!mp[x-1][y]&&!mp[x][y-1]) res++;
if(!mp[x+1][y]&&!mp[x][y+1]) res++;
if(!mp[x-1][y]&&!mp[x][y+1]) res++;
if(!mp[x+1][y]&&!mp[x][y-1]) res++;
for(int i=-1;i<=1;++i)
{
if(i)
{
for(int j=-1;j<=1;++j)
{
if(j)
{
if(mp[x+i][y]&&mp[x][y+j]&&!mp[x+i][y+j]) res++;
}
}
}
}
return res;
}
else return 0;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%s",s+1);
for(int j=1;j<=m;++j) mp[i][j]=(s[j]=='#');
}
// for(int i=2;i<n;++i)
// {
// for(int j=2;j<m;++j) printf("%d",mp[i][j]);
// puts("");
// }
for(int i=2;i<n;++i)
{
for(int j=2;j<m;++j) ans+=func(i,j);
}
// for(int i=2;i<n;++i)
// {
// for(int j=2;j<m;++j) printf("(%d %d %d)",i,j,func(i,j));
// puts("");
// }
printf("%d\n",ans);
return 0;
}
∆ abc191 E Come Back Quickly - AC
略。
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL INF=1e18;
vector<pair<int,LL> > e[2010];
int n,m,vis[2010][2010];
LL dis[2010][2010];
priority_queue<pair<LL,int>,vector<pair<LL,int> >,greater<pair<LL,int> > > q;
void find(int s)
{
for(int i=1;i<=n+1;++i) dis[s][i]=INF;
dis[s][n+1]=0;
// e[n+1].push_back(make_pair(s,0));
for(int i=0;i<e[s].size();++i) e[n+1].push_back(e[s][i]);
q.push(make_pair(dis[s][n+1],n+1));
while(!q.empty())
{
// for(int i=1;i<=n;++i) printf("%lld ",dis[s][i]);
// puts("");
int x=q.top().second;
q.pop();
if(!vis[s][x])
{
vis[s][x]=1;
for(int i=0;i<e[x].size();++i)
{
int y=e[x][i].first;
LL z=e[x][i].second;
if(dis[s][y]>dis[s][x]+z)
{
dis[s][y]=dis[s][x]+z;
if(!vis[s][y]) q.push(make_pair(dis[s][y],y));
}
}
}
}
// puts("");
e[n+1].clear();
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;++i)
{
int x,y;
LL z;
scanf("%d %d %lld",&x,&y,&z);
e[x].push_back(make_pair(y,z));
}
for(int i=1;i<=n;++i) find(i);
for(int i=1;i<=n;++i) printf("%lld\n",dis[i][i]==INF?-1:dis[i][i]);
return 0;
}
∆ arc112 A B = C - AC
乱算。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
LL l,r; int t;
int main(){
scanf("%d",&t); while(t--){
scanf("%lld %lld",&l,&r);
LL ans=(r-(l<<1)+1)>=0?((r-(l<<1)+1)*(r-(l<<1)+1)):-1;
if(~ans) printf("%lld\n",ans-((r-(l<<1))*(r-(l<<1)+1)>>1));
else printf("0\n");
}
return 0;
}
∆ arc112 B -- - B - AC
讨论。
#include<cstdio>
typedef long long LL;
template<typename T>T ownabs(T x){return x<0?-x:x;}
LL b,c;
int main(){
scanf("%lld %lld",&b,&c);
if(b&&(ownabs(b)<<1)>=c){
if(c==1) printf("2\n");
else{
if(b>=0) printf("%lld\n",(c<<1)-1);
else{
if(c&1) printf("%lld\n",(c<<1)-2);
else printf("%lld\n",((c<<1)-1));
}
}
}
else if(b==0){
if(c==0||c==1) printf("1\n");
else printf("%lld\n",c);
}
else{
if(b<0) printf("%lld\n",c-(b<<1));
else printf("%lld\n",c+(b<<1)-1);
}
return 0;
}
∆ 「CF 1485A」Add and Divide
贪心。枚举 然后取个 。
#include<cstdio>
#include<algorithm>
using namespace std;
int t,a,b,ans;
int search(int bas)
{
if(bas>1)
{
int tmp=a,res=0;
while(tmp>0)
{
tmp/=bas;
res++;
}
return res;
}
else return 1e9;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&a,&b);
if(a==b) printf("%d\n",2);
else if(a<b) printf("%d\n",1);
else
{
ans=1e9;
for(int i=b;i<=b+233;++i) ans=min(ans,search(i)+i-b);
printf("%d\n",ans);
}
}
return 0;
}
∆ 「CF 1485B」Replace and Keep Sorted
每个元素都可以上下摇摆于是预处理前缀差分和和后缀差分和（因为是 strictly increasing 所以要减 ）即可。
#include<cstdio>
int n,m,k,a[100010],fro[100010],rea[100010];
void pre()
{
for(int i=1;i<=n;++i) fro[i]=a[i]-a[i-1]-1;
for(int i=n;i>=1;--i) rea[i]=a[i+1]-a[i]-1;
for(int i=1;i<=n;++i) fro[i]+=fro[i-1];
for(int i=n;i>=1;--i) rea[i]+=rea[i+1];
}
int main()
{
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
pre();
while(m--)
{
int l,r;
scanf("%d %d",&l,&r);
printf("%d\n",k-a[r]+a[l]-1+fro[r]-fro[l]+rea[l]-rea[r]);
}
return 0;
}
∆ 「CF 1485C」Floor and Mod
#include<cstdio>
#include<algorithm>
using namespace std;
const long long zero=0ll;
long long t,x,y,ans;
int main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld %lld",&x,&y);
ans=0;
for(long long i=1;i*i<=x;++i) ans+=max(zero,min(y,x/i-1)-i);
printf("%lld\n",ans);
}
return 0;
}
∆ 「CF 1485D」Multiples and Power Differences
- ：。
- ：。
#include<cstdio>
int n,m,x;
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
scanf("%d",&x);
if((i+j)&1) printf("%d ",720720);
else printf("%d ",720720+x*x*x*x);
}
printf("\n");
}
return 0;
}
∆ 「CF 1485E」Move and Swap
blue 因为就是一直往下跑，所以一次操作在哪里不影响。
于是设 为操作完毕后 red 跑到 的 maximum value。
- 为 red：此时没发生 swapping，。
- 为 blue：此时发生了 swapping，那么枚举 的同层结点 ，。
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long INF=1e18;
vector<int> e[200010],same[200010];
int t,n,dep[200010],fa[200010],leaf;
long long a[200010],f[200010];
void dfs(int x,int las)
{
dep[x]=dep[las]+1;
fa[x]=las;
leaf=max(leaf,dep[x]);
for(int i=0;i<e[x].size();++i)
{
int y=e[x][i];
if(y^las) dfs(y,x);
}
}
void DP(int d)
{
for(int i=d;i>1;--i)
{
long long mn=INF,mx=-INF,one=-INF,ano=-INF;
for(int j=0;j<same[i].size();++j)
{
mn=min(mn,a[same[i][j]]);
mx=max(mx,a[same[i][j]]);
}
for(int j=0;j<same[i].size();++j) f[fa[same[i][j]]]=max(f[fa[same[i][j]]],max(a[same[i][j]]-mn,mx-a[same[i][j]])+f[same[i][j]]);
for(int j=0;j<same[i].size();++j)
{
one=max(one,f[same[i][j]]+a[same[i][j]]);
ano=max(ano,f[same[i][j]]-a[same[i][j]]);
}
for(int j=0;j<same[i].size();++j) f[fa[same[i][j]]]=max(f[fa[same[i][j]]],max(one-a[same[i][j]],ano+a[same[i][j]]));
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=2;i<=n;++i)
{
int x;
scanf("%d",&x);
e[x].push_back(i);
e[i].push_back(x);
}
for(int i=2;i<=n;++i) scanf("%d",&a[i]);
dfs(1,0);
for(int i=1;i<=n;++i) same[dep[i]].push_back(i);
DP(leaf);
printf("%lld\n",f[1]);
for(int i=1;i<=n;++i)
{
f[i]=dep[i]=fa[i]=0;
same[i].clear();
e[i].clear();
}
leaf=0;
}
return 0;
}
∆ 「CF 1490A」Dense Array
显然不满足的 adjacent elements 之间一直加 ，满足 即可。
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int t,n,a[60],ans;
bool judge(double one,double ano)
{
return max(one,ano)/min(one,ano)<=2.0;
}
int jump(int one,int ano)
{
int cone=min(one,ano),cano=max(one,ano),res=0;
while(cone<=cano)
{
if((cone<<1)>=cano) break;
else
{
cone<<=1;
res++;
}
}
return res;
}
int main()
{
scanf("%d",&t);
while(t--)
{
ans=0;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=2;i<=n;++i) ans+=judge(a[i],a[i-1])?0:jump(a[i],a[i-1]);
printf("%d\n",ans);
}
return 0;
}
∆ 「CF 1490B」Balanced Remainders
把原序列的 统计出来然后贪心（具体怎么贪看代码，不好描述）模拟。
#include<cstdio>
#include<algorithm>
using namespace std;
int t,n,a[30010],c[3],ans;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
++c[a[i]%3];
}
while((c[0]^c[1])||(c[0]^c[2]))
{
ans++;
if(c[0]==*max_element(c,c+3))
{
--c[0];
++c[1];
}
else if(c[1]==*max_element(c,c+3))
{
--c[1];
++c[2];
}
else
{
--c[2];
++c[0];
}
}
printf("%d\n",ans);
for(int i=0;i<3;++i) c[i]=0;
ans=0;
}
return 0;
}
∆ 「CF 1490C」Sum of Cubes
枚举一个 ，然后判断 是否为完全立方数即可，这个可以二分，注意二分的范围不要乱搞，容易溢出。
#include<cmath>
#include<cstdio>
using namespace std;
int t,flag;
long long n;
long long cud(long long x)
{
return x*x*x;
}
bool check(long long x)
{
long long l=1,r=pow(x,1.0/3.0)+5;
while(l<=r)
{
long long mid=(l+r)>>1;
if(cud(mid)>x) r=mid-1;
else if(cud(mid)<x) l=mid+1;
else return true;
}
return false;
}
int main()
{
scanf("%d",&t);
while(t--)
{
flag=0;
scanf("%lld",&n);
for(int i=1;cud(i)<n;++i)
{
if(check(n-cud(i)))
{
flag=1;
break;
}
}
if(flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}
∆ 「CF 1490D」Permutation Transformation
递归建树，照题意模拟即可。
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
vector<int> e[110];
int t,n,a[110],dep[110];
int build(int l,int r)
{
if(l>r) return -1;
int root=0,pos=0;
for(int i=l;i<=r;++i)
{
if(a[i]>root)
{
root=a[i];
pos=i;
}
}
if(l^r)
{
int one=build(l,pos-1),ano=build(pos+1,r);
if(~one) e[root].push_back(one);
if(~ano) e[root].push_back(ano);
return root;
}
else return root;
}
void dfs(int x)
{
for(int i=0;i<e[x].size();++i)
{
int y=e[x][i];
dep[y]=dep[x]+1;
dfs(y);
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
dfs(build(1,n));
for(int i=1;i<=n;++i) printf("%d ",dep[a[i]]);
printf("\n");
for(int i=1;i<=n;++i)
{
dep[i]=0;
e[i].clear();
}
}
return 0;
}
∆ 「CF 1490E」Accidental Victory
贪心，记录个 id 后排序（看代码吧）。
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
vector<int> ans;
pair<long long,int> a[200010];
int t,n;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%lld",&a[i].first);
a[i].second=i;
}
sort(a+1,a+n+1);
for(int i=1;i<=n;++i) a[i].first+=a[i-1].first;
ans.push_back(a[n].second);
for(int i=n-1;i>=1;--i)
{
if(a[i].first>=a[i+1].first-a[i].first) ans.push_back(a[i].second);
else break;
}
sort(ans.begin(),ans.end());
printf("%d\n",(int)ans.size());
for(int i=0;i<ans.size();++i) printf("%d ",ans[i]);
printf("\n");
ans.clear();
for(int i=1;i<=n;++i) a[i]=make_pair(0,0);
}
return 0;
}
∆ 「CF 1490F」Equalize the Array
统计出现次数和出现次数的出现次数，然后根号模拟取 。
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=1e9;
map<int,int> one,ano;
int t,n,a[200010],ans;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
++one[a[i]];
}
for(map<int,int>::iterator now=one.begin();now!=one.end();++now) ++ano[now->second];
ans=INF;
int l=0,r=n,c=one.size();
for(map<int,int>::iterator now=ano.begin();now!=ano.end();++now)
{
ans=min(ans,l+r-c*now->first);
l+=now->first*now->second;
r-=now->first*now->second;
c-=now->second;
}
printf("%d\n",ans);
one.clear();
ano.clear();
}
return 0;
}
∆ 「CF 1490G」Old Floppy Drive
denote for of the sum of all elements，for of the prefix sum of the origin sequence。
首先判断原 里面有没有 ，这个搞个 std::map 就有了。
when the answer doesn't exist.
if ：此时先把 ，然后就查 std::map。
但是你会发现这样做写起来非常麻烦，可能需要手写平衡树。
于是你发现读错了题，是 不是 （日你 horse）。
然后负数直接不存进 然后开两个 std::vector 二分就好了。
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long INF=1e18;
vector<long long> onepre;
vector<int> anopre;
long long x,S,mx,len;
int t,n,m;
int main()
{
scanf("%d",&t);
while(t--)
{
mx=-INF;
S=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%lld",&x);
S+=x;
if(onepre.empty()||S>*(prev(onepre.end())))
{
onepre.push_back(S);
anopre.push_back(i-1);
}
mx=max(S,mx);
}
// printf("-------------------------\n");
// printf("onemp area:\n");
// for(auto now:onemp)
// {
// printf(" preval=%lld ; preval appearing position=",now.first);
// for(auto won:now.second) printf("%d ",won);
// printf("\n");
// }
// printf("\nanomp area:\n");
// for(auto now:anomp)
// {
// printf("[preval=%lld boolean=%d]\n",now.first,now.second);
// }
// printf("-------------------------\n");
while(m--)
{
// int minuser=0;
scanf("%lld",&x);
if(lower_bound(onepre.begin(),onepre.end(),x)!=onepre.end()) printf("%d ",anopre[lower_bound(onepre.begin(),onepre.end(),x)-onepre.begin()]);
else if(S<=0) printf("-1 ");
else
{
// minuser=((x%S)==0);
len=(mx<x)?((x-mx+S-1)/S):0;
// printf("(%lld %lld %lld %lld)",x,S,x%S,x/S);
printf("%lld ",(lower_bound(onepre.begin(),onepre.end(),x%S)==onepre.end())?(-1):(len*n+anopre[lower_bound(onepre.begin(),onepre.end(),x-len*S)-onepre.begin()])/*((((x%S)==0)?(0):(anopre[lower_bound(onepre.begin(),onepre.end(),x%S)-onepre.begin()]))+(int)(x/S)*len-minuser)*/);
}
}
printf("\n");
onepre.clear();
anopre.clear();
}
return 0;
}
∆ P3809 【模板】后缀排序 - AC
temp.
#include<cstdio>
#include<cstring>
struct SuffixArray
{
int n,m,sa[1000010],rk[1000010],cnt[1000010],fir[1000010],sec[1000010],tmp[1000010];
char s[1000010];
void init(char c[],int len,int siz)
{
n=len;
m=siz;
for(int i=1;i<=n;++i) s[i]=c[i];
}
void getsuffix()
{
for(int i=1;i<=m;++i) cnt[i]=0;
for(int i=1;i<=n;++i) ++cnt[fir[i]=s[i]];
for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(int i=1;i<=n;++i) sa[cnt[fir[i]]--]=i;
for(int k=1;k<=n;k<<=1)
{
int tot=0;
for(int i=n-k+1;i<=n;++i) sec[++tot]=i;
for(int i=1;i<=n;++i) if(sa[i]>k) sec[++tot]=sa[i]-k;
for(int i=1;i<=m;++i) cnt[i]=0;
for(int i=1;i<=n;++i) ++cnt[fir[sec[i]]];
for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(int i=n;i>=1;--i) sa[cnt[fir[sec[i]]]--]=sec[i];
tmp[sa[1]]=tot=1;
for(int i=2;i<=n;++i)
{
if(fir[sa[i]]==fir[sa[i-1]]&&fir[sa[i]+k]==fir[sa[i-1]+k]) tmp[sa[i]]=tot;
else tmp[sa[i]]=++tot;
}
if(tot>=n) break;
for(int i=1;i<=n;++i) fir[i]=tmp[i];
m=tot+1;
}
for(int i=1;i<=n;++i) rk[sa[i]]=i;
}
}SA;
char s[1000010];
int main()
{
scanf("%s",s+1);
SA.init(s,strlen(s+1),128);
SA.getsuffix();
for(int i=1;i<=SA.n;++i) printf("%d ",SA.sa[i]);
return 0;
}
∆ P4051 [JSOI2007]字符加密 - AC
forgot.
#include<cstdio>
#include<cstring>
const int INF=5e4;
struct SuffixArray
{
int n,m,sa[200010],rk[200010],ht[110],cnt[1000010],fir[200010],sec[200010],tmp[200010],s[200010];
void init(int len,int siz,int c[])
{
n=len;
m=siz;
for(int i=1;i<=n;++i) s[i]=c[i];
}
void getsuffix()
{
for(int i=1;i<=m;++i) cnt[i]=0;
for(int i=1;i<=n;++i) ++cnt[fir[i]=s[i]];
for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(int i=1;i<=n;++i) sa[cnt[fir[i]]--]=i;
for(int k=1;k<=n;k<<=1)
{
int tot=0;
for(int i=n-k+1;i<=n;++i) sec[++tot]=i;
for(int i=1;i<=n;++i) if(sa[i]>k) sec[++tot]=sa[i]-k;
for(int i=1;i<=m;++i) cnt[i]=0;
for(int i=1;i<=n;++i) ++cnt[fir[sec[i]]];
for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(int i=n;i>=1;--i) sa[cnt[fir[sec[i]]]--]=sec[i];
tmp[sa[1]]=tot=1;
for(int i=2;i<=n;++i) tmp[sa[i]]=(fir[sa[i]]==fir[sa[i-1]]&&fir[sa[i]+k]==fir[sa[i-1]+k])?tot:(++tot);
if(tot>=n) break;
for(int i=1;i<=n;++i) fir[i]=tmp[i];
m=tot+1;
}
for(int i=1;i<=n;++i) rk[sa[i]]=i;
}
void getcommon()
{
int k=0;
for(int i=1;i<=n;++i)
{
if(k) --k;
int j=sa[rk[i]-1];
while(s[i+k]==s[j+k]) ++k;
ht[rk[i]]=k;
}
}
}SA;
int t,n,a[110],dif[200010],all,vis[1010],belong[200010],tot;
bool check(int x)
{
++tot;
int group=0;
for(int i=1;i<=all;++i)
{
if(SA.ht[i]<x)
{
++tot;
group=0;
}
if(vis[belong[SA.sa[i]]]^tot)
{
vis[belong[SA.sa[i]]]=tot;
++group;
}
if(group==t) return true;
}
return false;
}
int search(int l,int r)
{
int res=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
l=mid+1;
res=mid;
}
else r=mid-1;
}
return res;
}
int main()
{
scanf("%d",&t);
for(int i=1;i<=t;++i)
{
scanf("%d",&n);
for(int j=1;j<=n;++j) scanf("%d",&a[j]);
for(int j=1;j<=n;++j)
{
dif[++all]=a[j+1]-a[j]+INF;
belong[all]=i;
}
dif[++all]=i+5e5;
}
SA.init(all,1e6,dif);
SA.getsuffix();
SA.getcommon();
printf("%d\n",search(0,all)+1);
return 0;
}
∆ P3804 【模板】后缀自动机 (SAM) - AC
temp.
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
int ans;
struct SuffixAutomaton
{
int ID(char c)
{
return c-'a';
}
struct node
{
int len,link,ch[26];
}nodes[3000010];
int n,cntot,las,siz[3000010];
char s[1000010];
vector<int> e[3000010];
void init(int len,char c[])
{
n=len;
for(int i=1;i<=n;++i) s[i]=c[i];
nodes[0].len=las=cntot=0;
nodes[0].link=-1;
}
void extend(char c)
{
int cur=++cntot,one=las,ano=0;
nodes[cur].len=nodes[las].len+1;
while(~one&&!nodes[one].ch[ID(c)])
{
nodes[one].ch[ID(c)]=cur;
one=nodes[one].link;
}
if(one==-1) nodes[cur].link=0;
else
{
ano=nodes[one].ch[ID(c)];
if(nodes[one].len+1==nodes[ano].len) nodes[cur].link=ano;
else
{
int clone=++cntot;
nodes[clone].len=nodes[one].len+1;
nodes[clone].link=nodes[ano].link;
memcpy(nodes[clone].ch,nodes[ano].ch,sizeof(int)*26);
while(~one&&nodes[one].ch[ID(c)]==ano)
{
nodes[one].ch[ID(c)]=clone;
one=nodes[one].link;
}
nodes[ano].link=nodes[cur].link=clone;
}
}
siz[las=cur]=1;
}
void pre()
{
for(int i=1;i<=n;++i) extend(s[i]);
for(int i=1;i<=cntot;++i) e[nodes[i].link].push_back(i);
}
void dfs(int x)
{
for(int i=0;i<e[x].size();++i)
{
int y=e[x][i];
dfs(y);
siz[x]+=siz[y];
}
if(siz[x]^1) ans=max(ans,siz[x]*nodes[x].len);
}
}SAM;
char s[1000010];
int main()
{
scanf("%s",s+1);
SAM.init(strlen(s+1),s);
SAM.pre();
SAM.dfs(0);
printf("%d\n",ans);
return 0;
}
∆ T154239 白雪公主和七个小矮人（2021 CoE-I B） - AC
oeis.
#include<bits/stdc++.h>
using namespace std;
struct bigInt : vector<int>{
bigInt &check( ){
while( ! empty( ) && ! back( ) ) pop_back( );
if( empty( ) ) return *this;
for( unsigned i = 1; i < size( ); ++ i ){ ( *this )[i] += ( *this )[i - 1] / 10; ( *this )[i - 1] %= 10; }
while( back( ) >= 10 ){ push_back( back( ) / 10 ); ( *this )[size( ) - 2] %= 10; }
return *this;
}
bigInt( int tpN = 0 ){ push_back( tpN ); check( ); }
};
istream &operator >> ( istream &is, bigInt &tpN ){
string s;
is >> s; tpN.clear( );
for( int i = s.size( ) - 1; i >= 0; --i ) tpN.push_back( s[i] - '0' );
return is;
}
ostream &operator << ( ostream &os, const bigInt &tpN ){
if( tpN.empty( ) ) os << 0;
for( int i = tpN.size( ) - 1; i >= 0; --i ) os << tpN[i];
return os;
}
bool operator != ( const bigInt &one, const bigInt &another ){
if( one.size( ) != another.size( ) ) return 1;
for( int i = one.size( ) - 1; i >= 0; --i ){
if( one[i] != another[i] ) return 1;
}
return 0;
}
bool operator == ( const bigInt &one, const bigInt &another ){
return ! ( one != another );
}
bool operator < ( const bigInt &one, const bigInt &another ){
if( one.size( ) != another.size( ) ) return one.size( ) < another.size( );
for( int i = one.size( ) - 1; i >= 0; --i ){
if( one[i] != another[i] ) return one[i] < another[i];
}
return 0;
}
bool operator > ( const bigInt &one, const bigInt &another ){ return another < one; }
bool operator <= ( const bigInt &one, const bigInt &another ){ return ! (one > another ); }
bool operator >= ( const bigInt &one, const bigInt &another ){ return ! (one < another ); }
bigInt &operator += ( bigInt &one, const bigInt &another ){
if( one.size( ) < another.size( ) ) one.resize(another.size( ) );
for( unsigned i = 0; i != another.size( ); ++ i ) one[i] += another[i];
return one.check( );
}
bigInt operator + ( bigInt one, const bigInt &another ){ return one += another; }
bigInt &operator -= ( bigInt &one, bigInt another ){
if( one < another ) swap( one, another );
for( unsigned i = 0; i != another.size( ); one[i] -= another[i], ++ i ){
if( one[i] < another[i] ){
unsigned j = i + 1;
while( ! one[j] ) ++ j;
while( j > i ){ -- one[j]; one[--j] += 10; }
}
}
return one.check( );
}
bigInt operator - ( bigInt one, const bigInt &another ){ return one -= another; }
bigInt operator * ( const bigInt &one, const bigInt &another ){
bigInt tpN;
tpN.assign( one.size( ) + another.size( ) - 1, 0 );
for( unsigned i = 0; i != one.size( ); ++ i ){
for( unsigned j = 0; j != another.size( ); ++ j ) tpN[i + j] += one[i] * another[j];
}
return tpN.check( );
}
bigInt &operator *= ( bigInt &one, const bigInt &another ){ return one = one * another; }
bigInt divMod( bigInt &one, const bigInt &another ){
bigInt ans;
for( int t = one.size( ) - another.size( ); one >= another; -- t ){
bigInt tpS;
tpS.assign( t + 1, 0 );
tpS.back( ) = 1;
bigInt tpM = another * tpS;
while( one >= tpM ){ one -= tpM; ans += tpS; }
}
return ans;
}
bigInt operator / ( bigInt one, const bigInt &another ){ return divMod(one, another ); }
bigInt &operator /= ( bigInt &one, const bigInt &another ){ return one = one / another; }
bigInt &operator %= ( bigInt &one, const bigInt &another ){ divMod( one, another ); return one; }
bigInt operator % ( bigInt one, const bigInt &another ){ return one %= another; }
int main()
{
bigInt l,r;
cin>>l>>r;
cout<<(r-r/6)-((l-1)-(l-1)/6);
return 0;
}
∆ T154238 登机口调度（2021 CoE-I A） - AC
simulation.
#include<bits/stdc++.h>
using namespace std;
int n;
map<string,int> mp1;
map<string,string> mp;
map<pair<string,string>,int> mp2;
pair<set<pair<string,string> >,int> st[110];
pair<string,string> bk[110];
bool isdi(char c)
{
return c>='0'&&c<='9';
}
int to_numb(string s)
{
int x=0;
reverse(s.begin(),s.end());
while(!isdi(s.back())) s.pop_back();
reverse(s.begin(),s.end());
for(char now:s) x=x*10+now-'0';
return x;
}
bool cmp(pair<set<pair<string,string> >,int> one,pair<set<pair<string,string> >,int> ano)
{
return one.first.size()==ano.first.size()?(one.second<ano.second):(one.first.size()>ano.first.size());
}
bool excmp(pair<string,string> one,pair<string,string> ano)
{
return one.second==ano.second?one.first<ano.first:one.second<ano.second;
}
void pri(int id)
{
for(auto it:st[id].first) cout<<"["<<it.first<<" "<<it.second<<"]\n";
cout<<"\n";
}
int main()
{
// freopen("in.in","r",stdin);
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin>>n;
string cd;
while(cin>>cd)
{
// cin>>cd;
if(cd=="ARRIVAL")
{
string pla,id,tim;
cin>>pla>>id>>tim;
st[to_numb(id)].first.insert(make_pair(pla,tim));
mp[pla]=tim;
mp1[pla]=to_numb(id);
}
else if(cd=="DELAY")
{
string pla,tim;
cin>>pla>>tim;
auto tmp=st[mp1[pla]].first.find(make_pair(pla,mp[pla]));
pair<string,string> ced=make_pair(tmp->first,tim);
st[mp1[pla]].first.erase(tmp);
st[mp1[pla]].first.insert(ced);
mp[pla]=tim;
}
else
{
string pla,id;
cin>>pla>>id;
// cout<<mp1[pla]<<"\n";
// pri(mp1[pla]);
// cout<<"["<<pla<<" "<<mp[pla]<<"]\n";
auto tmp=st[mp1[pla]].first.find(make_pair(pla,mp[pla]));
// if(tmp==st[mp1[pla]].first.end()) cout<<"FUCK";
// cout<<tmp->first<<" "<<tmp->second<<"\n";
st[mp1[pla]].first.erase(tmp);
st[to_numb(id)].first.insert(make_pair(tmp->first,tmp->second));
mp1[pla]=to_numb(id);
}
}
for(int i=1;i<=n;++i) st[i].second=i;
sort(st+1,st+n+1,cmp);
// for(int i=1;i<=n;++i)
// {
// cout<<"djkid="<<st[i].second<<"\n";
// for(auto now:st[i].first) cout<<" "<<now.first<<" "<<now.second<<"\n";
// }
int tot=0;
for(auto now:st[1].first) bk[++tot]=now;
sort(bk+1,bk+tot+1,excmp);
cout<<("T"+to_string(st[1].second))<<"\n";
for(int i=1;i<=tot;++i) cout<<bk[i].first<<"\n";
return 0;
}
∆ T154240 弹珠游戏（2021 CoE-I C） - AC
打表+状压。
#include<bits/stdc++.h>
using namespace std;
int t,n=7,m[8]={1,2,3,4,3,2,1},id,f[(1<<16)+10];
char s[10];
const int upper=(1<<16);
const int ID[10][10]={{0},{4,1},{8,5,2},{12,9,6,3},{13,10,7},{14,11},{15}};
int walking[90]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,17,3,18,272,48,34,6,288,36,4352,768,544,96,68,12,4608,576,72,12288,8704,1536,1088,192,9216,1152,24576,17408,3072,2176,18432,49152,34816,33,528,66,8448,1056,132,16896,2112,33792,136,273,7,1057,4368,16912,112,546,2114,14,292,1792,8736,224,33824,1092,4672,584,28672,3584,17472,2184,9344,57344,34944};
int unionset(int x,int y){return x|y;}
int intersection(int x,int y){return x&y;}
bool emptyset(int x){return x==0;}
void dfs(int board)
{
if(~f[board]) return;
for(int i=0;i<82;++i)
{
if(emptyset(intersection(board,walking[i])))
{
int newset=unionset(board,walking[i]);
dfs(newset);
if(f[newset]==0)
{
f[board]=1;
return;
}
}
}
f[board]=0;
}
char fgc()
{
char res=0;
while((res^'*')&&(res^'.')) res=getchar();
return res;
}
int main()
{
scanf("%d",&t);
memset(f,-1,sizeof(f));
f[upper-1]=0;
for(int i=0;i^upper;++i)
{
if(f[i]==-1) dfs(i);
}
while(t--)
{
int board=0;
for(int i=0;i<n;++i)
{
for(int j=0;j<m[i];++j) board+=(fgc()=='*')?(1<<ID[i][j]):0;
}
printf(f[board]?"Possible.":"Impossible.");
printf("\n");
}
return 0;
}
∆ P3975 [TJOI2015]弦论 - AC
temp.
// via Strelitzia(XC)
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 5;
int nxt[N << 1],ver[N << 1],head[N << 1],tot;
void addEdge(int u,int v) {nxt[++ tot] = head[u];ver[tot] = v;head[u] = tot;}
struct node {
int ch[26];
int len,fa;
long long sz,ep;
}sam[N << 1];
char s[N],out[N];
int n,t,k,cnt,cntnd = 1,lst = 1;
int vis[N << 1];
void add(int c) {
int p = lst;
int u = lst = ++ cntnd;
sam[u].len = sam[p].len + 1;
if (t == 1)
sam[u].sz = 1;
for (; p && !sam[p].ch[c] ; p = sam[p].fa)
sam[p].ch[c] = u;
if (!p)
sam[u].fa = 1;
else {
int q = sam[p].ch[c];
if (sam[q].len == sam[p].len + 1)
sam[u].fa = q;
else {
int spt = ++ cntnd;
for (int i = 0 ; i < 26 ; ++ i)
sam[spt].ch[i] = sam[q].ch[i];
sam[spt].fa = sam[q].fa;
sam[spt].len = sam[p].len + 1;
sam[q].fa = sam[u].fa = spt;
for (; p && sam[p].ch[c] == q ; p = sam[p].fa)
sam[p].ch[c] = spt;
}
}
}
void dfs(int u) {
if (vis[u])
return;
vis[u] = 1;
for (int i = 0 ; i < 26 ; ++ i) {
int v = sam[u].ch[i];
if (v == 0)
continue;
dfs(v);
sam[u].sz += sam[v].sz;
}
}
void exdfs(int u) {
for (int e = head[u] ; e ; e = nxt[e]) {
int v = ver[e];
exdfs(v);
sam[u].sz += sam[v].sz;
}
sam[u].ep = sam[u].sz;
}
void redfs(int u) {
if (u != 1)
k -= t == 0 ? 1 : sam[u].ep;
if (k == 0) {
for (int i = 0 ; i < cnt ; ++ i)
putchar(out[i] + 'a');
exit(0);
}
for (int i = 0 ; i < 26 ; ++ i) {
if (sam[u].ch[i]) {
if (k > sam[sam[u].ch[i]].sz)
k -= sam[sam[u].ch[i]].sz;
else {
out[cnt ++] = i;
redfs(sam[u].ch[i]);
}
}
}
}
int main () {
scanf("%s",s);
n = strlen(s);
scanf("%d %d",&t,&k);
for (int i = 0 ; i < n ; ++ i)
add(s[i] - 'a');
for (int i = 2 ; i <= cntnd ; ++ i) {
addEdge(sam[i].fa,i);
if (t == 0)
sam[i].sz = 1;
}
if (t == 0) {
dfs(1);
if (k > sam[1].sz)
return 0 & puts("-1");
redfs(1);
}
else {
exdfs(1);
dfs(1);
if (k > sam[1].sz - sam[1].ep)
return 0 & puts("-1");
redfs(1);
}
return 0;
}
∆ P2178 [NOI2015] 品酒大会 - AC
SA+DSU.
#include<cstdio>
#include<algorithm>
using namespace std;
const long long INF=1e18;
long long n,mp[300010];
char s[300010];
long long a[300010],ans[300010],exans[300010],cur,excur;
struct suffix_array
{
long long n,m,sa[600010],rk[600010],cnt[600010],fir[600010],sec[600010],tmp[600010],ht[600010];
char s[300010];
void init(long long len,long long siz,char c[])
{
n=len;
m=siz;
for(long long i=1;i<=n;++i) s[i]=c[i];
}
void getsuffix()
{
for(long long i=1;i<=m;++i) cnt[i]=0;
for(long long i=1;i<=n;++i) ++cnt[fir[i]=s[i]];
for(long long i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(long long i=1;i<=n;++i) sa[cnt[fir[i]]--]=i;
for(long long k=1;k<=n;k<<=1)
{
long long tot=0;
for(long long i=n-k+1;i<=n;++i) sec[++tot]=i;
for(long long i=1;i<=n;++i) if(sa[i]>k) sec[++tot]=sa[i]-k;
for(long long i=1;i<=m;++i) cnt[i]=0;
for(long long i=1;i<=n;++i) ++cnt[fir[sec[i]]];
for(long long i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(long long i=n;i>=1;--i) sa[cnt[fir[sec[i]]]--]=sec[i];
tmp[sa[1]]=tot=1;
for(long long i=2;i<=n;++i) tmp[sa[i]]=(fir[sa[i]]==fir[sa[i-1]]&&fir[sa[i]+k]==fir[sa[i-1]+k])?tot:(++tot);
if(tot>=n) break;
for(long long i=1;i<=n;++i) fir[i]=tmp[i];
m=tot+1;
}
for(long long i=1;i<=n;++i) rk[sa[i]]=i;
}
void getcommon()
{
long long k=0;
for(long long i=1;i<=n;++i)
{
if(k) --k;
long long j=sa[rk[i]-1];
while(s[i+k]==s[j+k]) ++k;
ht[rk[i]]=k;
}
}
}SA;
struct disjoint_set_union
{
long long fa[300010];
long long mn[300010],mx[300010],siz[300010];
void init(long long n)
{
for(long long i=1;i<=n;++i)
{
fa[i]=i;
siz[i]=1;
mn[SA.rk[i]]=mx[SA.rk[i]]=a[i];
}
}
long long find(long long x){return (x^fa[x])?fa[x]=find(fa[x]):fa[x];}
void merge(long long x,long long y)
{
x=find(x);
y=find(y);
cur+=siz[x]*siz[y];
excur=max(excur,max(mn[x]*mn[y],mx[x]*mx[y]));
if(siz[x]<siz[y]) swap(x,y);
fa[y]=x;
mn[x]=min(mn[x],mn[y]);
mx[x]=max(mx[x],mx[y]);
siz[x]+=siz[y];
}
}DSU;
bool cmp(long long one,long long ano){return SA.ht[one]>SA.ht[ano];}
int main()
{
scanf("%lld %s",&n,s+1);
SA.init(n,128,s);
for(long long i=1;i<=n;++i) scanf("%lld",&a[i]);
SA.getsuffix();
SA.getcommon();
DSU.init(n);
SA.ht[1]=-1;
for(long long i=1;i<=n;++i) mp[i]=i;
sort(mp+1,mp+n+1,cmp);
excur=-INF;
long long pos=n-1;
for(long long i=1;i<=n;++i)
{
while(pos>SA.ht[mp[i]])
{
ans[pos]=cur;
exans[pos]=excur;
--pos;
}
if(pos<0) break;
DSU.merge(mp[i],mp[i]-1);
}
for(long long i=0;i<n;++i) printf("%lld %lld\n",ans[i],exans[i]==-INF?0:exans[i]);
return 0;
}
∆ P6793 [SNOI2020] 字符串 - AC
SA+DSU。
#include<cstdio>
#include<algorithm>
using namespace std;
int n,k;
long long ans;
char s[1000010];
int ownabs(int x)
{
return x<0?-x:x;
}
struct suffix_array
{
int n,m,sa[1000010],rk[1000010],cnt[1000010],fir[1000010],sec[1000010],tmp[1000010],ht[1000010];
char s[1000010];
void init(int len,int siz,char c[])
{
n=len;
m=siz;
for(int i=1;i<=n;++i) s[i]=c[i];
}
void getsuffix()
{
for(int i=1;i<=m;++i) cnt[i]=0;
for(int i=1;i<=n;++i) ++cnt[fir[i]=s[i]];
for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(int i=1;i<=n;++i) sa[cnt[fir[i]]--]=i;
for(int k=1;k<=n;k<<=1)
{
int tot=0;
for(int i=n-k+1;i<=n;++i) sec[++tot]=i;
for(int i=1;i<=n;++i) if(sa[i]>k) sec[++tot]=sa[i]-k;
for(int i=1;i<=m;++i) cnt[i]=0;
for(int i=1;i<=n;++i) ++cnt[fir[sec[i]]];
for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(int i=n;i>=1;--i) sa[cnt[fir[sec[i]]]--]=sec[i];
tmp[sa[1]]=tot=1;
for(int i=2;i<=n;++i) tmp[sa[i]]=(fir[sa[i]]==fir[sa[i-1]]&&fir[sa[i]+k]==fir[sa[i-1]+k])?tot:(++tot);
if(tot>=n) break;
for(int i=1;i<=n;++i) fir[i]=tmp[i];
m=tot+1;
}
for(int i=1;i<=n;++i) rk[sa[i]]=i;
}
void getcommon()
{
int k=0;
for(int i=1;i<=n;++i)
{
if(k) --k;
int j=sa[rk[i]-1];
while(s[i+k]==s[j+k]) ++k;
ht[rk[i]]=k;
}
}
}SA;
struct disjoint_set_union
{
int fa[1000010],num[1000010];
void init(int n)
{
for(int i=1;i<=n;++i) fa[i]=0;
for(int i=1;i<=(n>>1)-k+1;++i)
{
num[i]=1;
num[i+(n>>1)+1]=-1;
}
}
int find(int x)
{
return fa[x]?fa[x]=find(fa[x]):x;
}
void merge(int x,int y,int len,int id)
{
x=find(x);
y=find(y);
fa[x]=fa[y]=id;
if(num[x]*num[y]<0) ans+=(long long)(k-len)*min(ownabs(num[x]),ownabs(num[y]));
num[id]=num[x]+num[y];
}
}DSU;
struct node
{
int l,r,len;
}nodes[1000010];
bool cmp(node one,node ano)
{
return one.len>ano.len;
}
int main()
{
scanf("%d %d",&n,&k);
scanf("%s %s",s+1,s+n+2);
s[n+1]='#';
SA.init(n<<1|1,128,s);
SA.getsuffix();
SA.getcommon();
DSU.init(n<<1);
for(int i=1;i<=(n<<1);++i)
{
nodes[i].l=SA.sa[i];
nodes[i].r=SA.sa[i+1];
nodes[i].len=min(SA.ht[i+1],k);
}
sort(nodes+1,nodes+(n<<1)+1,cmp);
for(int i=1;i<=(n<<1);++i) DSU.merge(nodes[i].l,nodes[i].r,nodes[i].len,i+(n<<1|1));
printf("%lld\n",ans);
return 0;
}
∆ P4112 [HEOI2015]最短不公共子串 - AC
SAM+DP.
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=1e9;
int ID(char c)
{
return c-'a';
}
struct suffix_automaton
{
struct node
{
int len,link,ch[26];
}nodes[5010];
int n,cntot,las;
char s[2010];
void init(int len,char c[])
{
n=len;
for(int i=1;i<=n;++i) s[i]=c[i];
cntot=las=1;
nodes[0].len=nodes[0].link=0;
}
void extend(char c)
{
int cur=++cntot,one=las,ano=0;
nodes[cur].len=nodes[las].len+1;
while(one&&!nodes[one].ch[ID(c)])
{
nodes[one].ch[ID(c)]=cur;
one=nodes[one].link;
}
if(one==0) nodes[cur].link=1;
else
{
ano=nodes[one].ch[ID(c)];
if(nodes[one].len+1==nodes[ano].len) nodes[cur].link=ano;
else
{
int clone=++cntot;
nodes[clone].len=nodes[one].len+1;
nodes[clone].link=nodes[ano].link;
memcpy(nodes[clone].ch,nodes[ano].ch,sizeof(int)*26);
while(one&&nodes[one].ch[ID(c)]==ano)
{
nodes[one].ch[ID(c)]=clone;
one=nodes[one].link;
}
nodes[ano].link=nodes[cur].link=clone;
}
}
las=cur;
}
void getsuffix()
{
for(int i=1;i<=n;++i) extend(s[i]);
}
};
struct prefix_subseq_automaton
{
struct node
{
int pre[26];
}nodes[5010];
int n;
char s[2010];
void init(int len,char c[])
{
n=len;
for(int i=1;i<=n;++i) s[i]=c[i];
}
void getprefix()
{
for(int i=2;i<=n+1;++i)
{
for(int j=0;j<26;++j) nodes[i].pre[j]=nodes[i-1].pre[j];
nodes[i].pre[ID(s[i-1])]=i-1;
}
}
};
struct suffix_subseq_automaton
{
struct node
{
int suf[26];
}nodes[5010];
int n;
char s[2010];
void init(int len,char c[])
{
n=len;
for(int i=1;i<=n;++i) s[i]=c[i];
}
void getsuffix()
{
for(int i=n-1;i>=0;--i)
{
for(int j=0;j<26;++j) nodes[i].suf[j]=nodes[i+1].suf[j];
nodes[i].suf[ID(s[i+1])]=i+1;
}
}
};
char ones[2010],anos[2010];
int n,m;
namespace prob_one
{
suffix_automaton SAM;
int ans=INF;
void engoric(int pos)
{
int now=1;
for(int i=pos;i<=n;++i)
{
now=SAM.nodes[now].ch[ID(ones[i])];
if(!now)
{
ans=min(ans,i-pos+1);
return;
}
}
}
void solve()
{
SAM.init(m,anos);
SAM.getsuffix();
for(int i=1;i<=n;++i) engoric(i);
if(ans==INF) printf("-1\n");
else printf("%d\n",ans);
}
}
namespace prob_two
{
int ans=INF;
void engoric(int pos)
{
int now=pos;
for(int i=1;i<=m&&now<=n;++i)
{
if(ones[now]==anos[i]) ++now;
}
if(now<=n) ans=min(ans,now-pos+1);
}
void solve()
{
for(int i=1;i<=n;++i) engoric(i);
if(ans==INF) printf("-1\n");
else printf("%d\n",ans);
}
}
namespace prob_three
{
suffix_automaton SAM;
suffix_subseq_automaton SSAM;
int f[5010][5010];
void engoric(int i,int j)
{
f[i][j]=2001;
for(int k=0;k<26;++k)
{
int x=SSAM.nodes[i].suf[k],y=SAM.nodes[j].ch[k];
if(x<=n) f[i][j]=min(f[i][j],f[x][y]+1);
}
}
void solve()
{
SAM.init(m,anos);
SAM.getsuffix();
SSAM.init(n,ones);
SSAM.getsuffix();
for(int i=0;i<=n;++i)
{
for(int j=0;j<26;++j)
{
if(!SSAM.nodes[i].suf[j]) SSAM.nodes[i].suf[j]=n+1;
}
}
for(int i=n;i>=0;--i)
{
for(int j=1;j<=SAM.cntot;++j) engoric(i,j);
}
if(f[0][1]==2001) printf("-1\n");
else printf("%d\n",f[0][1]);
}
}
namespace prob_four
{
prefix_subseq_automaton PSAM;
suffix_subseq_automaton SSAM;
int f[5010][5010],ans=INF;
void engoric(int i,int j)
{
for(int k=0;k<26;++k)
{
if(PSAM.nodes[i].pre[k])
{
int tmp=SSAM.nodes[f[PSAM.nodes[i].pre[k]][j-1]].suf[ID(ones[i])];
if(tmp) f[i][j]=max(f[i][j],tmp);
else
{
ans=min(ans,j);
return;
}
}
}
}
void solve()
{
PSAM.init(n,ones);
PSAM.getprefix();
SSAM.init(m,anos);
SSAM.getsuffix();
for(int i=1;i<=n;++i)
{
int tmp=SSAM.nodes[0].suf[ID(ones[i])];
if(tmp) f[i][1]=max(f[i][1],tmp);
else
{
printf("1\n");
return;
}
}
for(int i=1;i<=n;++i)
{
for(int j=2;j<=i;++j) engoric(i,j);
}
if(ans==INF) printf("-1\n");
else printf("%d\n",ans);
}
}
int main()
{
scanf("%s %s",ones+1,anos+1);
n=strlen(ones+1);
m=strlen(anos+1);
prob_one::solve();
prob_two::solve();
prob_three::solve();
prob_four::solve();
return 0;
}
∆ abc192 A - Star - AC
.
#include<cstdio>
int x;
int main()
{
scanf("%d",&x);
for(int i=1;;++i)
{
if((x+i)%100==0)
{
printf("%d\n",i);
break;
}
}
return 0;
}
∆ abc192 B - uNrEaDaBlE sTrInG - AC
.
#include<cstdio>
#include<cstring>
char s[1010];
int main()
{
scanf("%s",s+1);
bool flag=1;
int n=strlen(s+1);
for(int i=1;i<=n;++i)
{
if(i&1)
{
if(s[i]<'a'||s[i]>'z')
{
flag=0;
break;
}
}
else
{
if(s[i]<'A'||s[i]>'Z')
{
flag=0;
break;
}
}
}
printf("%s\n",flag?"Yes":"No");
return 0;
}
∆ abc192 D - Base n - WA
bs.
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
struct bigInt : vector<long long>{
bigInt &check( ){
while( ! empty( ) && ! back( ) ) pop_back( );
if( empty( ) ) return *this;
for( unsigned i = 1; i < size( ); ++ i ){ ( *this )[i] += ( *this )[i - 1] / 10; ( *this )[i - 1] %= 10; }
while( back( ) >= 10 ){ push_back( back( ) / 10 ); ( *this )[size( ) - 2] %= 10; }
return *this;
}
bigInt( long long tpN = 0 ){ push_back( tpN ); check( ); }
};
istream &operator >> ( istream &is, bigInt &tpN ){
string s;
is >> s; tpN.clear( );
for( int i = s.size( ) - 1; i >= 0; --i ) tpN.push_back( s[i] - '0' );
return is;
}
ostream &operator << ( ostream &os, const bigInt &tpN ){
if( tpN.empty( ) ) os << 0;
for( int i = tpN.size( ) - 1; i >= 0; --i ) os << tpN[i];
return os;
}
bool operator != ( const bigInt &one, const bigInt &another ){
if( one.size( ) != another.size( ) ) return 1;
for( int i = one.size( ) - 1; i >= 0; --i ){
if( one[i] != another[i] ) return 1;
}
return 0;
}
bool operator == ( const bigInt &one, const bigInt &another ){
return ! ( one != another );
}
bool operator < ( const bigInt &one, const bigInt &another ){
if( one.size( ) != another.size( ) ) return one.size( ) < another.size( );
for( int i = one.size( ) - 1; i >= 0; --i ){
if( one[i] != another[i] ) return one[i] < another[i];
}
return 0;
}
bool operator > ( const bigInt &one, const bigInt &another ){ return another < one; }
bool operator <= ( const bigInt &one, const bigInt &another ){ return ! (one > another ); }
bool operator >= ( const bigInt &one, const bigInt &another ){ return ! (one < another ); }
bigInt &operator += ( bigInt &one, const bigInt &another ){
if( one.size( ) < another.size( ) ) one.resize(another.size( ) );
for( unsigned i = 0; i != another.size( ); ++ i ) one[i] += another[i];
return one.check( );
}
bigInt operator + ( bigInt one, const bigInt &another ){ return one += another; }
bigInt &operator -= ( bigInt &one, bigInt another ){
if( one < another ) swap( one, another );
for( unsigned i = 0; i != another.size( ); one[i] -= another[i], ++ i ){
if( one[i] < another[i] ){
unsigned j = i + 1;
while( ! one[j] ) ++ j;
while( j > i ){ -- one[j]; one[--j] += 10; }
}
}
return one.check( );
}
bigInt operator - ( bigInt one, const bigInt &another ){ return one -= another; }
bigInt operator * ( const bigInt &one, const bigInt &another ){
bigInt tpN;
tpN.assign( one.size( ) + another.size( ) - 1, 0 );
for( unsigned i = 0; i != one.size( ); ++ i ){
for( unsigned j = 0; j != another.size( ); ++ j ) tpN[i + j] += one[i] * another[j];
}
return tpN.check( );
}
bigInt &operator *= ( bigInt &one, const bigInt &another ){ return one = one * another; }
bigInt divMod( bigInt &one, const bigInt &another ){
bigInt ans;
for( int t = one.size( ) - another.size( ); one >= another; -- t ){
bigInt tpS;
tpS.assign( t + 1, 0 );
tpS.back( ) = 1;
bigInt tpM = another * tpS;
while( one >= tpM ){ one -= tpM; ans += tpS; }
}
return ans;
}
bigInt operator / ( bigInt one, const bigInt &another ){ return divMod(one, another ); }
bigInt &operator /= ( bigInt &one, const bigInt &another ){ return one = one / another; }
bigInt &operator %= ( bigInt &one, const bigInt &another ){ divMod( one, another ); return one; }
bigInt operator % ( bigInt one, const bigInt &another ){ return one %= another; }
char s[70];
int n,cntot;
bigInt m,num[70],mx;
bool check(bigInt bas)
{
bigInt res=0,sab=1;
for(int i=1;i<=cntot;++i)
{
res+=num[i]*sab;
sab*=bas;
if(res>m) return false;
}
return true;
}
int main()
{
cin>>(s+1)>>m;
n=strlen(s+1);
for(int i=n;i>=1;--i)
{
num[++cntot]=s[i]-'0';
mx=max(mx,num[cntot]);
}
if(cntot==1) cout<<(num[cntot]<=m)<<"\n";
else
{
bigInt l=mx+1,r=m+1,ans=0;
while(l<=r)
{
bigInt mid=(l+r)/2;
if(check(mid))
{
l=mid+1;
ans=mid;
}
else r=mid-1;
}
cout<<ans-mx<<"\n";
}
return 0;
}
∆ abc193 E - Train - UN
.
.
∆ arc113 A - A*B*C - AC
调和级数算。
#include<cstdio>
long long k;
int main()
{
scanf("%lld",&k);
long long ans=0;
for(long long i=1;i<=k;++i)
{
for(long long j=1;j<=k/i;++j) ans+=(k/i/j);
}
printf("%lld\n",ans);
return 0;
}
∆ arc113 B - A^B^C - AC
ex euler theorem.
#include<cstdio>
long long getphi(long long x)
{
long long res=x;
for(long long i=2;i*i<=x;++i)
{
if(x%i==0)
{
res=res/i*(i-1);
while(x%i==0) x/=i;
}
}
if(x>1) res=res/x*(x-1);
return res;
}
long long cqpow(long long bas,long long fur,long long mod)
{
long long res=1;
while(fur)
{
if(fur&1) res=res*bas%mod;
bas=bas*bas%mod;
fur>>=1;
}
return res;
}
long long a,b,c;
int main()
{
scanf("%lld %lld %lld",&a,&b,&c);
printf("%lld\n",cqpow(a,cqpow(b,c,getphi(10))+getphi(10),10));
return 0;
}