怕不是我再不写题解这题就该成没人做也没人会的千古谜题了......
T1:
仔细分析题面，发现相同就是广义SAM上节点相同，相似就是广义SAM上为从根到某个点路径的前缀。、
直接SAM上跑从根开始，每个点下界为1的最小流即可。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#define debug cout
using namespace std;
const int maxn=5e3+1e2;
const int inf=0x3f3f3f3f; int in[maxn],n,ans,sum; namespace NetworkFlow {
int s[maxn<<],t[maxn<<],nxt[maxn<<],f[maxn<<],dep[maxn<<],deg[maxn<<],cnt=;
int bak[maxn<<],bcnt;
int st,ed,_s,_t;
inline void coredge(int from,int to,int flow) {
t[++cnt] = to , f[cnt] = flow ,
nxt[cnt] = s[from] , s[from] = cnt;
}
inline void singledge(int from,int to,int flow) {
coredge(from,to,flow) , coredge(to,from,);
}
inline bool bfs() {
memset(dep,-,sizeof(dep)) , dep[st] = ;
queue<int> q; q.push(st);
while( q.size() ) {
const int pos = q.front(); q.pop();
for(int at=s[pos];at;at=nxt[at])
if( f[at] && !~dep[t[at]] ) {
dep[t[at]] = dep[pos] + , q.push(t[at]);
}
}
return ~dep[ed];
}
inline int dfs(int pos,int flow) {
if( pos == ed ) return flow;
int ret = , now = ;
for(int at=s[pos];at;at=nxt[at])
if( f[at] && dep[t[at]] > dep[pos] ) {
now = dfs(t[at],min(flow,f[at])) ,
ret += now , flow -= now ,
f[at] -= now , f[at^] += now;
if( !flow ) return ret;
}
if( !ret ) dep[pos] = -;
return ret;
}
inline int dinic() {
int ret = , now = ;
while( bfs() ) {
while( ( now = dfs(st,inf) ) )
ret += now;
}
return ret;
}
inline int findflow() {
for(int at=s[_t];at;at=nxt[at])
if( t[at] == _s ) return f[at^];
}
inline void backup() {
memcpy(bak,s,sizeof(s)) , bcnt = cnt;
}
inline void restore() {
memcpy(s,bak,sizeof(bak)) , cnt = bcnt;
}
} namespace SAM {
map<int,int> ch[maxn<<];
int fa[maxn<<],len[maxn<<],root,last,cnt; inline int NewNode(int ll) {
len[++cnt] = ll;
return cnt;
}
inline void extend(int x) {
int p = last;
int np = NewNode(len[p]+);
while( p && ch[p].find(x) == ch[p].end() ) ch[p][x] = np , p = fa[p];
if( !p ) fa[np] = root;
else {
int q = ch[p][x];
if( len[q] == len[p] + ) fa[np] = q;
else {
int nq = NewNode(len[p]+);
ch[nq] = ch[q] , fa[nq] = fa[q];
fa[np] = fa[q] = nq;
while( p && ch[p][x] == q ) ch[p][x] = nq , p = fa[p];
}
}
last = np;
}
inline void Ex_extend(int* sou,int li) {
last = root;
for(int i=;i<=li;i++) {
if( ch[last].find(sou[i]) != ch[last].end() ) last = ch[last][sou[i]];
else extend(sou[i]);
}
}
} inline void build() {
using SAM::ch;using SAM::cnt;
using namespace NetworkFlow;
_s = cnt * + , _t = _s + , st = _t + , ed = st + ;
#define cov(x) (x+cnt)
for(int i=;i<=cnt;i++) {
if( i != ) ++deg[i] , --deg[cov(i)];
for(map<int,int>::iterator it=ch[i].begin();it!=ch[i].end();it++) {
const int tar = it->second;
if( i == ) singledge(_s,tar,);
else singledge(cov(i),tar,);
}
if( i != ) singledge(cov(i),_t,);
}
backup();
for(int i=;i<=_t;i++) {
if( !deg[i] ) continue;
if( deg[i] > ) singledge(i,ed,deg[i]) , sum += deg[i];
else singledge(st,i,-deg[i]);
}
singledge(_t,_s,inf);
}
inline int getans() {
using namespace NetworkFlow;
int d = dinic();
if( d != sum ) return -; // No solution .
int ret = findflow();
restore();
st = _t , ed = _s;
int dd = dinic();
return ret - dd;
} int main() {
static int m;
SAM::root = SAM::NewNode();
scanf("%d",&m);
while(m--) {
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",in+i);
SAM::Ex_extend(in,n);
}
build();
ans = getans();
printf("%d\n",ans);
return ;
}
T2:
观察操作数量特点，发现可持久化块状数组可过。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e6+1e2,maxb=1e3,maxu=1e4+1e2,maxr=1e5+1e2; inline int* NewArray() {
static const int maxu = 1e4 + 1e3 + ;
static int dat[maxu][maxb],cnt;
return dat[cnt++];
} struct PersistentBlockedArray {
int* p[maxb];
inline void insert(int pos,int x) { // insert into this array .
if( !p[pos/maxb] ) p[pos/maxb] = NewArray();
p[pos/maxb][pos%maxb] = x;
}
inline void modify(int pos,int x) {
int* t = NewArray();
memcpy(t,p[pos/maxb],sizeof(int)*maxb);
t[pos%maxb] = x , p[pos/maxb] = t;
}
inline int query(int pos) {
return p[pos/maxb][pos%maxb];
}
}dat[maxu]; int ptr[maxu+maxr],now,cnt; inline void roll(int tar) {
ptr[++now] = ptr[tar];
}
inline void modify(int pos,int x) {
dat[++cnt] = dat[ptr[now]] , ptr[now] = cnt;
dat[ptr[now]].modify(pos,x);
}
inline int query(int pos) {
return dat[ptr[now]].query(pos);
} namespace IO {
const int BS = << ;
char ibuf[BS],obuf[BS],*ist,*ied,*oed=obuf;
inline char nextchar() {
if( ist == ied ) ied = ibuf + fread(ist=ibuf,,BS,stdin);
return ist == ied ? - : *ist++;
}
inline int getint() {
int ret = , ch;
while( !isdigit(ch=nextchar()) );
do ret=ret*+ch-''; while( isdigit(ch=nextchar()) );
return ret;
}
inline void getstr(char* s) {
char ch;
while( !isalpha(ch=nextchar()) ) ;
do *s++=ch; while( isalpha(ch=nextchar()) );
}
inline void flush() {
//cerr<<"in flush delta = "<<oed-obuf<<endl;
fwrite(obuf,,oed-obuf,stdout) , oed = obuf;
}
inline void printchar(const char &x) {
*oed++ = x;
//cerr<<"delta = "<<oed-obuf<<endl;
if( oed == obuf + BS ) flush();
}
inline void printint(int x) {
//cerr<<"x = "<<x<<endl;
static int stk[],top;
if( !x ) printchar('');
else {
top = ;
while(x) stk[++top] = x % , x /= ;
while(top) printchar(''+stk[top--]);
}
printchar('\n');
}
}
using IO::getint;
using IO::printint;
using IO::getstr;
using IO::flush; int main() {
static int n,m,lastans,ope;
static char o[];
n = getint() , m = getint();
for(int i=,x;i<n;i++) x = getint() , dat[].insert(i,x);
for(int i=,p,x,t;i<=m;i++) {
getstr(o);
if( *o == 'Q' ) {
p = ( getint() ^ lastans ) % n;
printint(lastans=query(p));
} else if( *o == 'M' ) {
++ope , p = ( getint() ^ lastans ) % n , x = getint();
modify(p,x);
} else if( *o == 'R' ) {
++ope , t = ( getint() ^ lastans ) % ope;
roll(t);
}
}
flush();
return ;
}
T3:
大力反演出phi，后面的sigma(i^k)显然是k+1次多项式，拉格朗日插值即可。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define debug cout
#define bool unsigned char
typedef long long int lli;
using namespace std;
const int maxn=1e6+1e2,lim=1e6,maxk=1e3+1e1;
const int mod=1e9+; int n,k; namespace Sieve {
lli sum[maxn],mem[maxn];
bool vis[maxn]; inline void pre() {
static int prime[maxn/],cnt;
static bool vis[maxn];
sum[] = ;
for(int i=;i<=lim;i++) {
if( !vis[i] ) prime[++cnt] = i , sum[i] = i - ;
for(int j=;j<=cnt&&(lli)i*prime[j]<=lim;j++) {
const int tar = i * prime[j];
vis[tar] = ;
if( i % prime[j] ) sum[tar] = sum[i] * ( prime[j] - );
else {
sum[tar] = sum[i] * prime[j];
break;
}
}
}
for(int i=;i<=lim;i++) sum[i] = ( sum[i] + sum[i-] ) % mod;
}
inline lli getphi(lli x) {
if( x <= lim ) return sum[x];
const lli t = n / x;
if( vis[t] ) return mem[t];
lli& ret = mem[t]; ret = x * ( x + ) >> , vis[t] = ;
for(lli i=,j;i<=x;i=j+) {
j = x / ( x / i );
ret -= ( j - i + ) * getphi(x/i) % mod , ret %= mod;
}
return ret = ( ret % mod + mod ) % mod;
}
} namespace Inter {
lli in[maxk],fac[maxk],facrev[maxk],pprv[maxk],ssuf[maxk],*prv=pprv+,*suf=ssuf+;
inline lli fastpow(lli base,int tim) {
lli ret = ;
while(tim) {
if( tim & ) ret = ret * base % mod;
if( tim >>= ) base = base * base % mod;
}
return ret;
}
inline void init() {
for(int i=;i<k;i++) in[i] = fastpow(i,k-);
for(int i=;i<k;i++) in[i] = ( in[i] + in[i-] ) % mod;
}
inline lli getmul(int p) {
return p ? fac[p] * facrev[k-p-] % mod : facrev[k-];
}
inline lli getval(lli x) {
lli ret = ;
prv[-] = ;
for(int i=;i<k;i++) prv[i] = prv[i-] * (x-i+mod) % mod;
suf[k] = ;
for(int i=k-;~i;i--) suf[i] = suf[i+] * (x-i+mod) % mod;
for(int i=;i<k;i++) {
lli now = prv[i-] * suf[i+] % mod;
ret = ret + now * in[i] % mod * getmul(i) % mod , ret %= mod;
}
return ret;
}
inline void getinv() {
static lli inv[maxn];
*fac = ;
for(int i=;i<=k;i++) fac[i] = fac[i-] * i % mod;
inv[k] = fastpow(fac[k],mod-);
for(int i=k;i;i--) inv[i-] = inv[i] * i % mod;
for(int i=;i<=k;i++) inv[i] = inv[i] * fac[i-] % mod;
for(int i=;i<=k;i++) fac[i] = fac[i-] * inv[i] % mod;
facrev[] = ;
for(int i=;i<=k;i++) facrev[i] = facrev[i-] * ( mod - inv[i] ) % mod;
}
}
inline lli segphi(lli l,lli r) {
return ( Sieve::getphi(r) - Sieve::getphi(l-) + mod ) % mod;
} inline lli calc(lli n) {
lli ret = ;
for(lli i=,j;i<=n;i=j+) {
j = n / ( n / i );
ret += segphi(i,j) % mod * Inter::getval(n/i) % mod , ret %= mod;
}
return ret;
} int main() {
scanf("%d%d",&n,&k) , k += , Sieve::pre() , Inter::init() , Inter::getinv();
printf("%lld\n",calc(n));
return ;
}
当然那个RYOI是什么意思？就不告诉你！