【省选模拟】20/05/04

【省选模拟】20/05/04

#include#define cs const#define pb push_backusing 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 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 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 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; jy) 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<

#include#define cs const#define pb push_backusing 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 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(tt || 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(tm?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 fac; if(n

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。