数学计算
用线段树记录之前乘过的每一个数，作除法时把原本的乘数改成111即可。
代码：
#include<bits/stdc++.h>
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
#define N 100005
using namespace std;
int t,n;
long long mod;
inline long long read(){
long long ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
return ans;
}
struct Node{int l,r;long long mul;}T[N<<2];
inline void pushup(int p){T[p].mul=T[lc].mul*T[rc].mul%mod;}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r,T[p].mul=1;
if(l==r)return;
build(lc,l,mid);
build(rc,mid+1,r);
}
inline void update(int p,int k,int v){
if(T[p].l==T[p].r){
T[p].mul=v;
return;
}
if(k<=mid)update(lc,k,v);
else update(rc,k,v);
pushup(p);
}
int main(){
t=read();
while(t--){
n=read(),mod=read();
build(1,1,n);
for(int i=1;i<=n;++i){
int op=read();
if(op==1){long long v=read();update(1,i,v);}
else{int pos=read();update(1,pos,1);}
printf("%lld\n",T[1].mul);
}
}
return 0;
}
智力竞赛
这是一道语文阅读题
二分答案之后上最小链覆盖即可。
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=505;
bool trans[N][N],tmp[N][N],e[N][N],vis[N];
int mp[N],lim,n,m,matching[N];
struct Node{
int id,w;
friend inline bool operator<(const Node&a,const Node&b){return a.w<b.w;}
}a[N];
inline bool find(int x,int Lim){
for(ri i=1;i<=Lim;++i){
if(!trans[x][i]||vis[i])continue;
vis[i]=1;
if(!matching[i]||find(matching[i],Lim))return matching[i]=x,1;
}
return 0;
}
inline int match(int Lim){
int ret=0;
memset(matching,0,sizeof(matching));
for(ri i=1;i<=Lim;++i){
memset(vis,0,sizeof(vis));
if(find(i,Lim))++ret;
}
return ret;
}
inline bool check(int Lim){
memset(trans,0,sizeof(trans));
for(ri i=1;i<=Lim;++i)for(ri j=1;j<=Lim;++j)trans[i][j]=e[i][j];
for(ri k=1;k<=Lim;++k)for(ri i=1;i<=Lim;++i)if(trans[i][k])
for(ri j=1;j<=Lim;++j)if(trans[k][j])trans[i][j]=1;
return Lim-match(Lim)<=lim;
}
int main(){
lim=read()+1,n=read();
for(ri i=1;i<=n;++i){
a[i]=(Node){i,read()};
for(ri tt=read();tt;--tt)tmp[i][read()]=1;
}
sort(a+1,a+n+1);
for(ri i=1;i<=n;++i)mp[a[i].id]=i;
for(ri i=1;i<=n;++i)for(ri j=1;j<=n;++j)e[mp[i]][mp[j]]=tmp[i][j];
int l=1,r=n,ans=1;
while(l<=r){
int mid=l+r>>1;
if(check(mid))l=mid+1,ans=mid;
else r=mid-1;
}
if(r^n)cout<<a[ans+1].w;
else puts("AK");
return 0;
}
party
好题。
考虑lcslcslcs的性质。
fi,j=max{fi−1,j,fi,j−1,fi−1,j−1+[si==tj]}f_{i,j}=max\{f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+[s_i==t_j]\}fi,j=max{fi−1,j,fi,j−1,fi−1,j−1+[si==tj]}
于是fi,j−fi−1,j=0/1f_{i,j}-f_{i-1,j}=0/1fi,j−fi−1,j=0/1，我们把这个东西拿来状压，然后转移即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1005,M=1<<16,mod=1e9+7;
int tt,n,f[2][M][3],tran1[20],tran2[20],tmp=0,ans[20],bit[M];
char s[20];
inline void trans(int sta,int a[]){
a[0]=0;
for(ri i=1;i<=n;++i)a[i]=a[i-1]+((sta>>(i-1))&1);
}
inline int inv_trans(int a[]){
int ret=0;
for(ri i=1;i<=n;++i)ret|=(a[i]-a[i-1])<<(i-1);
return ret;
}
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline void update(int&a,const int&b){a=add(a,b);}
inline int max(const int&a,const int&b,const int&c){return a>b?(a>c?a:c):(b>c?b:c);}
inline void update(int pos,int sta,int len,char x,int upd){
trans(sta,tran1);
for(ri i=1;i<=n;++i)tran2[i]=max(tran2[i-1],tran1[i],tran1[i-1]+(x==s[i]));
int nsta=inv_trans(tran2);
update(f[pos][nsta][len],upd);
}
int main(){
scanf("%d%d%s",&tt,&n,s+1);
for(ri i=1,up=1<<n;i<up;++i)bit[i]=bit[i>>1]+(i&1);
f[0][0][0]=1;
for(ri up=1<<n;tt;--tt){
memset(f[tmp^1],0,sizeof(f[tmp^1]));
for(ri i=0;i<up;++i){
if(f[tmp][i][0]){
update(tmp^1,i,1,'N',f[tmp][i][0]);
update(tmp^1,i,0,'O',f[tmp][i][0]);
update(tmp^1,i,0,'I',f[tmp][i][0]);
}
if(f[tmp][i][1]){
update(tmp^1,i,1,'N',f[tmp][i][1]);
update(tmp^1,i,2,'O',f[tmp][i][1]);
update(tmp^1,i,0,'I',f[tmp][i][1]);
}
if(f[tmp][i][2]){
update(tmp^1,i,1,'N',f[tmp][i][2]);
update(tmp^1,i,0,'O',f[tmp][i][2]);
}
}
tmp^=1;
}
for(ri i=0,up=1<<n;i<up;++i)for(ri j=0;j<3;++j)update(ans[bit[i]],f[tmp][i][j]);
for(ri i=0;i<=n;++i)cout<<ans[i]<<'\n';
return 0;
}
str
对于每个碱基序列用kmpkmpkmp处理出failfailfail数组来进行dpdpdp转移即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=10005,mod=1e9+7;
typedef long long ll;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline void update(int&a,const int&b){a=add(a,b);}
int k,ans=0,Tt,n,f[2][N],tmp=0,m,fail[N];
char s[N],t[N];
int main(){
scanf("%d%s",&Tt,s+1),n=strlen(s+1);
for(ri i=0;i<=n;++i)f[0][i]=1;
for(ri tt;Tt;--Tt){
tmp^=1,memset(f[tmp],0,sizeof(f[tmp])),scanf("%d",&tt);
while(tt--){
scanf("%s",t+1),m=strlen(t+1);
for(ri i=1,j=0;i<m;++i){
while(j&&t[i+1]!=t[j+1])j=fail[j];
fail[i+1]=t[i+1]==t[j+1]?++j:0;
}
for(ri i=1,j=0;i<=n;++i){
while(j&&s[i]!=t[j+1])j=fail[j];
if(s[i]==t[j+1])++j;
if(j==m)update(f[tmp][i],f[tmp^1][i-m]);
}
}
}
for(ri i=0;i<=n;++i)update(ans,f[tmp][i]);
cout<<ans;
return 0;
}
xor
额这个题不是把可持久化01trie01trie01trie放到树上来差个分就完了吗？
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1e5+5;
struct Trie{
int son[N*100][2],siz[N*100],tot;
Trie(){tot=0,memset(son,0,sizeof(son)),memset(siz,0,sizeof(siz));}
inline void insert(int &o,int las,int v){
int p=++tot;
o=p;
for(ri i=31,tmp;~i;--i){
tmp=(v>>i)&1;
siz[p]=siz[las]+1,son[p][tmp^1]=son[las][tmp^1],son[p][tmp]=++tot;
p=son[p][tmp],las=son[las][tmp];
}
siz[p]=siz[las]+1;
}
inline int query1(int pl,int pr,int v){
int ret=0;
for(ri i=31,tmp;~i;--i){
tmp=(v>>i)&1;
if(siz[son[pr][tmp^1]]!=siz[son[pl][tmp^1]])ret|=1<<i,pl=son[pl][tmp^1],pr=son[pr][tmp^1];
else pl=son[pl][tmp],pr=son[pr][tmp];
}
return ret;
}
inline int query2(int pa,int pb,int pc,int pd,int v){
int ret=0;
for(ri i=31,tmp;~i;--i){
tmp=(v>>i)&1;
if(siz[son[pa][tmp^1]]+siz[son[pb][tmp^1]]-siz[son[pc][tmp^1]]-siz[son[pd][tmp^1]]){
ret|=1<<i;
pa=son[pa][tmp^1],pb=son[pb][tmp^1],pc=son[pc][tmp^1],pd=son[pd][tmp^1];
}
else pa=son[pa][tmp],pb=son[pb][tmp],pc=son[pc][tmp],pd=son[pd][tmp];
}
return ret;
}
}T1,T2;
int n,q,rt1[N],rt2[N],siz[N],top[N],pred[N],tot=0,hson[N],dep[N],fa[N],num[N],a[N];
vector<int>e[N];
void dfs1(int p){
siz[p]=1;
for(ri i=0,v;i<e[p].size();++i){
if((v=e[p][i])==fa[p])continue;
fa[v]=p,dep[v]=dep[p]+1,dfs1(v),siz[p]+=siz[v];
if(siz[v]>siz[hson[p]])hson[p]=v;
}
}
void dfs2(int p,int tp){
top[p]=tp,pred[num[p]=++tot]=p;
T1.insert(rt1[p],rt1[fa[p]],a[p]);
if(!hson[p])return;
dfs2(hson[p],tp);
for(ri i=0,v;i<e[p].size();++i)if((v=e[p][i])!=fa[p]&&v!=hson[p])dfs2(v,v);
}
inline int lca(int x,int y){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int main(){
n=read(),q=read();
for(ri i=1;i<=n;++i)a[i]=read();
for(ri i=1,u,v;i<n;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
dfs1(1),dfs2(1,1);
for(ri i=1;i<=n;++i)T2.insert(rt2[i],rt2[i-1],a[pred[i]]);
for(ri op,x,y,t;q;--q){
op=read(),x=read(),y=read();
if(op==1)cout<<T2.query1(rt2[num[x]-1],rt2[num[x]+siz[x]-1],y)<<'\n';
else t=lca(x,y),cout<<T1.query2(rt1[x],rt1[y],rt1[t],rt1[fa[t]],read())<<'\n';
}
return 0;
}
教科书般的*
发现要维护这个东西：f(x,k)=∑i=1xikf(x,k)=\sum_{i=1}^xi^kf(x,k)=∑i=1xik
然后这个肯定是个kkk次多项式，于是拉格朗日插值把多项式求出来就完了。代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int mod=1e9+7,N=105;
typedef long long ll;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline void update(int&a,const int&b){a=add(a,b);}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}
ll n,a[N];
int m,k,f[N],inv[N];
inline int lagrange(int x,int n){
if(x<=k+2)return f[x];
int ret=0;
for(ri i=1,mult;i<=n;++i){
mult=f[i];
for(ri j=1;j<=n;++j){
if(i>j)mult=mul(mult,mul(inv[i-j],dec(x,j)));
if(i<j)mult=mul(mult,mul(mod-inv[j-i],dec(x,j)));
}
ret=add(ret,mult);
}
return ret;
}
int main(){
inv[1]=1;
for(ri i=2;i<=55;++i)inv[i]=mul(inv[mod-mod/i*i],mod-mod/i);
int tt;
scanf("%d",&tt);
while(tt--){
scanf("%lld%d",&n,&m),k=m+1;
for(ri i=1;i<=m;++i)scanf("%lld",&a[i]);
sort(a+1,a+m+1);
a[m+1]=n+1;
f[1]=1;
for(ri i=2;i<=k+2;++i)f[i]=add(f[i-1],ksm(i,k));
int ans=0;
for(ri i=0;i<=m;++i)for(ri j=i+1;j<=m+1;++j){
ans=add(ans,lagrange((a[j]-a[i]-1)%mod,k+2));
ans=dec(ans,lagrange((a[j-1]-a[i])%mod,k+2));
}
cout<<ans<<'\n';
}
return 0;
}