A题：活着的证据
显然是贪心，对于位数不够的情况肯定是要吧所有v和i都用上，如果位数够了，多的v显然没用，多的i从高位向低位补齐即可，注意一些细节iii=3 viii=8
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read()
{
char c;
ll w=1;
while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
ll ans=c-'0';
while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
return ans*w;
}
int T;
const int xx=5e6+5;
int a[xx];
int main(){
T=read();
while(T--)
{
int V=read(),I=read(),n=read();
if(V+I<=n)
{
while(V--)putchar('5');
while(I--)putchar('1');
puts("");
continue;
}
memset(a,0,sizeof(a[0])*(n+1));
for(int i=1;i<=min(V,n);i++)a[i]=5;
for(int i=n;i>=1;i--)if(!a[i])a[i]=1,I--;
//注意单i只能加到3
for(int i=1;i<=n;i++)
{
if(a[i]==5&&I>=3){I-=3;a[i]+=3;}
else if(I>=2)I-=2,a[i]+=2;
else if(I>=1)I-=1,a[i]++;
}
for(int i=1;i<=n;i++)cout<<a[i];
puts("");
}
return 0;
}B题：寻寻觅觅寻不到
明显模拟，记录从最长多少个后缀是合法的，最长多少前缀是合法的，最后再把截取的字符串放到最末尾看是否匹配即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read()
{
char c;
ll w=1;
while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
ll ans=c-'0';
while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
return ans*w;
}
int n;
const int xx=3e5+5;
char s[xx],c[xx];
int pre[xx],suf[xx];
int main(){
// freopen("str.in","r",stdin);
// freopen("str.out","w",stdout);
int T=read();
while(T--)
{
scanf("%s",s+1);
scanf("%s",c+1);
int n=strlen(s+1),m=strlen(c+1),k=read();
assert(k<=n);
if(n!=m){puts("NO");continue;}
memset(pre,0,sizeof(pre[0])*(n+3));
memset(suf,0,sizeof(suf[0])*(n+3));
for(int i=1;i<=n;i++)
{
if(s[i]==c[i])pre[i]=1;
else break;
}
pre[0]=1;suf[n+1]=1;
for(int i=n;i>=k+1;i--)
{
if(s[i]==c[i-k])suf[i]=1;
else break;
}
int vis=0;
for(int i=1;i<=n-k+1;i++)
{
int vs=1;
for(int j=1;j<=k;j++)if(s[i+j-1]!=c[n-k+j]){vs=0;break;}
if(!vs)continue;
if(pre[i-1]&&suf[i+k]){vis=1;break;}
}
if(!vis)puts("NO");
else puts("YES");
}
return 0;
}C题：踩不出足迹
考虑异或的性质，首先异或和同或都是具有交换律的，所以我们可以任意调换顺序。
首先同或运算符就等价于和另外一个数取反异或起来。。
所以我们如果需要将若干个数取反后异或起来，可以把它们排在一起然后同时消掉这两个取反符号。
最终可能会有一个取反后的数没有被消掉，我们就分类讨论一下。就是比较一下 和
的大小。
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
ll read()
{
char c;
ll w=1;
while((c=getchar())>'9'||c<'0');
ll ans=c-'0';
while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
return ans*w;
}
ll x,y;
signed main(){
int n,k;
n=read();
k=read();
while(n--)
{
y=read();
x^=y;
}
if(n==1)cout<<y<<"\n";
else
if(k==64)cout<<max(x,x^((0ull)-1ull))<<'\n';
else cout<<max(x,x^((1ull<<k)-1))<<'\n';
return 0;
}D题：都市的柏油路太硬
仔细观察题面，对于第二次建边之后答案一定就是原最小生成树上的最大边，将原树建成最小生成树多次询问两点之间的最大路径，考虑如何优化多测，可以使用kruskal重构树+O(1) lca 得到每次询问O(1)的复杂度（对于部分常数优秀的应该不优化也可以带log跑过）
#include <bits/stdc++.h>
using namespace std;
namespace fastIO{
#define BUF_SIZE 100000
#define OUT_SIZE 100000
//fread->read
bool IOerror=0;
//inline char nc(){char ch=getchar();if(ch==-1)IOerror=1;return ch;}
inline char nc(){
static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
if(p1==pend){
p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);
if(pend==p1){IOerror=1;return -1;}
}
return *p1++;
}
inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
template<class T> inline bool read(T &x){
bool sign=0;char ch=nc();x=0;
for(;blank(ch);ch=nc());
if(IOerror)return false;
if(ch=='-')sign=1,ch=nc();
for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if(sign)x=-x;
return true;
}
inline bool read(double &x){
bool sign=0;char ch=nc();x=0;
for(;blank(ch);ch=nc());
if(IOerror)return false;
if(ch=='-')sign=1,ch=nc();
for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if(ch=='.'){
double tmp=1; ch=nc();
for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
}
if(sign)x=-x;
return true;
}
inline bool read(char *s){
char ch=nc();
for(;blank(ch);ch=nc());
if(IOerror)return false;
for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
*s=0;
return true;
}
inline bool read_line(char *s){
char ch=nc();
for(;blank(ch);ch=nc());
if(IOerror)return false;
for(;ch!='\n'&&!IOerror;ch=nc())*s++=ch;
*s=0;
return true;
}
inline bool read(char &c){
for(c=nc();blank(c);c=nc());
if(IOerror){c=-1;return false;}
return true;
}
template<class T,class... U>bool read(T& h,U&... t){return read(h)&&read(t...);}
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace fastIO;
/************* debug begin *************/
string to_string(string s){return '"'+s+'"';}
string to_string(const char* s){return to_string((string)s);}
string to_string(const bool& b){return(b?"true":"false");}
template<class T>string to_string(T x){ostringstream sout;sout<<x;return sout.str();}
template<class A,class B>string to_string(pair<A,B> p){return "("+to_string(p.first)+", "+to_string(p.second)+")";}
template<class A>string to_string(const vector<A> v){
int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}";
return res;
}
void debug_out(){puts("");}
template<class T,class... U>void debug_out(const T& h,const U&... t){cout<<" "<<to_string(h);debug_out(t...);}
#ifdef tokitsukaze
#define debug(...) cout<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__);
#else
#define debug(...) 233;
#endif
/************* debug end *************/
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define sqr(x) (x)*(x)
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<int,ll> PIL;
typedef pair<ll,int> PLI;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<PII > VPII;
/************* define end *************/
void read(int *x,int l,int r){for(int i=l;i<=r;i++) read(x[i]);}
void read(ll *x,int l,int r){for(int i=l;i<=r;i++) read(x[i]);}
void read(double *x,int l,int r){for(int i=l;i<=r;i++) read(x[i]);}
void println(VI x){for(int i=0;i<sz(x);i++) printf("%d%c",x[i]," \n"[i==sz(x)-1]);}
void println(VL x){for(int i=0;i<sz(x);i++) printf("%lld%c",x[i]," \n"[i==sz(x)-1]);}
void println(int *x,int l,int r){for(int i=l;i<=r;i++) printf("%d%c",x[i]," \n"[i==r]);}
void println(ll *x,int l,int r){for(int i=l;i<=r;i++) printf("%lld%c",x[i]," \n"[i==r]);}
/*************** IO end ***************/
void go();
int main(){
#ifdef tokitsukaze
freopen("TEST.txt","r",stdin);
#endif
go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=2e6+10;
const ll mod=998244353;
/********************************* head *********************************/
void assert_lr(int x,int l,int r){assert(x>=l&&x<=r);}
struct LCA
{
#define type int
struct node{int to;type w;node(){}node(int _to,type _w):to(_to),w(_w){}};
type dis[MAX];
int path[2*MAX],deep[2*MAX],first[MAX],len[MAX],tot,n;
int dp[2*MAX][22];
vector<node> mp[MAX];
void dfs(int x,int pre,int h)
{
int i;
path[++tot]=x;
first[x]=tot;
deep[tot]=h;
for(i=0;i<mp[x].size();i++)
{
int to=mp[x][i].to;
if(to==pre) continue;
dis[to]=dis[x]+mp[x][i].w;
len[to]=len[x]+1;
dfs(to,x,h+1);
path[++tot]=x;
deep[tot]=h;
}
}
void ST(int n)
{
int i,j,x,y;
for(i=1;i<=n;i++) dp[i][0]=i;
for(j=1;(1<<j)<=n;j++)
{
for(i=1;i+(1<<j)-1<=n;i++)
{
x=dp[i][j-1];
y=dp[i+(1<<(j-1))][j-1];
dp[i][j]=deep[x]<deep[y]?x:y;
}
}
}
int query(int l,int r)
{
int len,x,y;
len=(int)log2(r-l+1);
x=dp[l][len];
y=dp[r-(1<<len)+1][len];
return deep[x]<deep[y]?x:y;
}
int lca(int x,int y)
{
int l,r,pos;
l=first[x];
r=first[y];
if(l>r) swap(l,r);
pos=query(l,r);
return path[pos];
}
type get_dis(int a,int b){return dis[a]+dis[b]-2*dis[lca(a,b)];}
int get_len(int a,int b){return len[a]+len[b]-2*len[lca(a,b)];}
void init(int _n)
{
n=_n;
for(int i=0;i<=n;i++)
{
dis[i]=0;
len[i]=0;
mp[i].clear();
}
}
void add_edge(int a,int b,type w=1)
{
mp[a].pb(node(b,w));
mp[b].pb(node(a,w));
}
void work(int rt)
{
tot=0;
dfs(rt,0,0);
ST(2*n-1);
}
#undef type
}lca;
/*
lca.init(n);
lca.add_edge(a,b,w) undirected edge.
lca.work(rt);
*/
struct dsu
{
int pre[MAX];
void init(int n)
{
int i;
for(i=1;i<=n;i++) pre[i]=i;
}
int find(int x)
{
if(pre[x]!=x) pre[x]=find(pre[x]);
return pre[x];
}
bool merge(int a,int b)
{
int ra,rb;
ra=find(a);
rb=find(b);
if(ra!=rb)
{
pre[ra]=rb;
return 1;
}
return 0;
}
}dsu;
struct node
{
int x,y;
ll w;
node(){}
node(int a,int b,ll c):x(a),y(b),w(c){}
friend bool operator<(node a,node b) {return a.w<b.w;}
};
vector<node> edge;
int tot;
ll val[MAX];
int kruskal(int n)
{
int res=0;
tot=n;
dsu.init(2*n);
sort(all(edge));
lca.init(2*n);
for(int i=0;i<sz(edge);i++)
{
int x=dsu.find(edge[i].x);
int y=dsu.find(edge[i].y);
if(x!=y)
{
res+=edge[i].w;
tot++;
lca.add_edge(tot,x);
lca.add_edge(tot,y);
dsu.merge(x,tot);
dsu.merge(y,tot);
val[tot]=edge[i].w;
}
}
return res;
}
typedef unsigned long long ull;
ull myRand(ull &k1, ull &k2){
ull k3 = k1, k4 = k2;
k1 = k4;
k3 ^= (k3 <<23);
k2 = k3 ^ k4 ^ (k3 >>17) ^ (k4 >>26);
return k2 + k4;
}
pair<int,int>myRanq(ull&k1,ull&k2,int MAXN){
int x=myRand(k1,k2)%MAXN+1,y=myRand(k1,k2)%MAXN+1;
if(x>y)return make_pair(y,x);
else return make_pair(x,y);
}
void go()
{
int n,m,i,a,b,q;
ll c,ans;
ull a1,a2;
while(read(n,m))
{
assert_lr(n,1,1e6);
assert_lr(m,1,2e6);
edge.clear();
while(m--)
{
read(a,b,c);
assert_lr(c,0,2e9);
edge.pb(node(a,b,c));
}
mem(val,0);
kruskal(n);
lca.work(tot);
read(q);
assert_lr(q,1,1e6);
read(a1,a2);
ans=0;
while(q--)
{
PII qst=myRanq(a1,a2,n);
ll v=val[lca.lca(qst.fi,qst.se)];
// debug(qst,lca.lca(qst.fi,qst.se))
ans^=v;
}
printf("%lld\n",ans);
}
}E：骄傲无知的现代人不知道珍惜
首先考虑如果组合数中模数远大于指数的情况。
问题转化为给定一张图，可以加边删边，求 GCPI。
对操作时间建立线段树，会发现每条边的贡献都是一个区间，启示我们使用可撤销并查集维护连通性，预处理逆元进行计算。
如果模数不一定大于指数，此时预处理逆元的方法不再可做。此时需要 LUCAS 定理来辅助求解。
同时，观察可知题中所给的模数不一定为质数，启示我们利用 EXLUCAS 的思想，提前预处理好每个数对应的情况，每次用 CRT 合并起来即可。
时限非常宽松，不需要明显常数优化。
#include <bits/stdc++.h>
using namespace std;
namespace fastIO{
#define BUF_SIZE 100000
#define OUT_SIZE 100000
//fread->read
bool IOerror=0;
//inline char nc(){char ch=getchar();if(ch==-1)IOerror=1;return ch;}
inline char nc(){
static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
if(p1==pend){
p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);
if(pend==p1){IOerror=1;return -1;}
}
return *p1++;
}
inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
template<class T> inline bool read(T &x){
bool sign=0;char ch=nc();x=0;
for(;blank(ch);ch=nc());
if(IOerror)return false;
if(ch=='-')sign=1,ch=nc();
for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if(sign)x=-x;
return true;
}
inline bool read(double &x){
bool sign=0;char ch=nc();x=0;
for(;blank(ch);ch=nc());
if(IOerror)return false;
if(ch=='-')sign=1,ch=nc();
for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if(ch=='.'){
double tmp=1; ch=nc();
for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
}
if(sign)x=-x;
return true;
}
inline bool read(char *s){
char ch=nc();
for(;blank(ch);ch=nc());
if(IOerror)return false;
for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
*s=0;
return true;
}
inline bool read_line(char *s){
char ch=nc();
for(;blank(ch);ch=nc());
if(IOerror)return false;
for(;ch!='\n'&&!IOerror;ch=nc())*s++=ch;
*s=0;
return true;
}
inline bool read(char &c){
for(c=nc();blank(c);c=nc());
if(IOerror){c=-1;return false;}
return true;
}
template<class T,class... U>bool read(T& h,U&... t){return read(h)&&read(t...);}
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace fastIO;
/************* debug begin *************/
string to_string(string s){return '"'+s+'"';}
string to_string(const char* s){return to_string((string)s);}
string to_string(const bool& b){return(b?"true":"false");}
template<class T>string to_string(T x){ostringstream sout;sout<<x;return sout.str();}
template<class A,class B>string to_string(pair<A,B> p){return "("+to_string(p.first)+", "+to_string(p.second)+")";}
template<class A>string to_string(const vector<A> v){
int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}";
return res;
}
void debug_out(){puts("");}
template<class T,class... U>void debug_out(const T& h,const U&... t){cout<<" "<<to_string(h);debug_out(t...);}
#ifdef tokitsukaze
#define debug(...) cout<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__);
#else
#define debug(...) 233;
#endif
/************* debug end *************/
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define sqr(x) (x)*(x)
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<int,ll> PIL;
typedef pair<ll,int> PLI;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<PII > VPII;
/************* define end *************/
void read(int *x,int l,int r){for(int i=l;i<=r;i++) read(x[i]);}
void read(ll *x,int l,int r){for(int i=l;i<=r;i++) read(x[i]);}
void read(double *x,int l,int r){for(int i=l;i<=r;i++) read(x[i]);}
void println(VI x){for(int i=0;i<sz(x);i++) printf("%d%c",x[i]," \n"[i==sz(x)-1]);}
void println(VL x){for(int i=0;i<sz(x);i++) printf("%lld%c",x[i]," \n"[i==sz(x)-1]);}
void println(int *x,int l,int r){for(int i=l;i<=r;i++) printf("%d%c",x[i]," \n"[i==r]);}
void println(ll *x,int l,int r){for(int i=l;i<=r;i++) printf("%lld%c",x[i]," \n"[i==r]);}
/*************** IO end ***************/
void go();
int main(){
#ifdef tokitsukaze
freopen("TEST.txt","r",stdin);
#endif
go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=2e5+10;
//const ll mod=998244353;
ll mod;
/********************************* head *********************************/
void assert_lr(int x,int l,int r){assert(x>=l&&x<=r);}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
ll g,t;
g=exgcd(b,a%b,x,y);
t=x;
x=y;
y=t-a/b*y;
return g;
}
namespace exCRT
{
ll excrt(VL &a,VL &b)//res=a_i(mod b_i)
{
ll x,y,k,g,c,p,res,bg;
assert(sz(a)==sz(b));
assert(sz(a)>0);
// debug(a)
// debug(b)
p=b[0];
res=a[0];
for(int i=1;i<sz(a);i++)
{
c=(a[i]-res%b[i]+b[i])%b[i];
g=exgcd(p,b[i],x,y);
bg=b[i]/g;
if(c%g!=0) return -1;
x=(x*(c/g))%bg;
res+=x*p;
p*=bg;
res=(res%p+p)%p;
}
return (res%p+p)%p;
}
};
namespace exLucas
{
ll pow2(ll a,ll b,ll p)
{
ll res=1;
while(b>0)
{
if(b&1) res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
ll inv(ll a,ll p)
{
ll g,x,y,res;
g=exgcd(a,p,x,y);
res=(g==1?(x+p)%p:-1);
assert(res!=-1);
return res;
}
map<ll,pair<VL,VL> > mp;
map<PLL,VL > fac;
void init(VL mod_list)
{
ll i,j,p;
mp.clear();
fac.clear();
for(auto mod_i:mod_list)
{
p=mod_i;
VL a,b;
for(i=2;i*i<=p;i++)
{
if(p%i) continue;
b.pb(1LL);
while(p%i==0) b[sz(b)-1]*=i,p/=i;
a.pb(i);
}
if(p>1) a.pb(p),b.pb(p);
mp[mod_i]=MP(a,b);
for(i=0;i<sz(a);i++)
{
if(fac.count(MP(a[i],b[i]))) continue;
VL fac_tmp=VL(b[i]+1);
fac_tmp[0]=1;
for(j=1;j<=b[i];j++)
{
if(j%a[i]) fac_tmp[j]=fac_tmp[j-1]*j%b[i];
else fac_tmp[j]=fac_tmp[j-1];
}
fac[MP(a[i],b[i])]=fac_tmp;
// debug(a[i],b[i])
}
}
}
ll cal_fac(ll n,ll x,ll p)
{
if(!n) return 1LL;
ll res=1;
assert(fac.count(MP(x,p)));
res=res*fac[MP(x,p)][p-1]%p;
res=pow2(res,n/p,p);
res=res*fac[MP(x,p)][n%p]%p;
return res*cal_fac(n/x,x,p)%p;
}
ll multilucas(ll n,ll m,ll x,ll p)
{
if(m>n) return 0;
ll i,cnt;
cnt=0;
for(i=n;i;i/=x) cnt+=i/x;
for(i=m;i;i/=x) cnt-=i/x;
for(i=n-m;i;i/=x) cnt-=i/x;
return pow2(x,cnt,p)* \
cal_fac(n,x,p)%p* \
inv(cal_fac(m,x,p),p)%p* \
inv(cal_fac(n-m,x,p),p)%p;
}
ll C(ll n,ll m,ll p)
{
if(m>n||m<0||n<0) return 0;
ll i,res;
VL a,b,resa;
assert(mp.count(p));
a=mp[p].fi;
b=mp[p].se;
// debug(n,m)
for(i=0;i<sz(a);i++) resa.pb(multilucas(n,m,a[i],b[i]));
res=exCRT::excrt(resa,b);
assert(res!=-1);
return res;
}
};
ll ans[MAX],val[MAX];
struct dsu
{
PII st[MAX];
int pre[MAX],top;
ll sum[MAX],res[MAX],sz[MAX];
multiset<ll> ans;
void init(int n)
{
int i;
ans.clear();
for(i=1;i<=n;i++)
{
pre[i]=i;
sz[i]=1;
sum[i]=val[i];
res[i]=exLucas::C(sum[i],sz[i],mod);
// debug(i,res[i])
ans.insert(res[i]);
}
top=0;
}
int find(int x)
{
while(x!=pre[x]) x=pre[x];
return x;
}
bool merge(int a,int b)
{
int ra,rb;
ra=find(a);
rb=find(b);
if(ra==rb) return 0;
if(sz[ra]>sz[rb]) swap(ra,rb);
pre[ra]=rb;
ans.erase(ans.find(res[ra]));
ans.erase(ans.find(res[rb]));
sz[rb]+=sz[ra];
sum[rb]=(sum[rb]+sum[ra]);
res[rb]=exLucas::C(sum[rb],sz[rb],mod);
ans.insert(res[rb]);
st[top++]=MP(ra,rb);
return 1;
}
void roll_back()
{
PII now=st[--top];
pre[now.fi]=now.fi;
ans.erase(ans.find(res[now.se]));
sz[now.se]-=sz[now.fi];
sum[now.se]=((sum[now.se]-sum[now.fi]));
assert(sum[now.se]>=0);
res[now.se]=exLucas::C(sum[now.se],sz[now.se],mod);
ans.insert(res[now.se]);
ans.insert(res[now.fi]);
}
}dsu;
PII e[MAX];
struct Segment_Tree
{
#define type int
#define ls (id<<1)
#define rs (id<<1|1)
int n,ql,qr;
type qv;
VI v[MAX<<2];
void build(int l,int r,int id)
{
v[id].clear();
if(l==r) return;
int mid=(l+r)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
}
void update(int l,int r,int id)
{
if(l>=ql&&r<=qr)
{
v[id].pb(qv);
return;
}
int mid=(l+r)>>1;
if(ql<=mid) update(l,mid,ls);
if(qr>mid) update(mid+1,r,rs);
}
void build(int _n){n=_n;build(1,n,1);}
void upd(int l,int r,type v)
{
ql=l;
qr=r;
qv=v;
update(1,n,1);
}
void dfs(int l,int r,int id)
{
int cnt=0;
for(auto it:v[id]) cnt+=dsu.merge(e[it].fi,e[it].se);
if(l==r)
{
ans[l]=*dsu.ans.rbegin();
while(cnt--) dsu.roll_back();
return;
}
int mid=(l+r)>>1;
dfs(l,mid,ls);
dfs(mid+1,r,rs);
while(cnt--) dsu.roll_back();
}
#undef type
#undef ls
#undef rs
}tr;
int l[MAX],r[MAX];
void go()
{
int n,q,i,op,tot,k;
exLucas::init(VL{4580564,1145141,100160063,102101809});
while(read(n,q,mod))
{
assert_lr(n,1,8e4);
assert_lr(q,1,8e4);
for(i=1;i<=n;i++)
{
read(val[i]);
assert_lr(val[i],0,2e9);
}
tot=0;
for(i=1;i<=q;i++)
{
read(op);
if(op==0)
{
tot++;
read(e[tot].fi,e[tot].se);
l[tot]=i;
r[tot]=q;
}
else if(op==1)
{
read(k);
assert(k>=0&&k<=tot);
assert(r[k]==q);
r[k]=i-1;
}
else assert(0);
}
tr.build(q);
for(i=1;i<=tot;i++) tr.upd(l[i],r[i],i);
dsu.init(n);
tr.dfs(1,q,1);
for(i=1;i<=q;i++) printf("%lld\n",ans[i]);
}
}F：那一片被文明糟踏过的海洋和天地
首先考虑暴力的做法，对于每个询问串，我们可以暴力扫描 4 个询问串，每次对每 4 个询问串扫描 3n 个原串，匹配算法可以使用 算法，时间复杂度
。
对于多个字符串匹配问题，我们可以想到使用 ac 自动机，考虑将 n 组串都建入到 ac 自动机里，考虑直接进行匹配，当询问串与原串都只有 1 个的时候我们可以转化成为一般的 ac 自动机问题。
以下简称 为自动机，默认在建立自动机时建立了
指针所构成的一颗树。
考虑如何处理多个原串与询问串。首先我们每组原串（3 个）在自动机上结尾节点打上相同的标记，对于一个正在进行匹配的询问串，我们可以发现在自动机上的节点一个点对应的可匹配节点是 树到 1 号点的一条链，一个暴力的想法是跳
链到 1 号点，并开一个桶，表示第
个原串是否被匹配，当然这样的复杂度是不可接受的，观察数据范围，发现 n 较小，若直接每个点开桶时间与空间复杂度都为
刚好过不去，但是超出的时间与空间复杂度又并不是很多。考虑优化，发现桶的每一位所记录的只会是 0/1 ，运用压位的思想，我们可以将 64 个 0/1 位记录在一个 unsigned long long 里面，这样时间复杂度与空间复杂度变为
。
考虑对于二进制位桶的合并，其实就是对于两个数进行一次按位或运算，复杂度同样会缩小到 。
对于第二个询问，问每组原串会被多少个询问串包含，我们可以考虑在询问串进行匹配的时候在节点上打上相同的询问串标记，一个原串能被哪些询问串包含就是 树上这个原串结尾子树内询问串的所有标记，按照
树叶子到根进行合并求解即可。
总复杂度为 在可接受范围内。
由于普通的ac自动机实现方法是需要将每条边都补全出来，由于这个是数串，所以暴力补全的想法不再适用，这时我们需要在构建 指针的时候额外进行一些处理，这里需要注意一下。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
char gc(){static char buf[1<<16],*s,*t;if(s==t){t=(s=buf)+fread(buf,1,1<<16,stdin);if(s==t)return EOF;};return *s++;}
int read()
{
char c;
int w=1;
while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
int ans=c-'0';
while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
return ans*w;
}
const int xx=5e4+5;
struct node
{
map<int,int>to;
int fail;
bitset<20001>toroot;
bitset<50001>tosubtree;
}e[xx];
int cst=1,a[xx],cnt;
int insert(int id)
{
int last=1;
for(int i=1;i<=cnt;i++)
{
if(e[last].to.find(a[i])==e[last].to.end())e[last].to[a[i]]=++cst;
last=e[last].to[a[i]];
}
e[last].toroot[id]=1;
return last;
}
vector<int>v[xx];
int n,m;
vector<int>sx;
void getfail()
{
queue<int>q;
sx.push_back(1);
for(auto it:e[1].to)
{
e[it.second].fail=1;
q.push(it.second);
}
e[1].fail=1;
while(!q.empty())
{
int x=q.front();
sx.push_back(x);
q.pop();
for(auto it:e[x].to)
{
int to=it.second,i=it.first;
int p=e[x].fail;
while(p!=1&&e[p].to.find(i)==e[p].to.end())p=e[p].fail;//特别注意与普通ac自动机不同
e[to].fail=(e[p].to.find(i)==e[p].to.end())?1:e[p].to[i];
q.push(to);
}
}
}
bitset<20001>lin;
bitset<50001>col;
signed main(){
n=read();
for(int k=1;k<=n;k++)
{
int p=3;
while(p--)
{
cnt=read();
for(int i=1;i<=cnt;i++)a[i]=read();
v[k].push_back(insert(k));
}
}
getfail();
for(int i=0;i<sx.size();i++)e[sx[i]].toroot|=e[e[sx[i]].fail].toroot;
m=read();
for(int k=1;k<=m;k++)
{
lin.reset();
int p=4;
while(p--)
{
cnt=read();
for(int i=1;i<=cnt;i++)a[i]=read();
int last=1;
for(int i=1;i<=cnt;i++)
{
while(last!=1&&e[last].to.find(a[i])==e[last].to.end())last=e[last].fail;
if(e[last].to.find(a[i])==e[last].to.end())last=1;
else last=e[last].to[a[i]];
e[last].tosubtree[k]=1;
lin|=e[last].toroot;
}
}
cout<<lin.count()<<"\n";
}
for(int i=sx.size()-1;i>=0;i--)e[e[sx[i]].fail].tosubtree|=e[sx[i]].tosubtree;
for(int i=1;i<=n;i++)
{
col.reset();
for(int j=0;j<v[i].size();j++)col|=e[v[i][j]].tosubtree;
cout<<col.count()<<" \n"[i==n];
}
return 0;
}
/*
3 4
3 1 2 3
2 7 8
1 9
1 56
2 1 2
3 1 2 5
4 5 4 1 4
1 6
1 7
4 1 2 3 4
2 8 9
1 7
1 114
4 7 8 9 1
2 8 6
1 9982
1 514
3 3 2 1
3 2 3 1
3 7 7 7
3 8 8 8
1 56
3 1 2 5
1 114
1 514
3 (1 2 3)
2 (1 3)
1 (3)
1 (2)
2 2 3
*/
全部评论
(0) 回帖