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);
}
;
}