4C(容斥)
http://noi.ac/contest/56/problem/25
同时交换一行或一列对答案显然没有影响，于是将行列均从大到小排序，每次处理限制相同的一段行列（呈一个L形）。
问题变成，决定这个L形中每个位置的高度，是每个位置都不超出所在行列的限制，且每行每列都有至少一个位置达到最高限制。
容斥，暴力枚举有多少行多少列没有任何一个位置达到最高限制，这些行列中的位置都只能取到0~h。其余L形中的位置都无限制，即能取到0~h+1。
#include<cstdio> #include<algorithm> #define rep(i,l,r) for (int i=(l); i<=(r); i++) using namespace std; ,mod=1e9+; ; int ksm(int a,int b){ ; ) ) res=1ll*res*a%mod; return res; } bool cmp(int a,int b){ return a>b; } int main(){ scanf(][]=; rep(i,,N-){ C[i][]=; rep(j,,i) C[i][j]=(C[i-][j]+C[i-][j-])%mod; } rep(i,,n) scanf(,a+n+,cmp); rep(i,,m) scanf(,b+m+,cmp); a[n+]=b[m+]=-; ,y=; x<n||y<m; ){ ],b[y+]),xx=x,yy=y,ans=; ]==h) ++x; ]==h) ++y; rep(i,,x-xx) rep(j,,y-yy){ int S1=(x-i)*(y-j)-xx*yy,S2=x*y-S1-xx*yy; ,S1)%mod*ksm(h,S2)%mod; ) ans=(ans-res+mod)%mod; else ans=(ans+res)%mod; } Ans=1ll*Ans*ans%mod; } printf("%d\n",Ans); ; }
5A(杜教筛)
$$\begin{align*}
&\ \ \ \ \sum_{k=1}^{n}\sum_{i=1}^{k}\sum_{j=1}^{k}(i,j,k)\\
&=\sum_{p=1}^{n}p\sum_{k=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{i=1}^{k}\sum_{j=1}^{k}[(i,j,k)=1]\\
&=\sum_{p=1}^{n}p\sum_{k=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{i=1}^{k}\sum_{j=1}^{k}\sum_{d|i,d|j,d|k}\mu(d)\\
&=\sum_{p=1}^{n}p\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\sum_{k=1}^{\lfloor\frac{n}{pd}\rfloor}\sum_{i=1}^{k}\sum_{j=1}^{k}1\\
&=\sum_{p=1}^{n}p\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)f(\lfloor\frac{n}{pd}\rfloor)\\
&=\sum_{T=1}^{n}f(\lfloor\frac{n}{T}\rfloor)\sum_{d|T}\mu(d)\cdot\frac{T}{d}\\
&=\sum_{T=1}^{n}f(\lfloor\frac{n}{T}\rfloor)\varphi(T)
\end{align*}$$
其中$f(n)=\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}$，最后一步是根据$id*\mu=\varphi$得到的。
观察这个式子发现可以根号加速，$\varphi$的前缀和用杜教筛求出。通过记忆化能做到玄学复杂度。
#include<cstdio> #include<cstring> #include<algorithm> #define rep(i,l,r) for (int i=(l); i<=(r); i++) using namespace std; ; ,inv,b[N],p[N],tot,phi[N],Phi[N],ans; int ksm(int a,int b){ ; ) ) res=1ll*res*a%mod; return res; } )%mod*(x+x+)%mod*inv%mod; } void init(int n){ rep(i,,n){ ; ; i*p[j]<=n; ++j){ b[i*p[j]]=; ); else { phi[i*p[j]]=phi[i]*p[j]; break; } } } } int P(int x){ if (x<=m) return phi[x]; if (~Phi[n/x]) return Phi[n/x]; ; ,j; i<=x; i=j+) j=x/(x/i),res=(res+1ll*(j-i+)*P(x/i))%mod; res=((1ll*x*(x+)>>)-res+mod)%mod; return Phi[n/x]=res; } int main(){ freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf(,mod-); phi[]=; init(m); rep(i,,m) phi[i]=(phi[i]+phi[i-])%mod; memset(Phi,-,sizeof(Phi)); ,j; i<=n; i=j+) j=n/(n/i),ans=(ans+1ll*(P(j)-P(i-)+mod)*S(n/i))%mod; printf("%d\n",ans); ; }
5B(后缀树DP)
http://noi.ac/contest/57/problem/18
最优策略显然是，每次根据已知部分，估计出对方下一步最有可能出什么，再以此决定出拳。
将串反序建出原串的后缀树，再在后缀树上DP即可。用id存下子串第一次出现的位置。转移显然。
#include<cstdio> #include<vector> #include<cstring> #include<algorithm> #define rep(i,l,r) for (int i=(l); i<=(r); i++) typedef long long ll; using namespace std; ; char s[N]; ,w[N],d[N],a[N],lst,rt,mx[N],son[N][],fa[N],id[N]; vector<int>Son[N]; ll sw[N],f[N]; void ext(int c,int x){ ; id[np]=x; while (p && !son[p][c]) son[p][c]=np,p=fa[p]; ; return; } int q=son[p][c]; ) { fa[np]=q; return; } ; son[nq][]=son[q][]; son[nq][]=son[q][]; son[nq][]=son[q][]; fa[nq]=fa[q]; fa[q]=fa[np]=nq; while (p && son[p][c]==q) son[p][c]=nq,p=fa[p]; } || (y==&&x==)) ? w[z] : (((x-y+)%==) ? d[z] : ); } void dfs(int x){ ; rep(i,,ed) dfs(Son[x][i]),id[x]=id[Son[x][i]]; if (mx[x]>=n) return; rep(j,,){ ll res=1ll<<; rep(i,,ed){ int y=Son[x][i],op=a[id[y]+mx[x]]; res=min(res,sw[min(mx[y],n)]-sw[mx[x]+]+f[y]+calc(j,op,mx[x]+)); } f[x]=max(f[x],res); } } int main(){ scanf(); rep(i,,n) a[i]=(s[i]==:(s[i]==:); rep(i,,n) scanf(]+w[i]; *n; i; i--) ext(a[i],i); rep(i,,nd) Son[fa[i]].push_back(i); dfs(); printf(]); ; }
6B(2-SAT)
http://noi.ac/contest/58/problem/24
每只蚯蚓建n个点，点v[i][j]表示蚯蚓i是否位于节点j的子树内。
2-SAT建图，边数为$O(mn^2+qn)$。
#include<cstdio> #include<algorithm> #define rep(i,l,r) for (int i=(l); i<=(r); i++) using namespace std; ,M=; ][]; int cnt,scc,top,hd[N],v[M],nxt[M],low[N],dfn[N],stk[N],inq[N],bel[N]; void adde(int x,int y){ V[++tot]=y,Nxt[tot]=Hd[x],Hd[x]=tot; } void add(int x,int y){ v[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt; x^=,y^=; v[++cnt]=x,nxt[cnt]=hd[y],hd[y]=cnt; } void dfs(int u,int f){ fa[u]=f,dep[u]=dep[f]+,L[u]=++tim; for(int i=Hd[u];i;i=Nxt[i]) if(V[i]!=f) dfs(V[i],u); R[u]=tim; } void tarjan(int u){ dfn[u]=low[u]=++tim; stk[++top]=u,inq[u]=; for(int i=hd[u];i;i=nxt[i]) if (!dfn[v[i]]) tarjan(v[i]),low[u]=min(low[u],low[v[i]]); else if(inq[v[i]])low[u]=min(low[u],dfn[v[i]]); if(dfn[u]==low[u]){ int x=tot; scc++; ; } } int main(){ scanf("%d%d%d",&n,&m,&Q); rep(i,,n) scanf("%d%d",&x,&y),adde(x,y),adde(y,x); dfs(,); tot=; rep(i,,m) rep(j,,n) id[i][j]=tot,tot+=; rep(i,,m){ add(id[i][]^,id[i][]); rep(j,,n) add(id[i][j],id[i][fa[j]]); rep(j,,n) rep(k,j+,n) if((L[j]<L[k]||L[j]>R[k])&&(L[k]<L[j]||L[k]>R[j])) add(id[i][j],id[i][k]^); } while(Q--){ scanf("%d%d%d",&x,&y,&z); for (int i=Hd[z];i;i=Nxt[i]) ); ) add(id[x][z]^,id[y][z]); } tim=; rep(i,,tot-) if (!dfn[i]) tarjan(i); rep(i,,m){ ; rep(j,,n) ]) ret=dep[j]>dep[ret]?j:ret; printf("%d ",ret); } ; }
