【省选模拟】20/05/04

• ：合法的连边出来是个二分图，问题转换为每个点有一个最大经过次数的限制，每一步只能走到相邻点，问先手必胜的点
• 这是一个二分图博弈问题，一个简单的版本是一个点只能经过一次，那么有结论，可能不在最大匹配上的点必败，可能不在指的是存在一个最大匹配没有它存在，因为考虑这个最大匹配，当前点走到的任意点一定在最大匹配上，那么后手可以顺着最大匹配走，并且最后走到先手的集合，如果走到后手的集合那么就找到了增广路，最大匹配会变大，暴力 是删点考虑再做一次，快速 是找到不在当前最大匹配的点，考虑从它开始找一条增广路把最大匹配拆掉，增广路的末尾也可以不在最大匹配中
• 这道题考虑假装拆一下点，那么必胜当且仅当没有这个点没有满配，网络流即可

#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
typedef long long ll;
cs int N = 550, M = N * N << 2;
cs ll INF = 1e16;
int n; ll a[N]; int b[N];
cs int K = 1e6 + 50;
vector<int> prm; bool isp[K];
void linear_sieve(int n){
for(int i=2; i<=n; i++){
if(!isp[i]) prm.pb(i);
for(int c : prm) if(c*i>n) break;
else{ isp[c*i]=true; if(i%c==0) break; }
}
}
ll mul(ll a, ll b, ll mod){ return (a*b-(ll)((long double)a/mod*b)*mod+mod)%mod; }
ll ksm(ll a, ll b, ll mod){
ll as=1; for(;b;b>>=1,a=mul(a,a,mod))
if(b&1) as=mul(as,a,mod); return as;
}
bool miller(ll a){
if(a<=1e6) return !isp[a];
if(a&1^1) return false;
static int c[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
for(int T=5;T;T--){
int p=c[rand()&15];
ll x=a-1, y=0; while(x&1^1) x>>=1,++y;
ll now=ksm(p,x,a);
for(int i=0; i<y; i++){
ll nxt=mul(now,now,a);
if(nxt==1&&(now!=1&&now!=a-1)) return false;
now=nxt; if(now==1) break;
} if(now!=1) return false;
} return true;
}
int fi[N], nxt[M], to[M], ec; ll w[M];
int S, T, c[N];
void adde(int x, int y, ll z){
nxt[++ec]=fi[x], fi[x]=ec, to[ec]=y, w[ec]=z;
nxt[++ec]=fi[y], fi[y]=ec, to[ec]=x, w[ec]=0;
} bool as[N]; int d[N];
bool bfs(){
memset(d,-1,sizeof(int)*(T+1));
queue<int> q; q.push(S); d[S]=0;
while(!q.empty()){
int x=q.front(); q.pop();
for(int e=fi[x];e;e=nxt[e]) if(w[e]){
int v=to[e]; if(d[v]==-1)
d[v]=d[x]+1, q.push(v);
if(v==T) return true;
}
} return false;
}
ll dfs(int u, ll flw){
if(u==T) return flw; ll as=0;
for(int e=fi[u];e;e=nxt[e]) if(d[to[e]]==d[u]+1){
int v=to[e]; ll dlt=dfs(v,min(flw,w[e]));
w[e]-=dlt; w[e^1]+=dlt; as+=dlt; flw-=dlt;
if(!flw) break;
} if(flw) d[u]=-1; return as;
}
void dinic(){ ll as=0; while(bfs()) as+=dfs(S,INF); } bool vis[N];
void work(int u){
if(vis[u]) return; vis[u] = true;
for(int e=fi[u];e;e=nxt[e]){
int v=to[e]; if(v==S||v==T) continue;
for(int o=fi[v];o;o=nxt[o])
if(w[o^c[v]^1]&&!as[to[o]]&&to[o]!=S&&to[o]!=T)
as[to[o]]=true, work(to[o]);
}
} vector<int> G[N];
void col(int u, int co=0){ if(~c[u]) return; c[u]=co; for(int v:G[u]) col(v,co^1); }
void Main(){
scanf("%d",&n); T=n+1;
memset(fi,0,sizeof(int)*(T+1)); ec=1;
memset(vis,0,sizeof(bool)*(n+1));
for(int i=1; i<=n; i++){
G[i].clear();
scanf("%lld%d",&a[i],&b[i]); c[i]=-1; as[i]=0;
for(int j=1; j<i; j++){
ll x=a[i], y=a[j]; if(x>y) swap(x,y);
if(y%x||!miller(y/x)) continue; G[i].pb(j); G[j].pb(i);
}
}
for(int i=1; i<=n; i++) if(c[i]==-1) col(i,0);
for(int i=1; i<=n; i++){
if(c[i]) adde(i,T,b[i]);
else adde(S,i,b[i]);
if(!c[i]) for(int v:G[i]) adde(i,v,INF);
} dinic();
for(int i=1; i<=n; i++){
if(c[i]){
for(int e=fi[i];e;e=nxt[e])
if(to[e]==T&&w[e]) as[i]=true;
} else{
for(int e=fi[i];e;e=nxt[e])
if(to[e]==S&&w[e^1]) as[i]=true;
}
} for(int i=1; i<=n; i++) if(as[i]) work(i); int ct=0;
for(int i=1; i<=n; i++) if(as[i]) ++ct; if(!ct) return puts("-1"),void();
for(int i=1; i<=n; i++) if(as[i]) cout<<a[i]<<" "; puts("");
}
signed main(){
#ifdef FSYolanda
freopen("1.in","r",stdin);
#endif
int T; scanf("%d",&T); linear_sieve(1e6);
while(T--) Main(); return 0;
}

• ：暴力，需要统计一个置换下的三种匹配情况：
  在一个循环中出现，在循环的前缀后缀出现，出现在多个循环拼接起来
  长度很小的时候后两种可以单独算，第一种用矩阵乘法 +
  第二种，长度很长的时候，钦定一个前缀后缀，从起点开始做一圈做到钦定的后缀前面并且强制现在不匹配，那么这种情况只会算到只有当前前后缀匹配的情况，复杂度

#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
typedef unsigned long long ull;
cs int Mod = 1e9 + 7;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }
int dec(int a, int b){ return a - b < 0 ? a - b + Mod : a - b; }
int mul(int a, int b){ return 1ll * a * b % Mod; }
void Add(int &a, int b){ a = add(a,b); }
void Mul(int &a, int b){ a = mul(a,b); }
void Dec(int &a, int b){ a = dec(a,b); }
int ksm(int a, int b){ int as=1; for(;b;b>>=1,Mul(a,a)) if(b&1) Mul(as,a); return as; }
cs int N = 32, M = 5e4 + 50, T = 1e3;
int n, m; char S[N];
bool isp[M]; vector<int> prm;
void linear_sieve(int n){
for(int i=2; i<=n; i++){
if(!isp[i]) prm.pb(i);
for(int c:prm) if(c*i>n) break;
else{ isp[i*c]=true; if(i%c==0) break; }
}
}
int phi(int n){
int x=n; for(int p : prm){
if(p*p>n) break;
if(n%p==0){ x=x/p*(p-1); while(n%p==0) n/=p; }
} if(n>1) x=x/n*(n-1); return x;
}
struct mat{
int a[N][N];
mat(){ memset(a,0,sizeof(a)); }
void I(){ for(int i=0; i<=m; i++) a[i][i]=1; }
mat operator * (cs mat &A){
mat B; for(int i=0; i<=m; i++)
for(int j=0; j<=m; j++){
ull as = 0;
for(int k=0; k<=m; k++) as+=(ull)a[i][k]*A.a[k][j];
B.a[i][j]=as%Mod;
} return B;
}
}A[T+1],B[T+1],C[T+1];
struct vec{
int a[N];
vec(){ memset(a,0,sizeof(a)); }
vec operator * (cs mat &A){
vec B; for(int i=0; i<=m; i++){
ull as = 0;
for(int j=0; j<=m; j++) as+=(ull)a[j]*A.a[j][i];
B.a[i]=as%Mod;
} return B;
}
};
int nxt[N], trs[N][2], R;
void pre_work(){
for(int i=1,j=0; i<=m; i++){
j=trs[nxt[i-1]][S[i]-'A'];
nxt[i]=j; trs[i-1][S[i]-'A']=i;
trs[i][0]=trs[j][0];
trs[i][1]=trs[j][1];
} R=m-nxt[m];
trs[m][0]=trs[m][1]=m;
A[0].I();
for(int i=0; i<=m; i++){
A[1].a[i][trs[i][0]]++;
A[1].a[i][trs[i][1]]++;
} for(int i=2; i<=T; i++) A[i]=A[i-1]*A[1];
B[0].I(); B[1]=A[T];
for(int i=2; i<=T; i++) B[i]=B[i-1]*B[1];
C[0].I(); C[1]=B[T];
for(int i=2; i<=T; i++) C[i]=C[i-1]*C[1];
}
vec Get(vec now, int t){
now = now * A[t%T]; t /= T;
now = now * B[t%T]; t /= T;
now = now * C[t]; return now;
}
int fir_work(int t){
if(t<m) return 0; vec now; now.a[0]=1;
now=Get(now,t); return now.a[m];
}
int sec_work(int t){
if(t<=m){
static int a[N]; int as = 0;
for(int u=1; u<m; u++){
if(u>t || m-u>t) continue;
bool ok = true;
for(int i=1; i<=m; i++) a[i]=-1;
for(int i=1,r=t-u+1; i<=u; i++,r++) a[r]=S[i]-'A';
for(int i=1,r=u+1; i<=m-u; i++, r++){
if(~a[i]&&a[i]!=S[r]-'A'){ ok = false; break; }
a[i]=S[r]-'A';
}
if(ok){
if(t<m) ++as;
else{ int u=0; for(int i=1; i<=t; i++) u=trs[u][a[i]]; as+=(u!=m); }
}
} return as;
}
int as = 0;
for(int u=1; u<m; u++){
vec pr[2]; pr[0].a[0]=1; int now=0, nxt=1;
for(int i=m-u; i<m; i++){
for(int j=0; j<=m; j++) pr[nxt].a[j]=0;
for(int j=0; j<=m; j++) if(pr[now].a[j])
Add(pr[nxt].a[trs[j][S[i+1]-'A']], pr[now].a[j]);
swap(now,nxt);
}
pr[now]=Get(pr[now],t-m);
for(int i=0; i<m-u; i++){
for(int j=0; j<=m; j++) pr[nxt].a[j]=0;
for(int j=0; j<=m; j++) if(pr[now].a[j])
Add(pr[nxt].a[trs[j][S[i+1]-'A']], pr[now].a[j]);
swap(now,nxt);
}
for(int i=m-u; i<m-1; i++){
for(int j=0; j<=m; j++) pr[nxt].a[j]=0;
for(int j=0; j<=m; j++) if(pr[now].a[j])
Add(pr[nxt].a[trs[j][S[i+1]-'A']], pr[now].a[j]);
swap(now,nxt);
}
for(int i=0; i<m; i++) Add(as,pr[now].a[i]);
} return as;
}
int thr_work(int t){
if(m<=t) return 0;
static int a[N]; int as=0;
for(int u=1; u<=m; u++){
#define idx(x) (x>m?x-m:x)
for(int i=1; i<=t; i++) a[i]=S[idx(i+u-1)]-'A'; bool ok = true;
#undef idx(x)
for(int i=1,nx=(t-u+2)%t; i<=m; i++,nx=(nx+1)>t?1:nx+1)
if(a[nx]!=S[i]-'A'){ ok = false; break; }
if(ok){
int nd=0;
for(int i=1; i<=t+t; i++)
nd=trs[nd][a[i>t?i-t:i]]; as+=(nd!=m);
}
} return as;
}
int work(int t){
int as = 0; Add(as, fir_work(t));
Add(as, sec_work(t)); Add(as, thr_work(t));
return as;
}
int main(){
#ifdef FSYolanda
freopen("1.in","r",stdin);
#endif
scanf("%d%s",&n,S+1);
linear_sieve(sqrt(n));
m=strlen(S+1); vector<int> fac;
if(n<m) return puts("0"),0;
for(int i=1; i*i<=n; i++) if(n%i==0){
fac.pb(i); if(i*i!=n) fac.pb(n/i);
} int as = 0; pre_work();
for(int t : fac) Add(as,mul(phi(n/t),work(t)));
cout<<mul(as,ksm(n,Mod-2)); return 0;
}