https://tdpc.contest.atcoder.jp/assignments
N
简单的树形DP，把加边转化成加点，组合数简单算一下。
CO int N=1e3+10;
int fac[N],ifac[N];
vector<int> to[N];
int siz[N],dp[N];
void dfs(int u,int fa){
siz[u]=1;
for(int v:to[u])if(v!=fa){
dfs(v,u);
siz[u]+=siz[v];
}
dp[u]=fac[siz[u]-1];
for(int v:to[u])if(v!=fa)
dp[u]=mul(dp[u],mul(dp[v],ifac[siz[v]]));
}
int main(){
int n=read<int>();
fac[0]=1;
for(int i=1;i<=n;++i) fac[i]=mul(fac[i-1],i);
ifac[n]=fpow(fac[n],mod-2);
for(int i=n-1;i>=0;--i) ifac[i]=mul(ifac[i+1],i+1);
for(int i=1;i<n;++i){
int u=read<int>(),v=read<int>();
to[u].push_back(v),to[v].push_back(u);
}
int ans=0;
for(int i=1;i<=n;++i){
dfs(i,0);
ans=add(ans,dp[i]);
}
printf("%d
",mul(ans,ifac[2]));
return 0;
}
O
插空法的运用。
int a[27],s[27];
int fac[261],ifac[261];
int dp[27][261],cnt[11][11];
IN int binom(int n,int m){
return mul(fac[n],mul(ifac[m],ifac[n-m]));
}
void dfs(int x,int s){
++cnt[s][x];
for(int i=1;i<=10-s;++i) dfs(x+1,s+i);
}
int main(){
int n=0;
for(int i=1;i<=26;++i)if(read(a[i])){
a[++n]=a[i];
s[n]=s[n-1]+a[n];
}
fac[0]=1;
for(int i=1;i<=260;++i) fac[i]=mul(fac[i-1],i);
ifac[260]=fpow(fac[260],mod-2);
for(int i=259;i>=0;--i) ifac[i]=mul(ifac[i+1],i+1);
dfs(0,0);
dp[0][0]=1;
for(int i=0;i<n;++i)for(int j=0;j<=s[i];++j)if(dp[i][j]){
for(int k=1;k<=a[i+1];++k)if(k<=s[i]+1){
for(int x=0;x<=k;++x)if(x<=j and k-x<=s[i]+1-j)
dp[i+1][j-x+a[i+1]-k]=add(dp[i+1][j-x+a[i+1]-k],
mul(dp[i][j],mul(cnt[a[i+1]][k],mul(binom(s[i]+1-j,k-x),binom(j,x)))));
}
}
printf("%d
",dp[n][0]);
return 0;
}
P
选不相交的链。DP状态同 林克卡特树。
CO int N=1e3+10;
int K;
vector<int> to[N];
int dp[N][51][3],tmp[51][3];
void dfs(int u,int fa){
dp[u][0][0]=1;
for(int v:to[u])if(v!=fa){
dfs(v,u);
for(int i=0;i<=K;++i) fill(tmp[i],tmp[i]+3,0);
for(int i=0;i<=K;++i){
for(int j=0;j<=i;++j){
tmp[i][0]=add(tmp[i][0],
mul(dp[u][j][0],add(dp[v][i-j][0],add(dp[v][i-j][1],dp[v][i-j][2])))
);
tmp[i][1]=add(tmp[i][1],add(
mul(dp[u][j][0],add(i-j-1>=0?dp[v][i-j-1][0]:0,dp[v][i-j][1])),
mul(dp[u][j][1],add(dp[v][i-j][0],add(dp[v][i-j][1],dp[v][i-j][2])))
));
tmp[i][2]=add(tmp[i][2],add(
mul(dp[u][j][1],add(dp[v][i-j][0],i-j+1<=K?dp[v][i-j+1][1]:0)),
mul(dp[u][j][2],add(dp[v][i-j][0],add(dp[v][i-j][1],dp[v][i-j][2])))
));
}
}
for(int i=0;i<=K;++i) copy(tmp[i],tmp[i]+3,dp[u][i]);
}
}
int main(){
int n=read<int>();
read(K);
for(int i=1;i<n;++i){
int u=read<int>(),v=read<int>();
to[u].push_back(v),to[v].push_back(u);
}
dfs(1,0);
printf("%d
",add(dp[1][K][0],add(dp[1][K][1],dp[1][K][2])));
return 0;
}
Q
为了不重复只能加01字符。
为了知道是否成段需要记录结束位置。
但是这样没法转移。可以再存一个AC自动机状态，也可以再存末7位的数。可以发现结束位置需要记录8位。
https://suikaba.hatenablog.com/entry/2017/08/27/181249
mask：
int w[9][1<<8];
int pre[1<<7][1<<8][2];
int dp[101][1<<7][1<<8];
int main(){
int n=read<int>(),L=read<int>();
for(int i=1;i<=n;++i){
static char s[9];scanf("%s",s);
int len=strlen(s);
int b=0;
for(int j=0;j<len;++j) b|=(s[j]-'0')<<j;
w[len][b]=1;
}
for(int j=0;j<1<<7;++j)for(int k=0;k<1<<8;++k)
for(int l=0;l<2;++l){
int f=0;
for(int m=0;m<8;++m)if(k>>m&1){
int b=(j<<1|l)&((1<<(m+1))-1);
if(w[m+1][b]) {f=1;break;}
}
pre[j][k][l]=f;
}
dp[0][0][1]=1;
for(int i=0;i<L;++i)for(int j=0;j<1<<7;++j)
for(int k=0;k<1<<8;++k)if(dp[i][j][k])
for(int l=0;l<2;++l){
int f=pre[j][k][l];
int nj=(j<<1&127)|l;
int nk=(k<<1&255)|f;
dp[i+1][nj][nk]=add(dp[i+1][nj][nk],dp[i][j][k]);
}
int ans=0;
for(int j=0;j<1<<7;++j)for(int k=0;k<1<<7;++k)
ans=add(ans,dp[L][j][k<<1|1]);
printf("%d
",ans);
return 0;
}
AC自动机：
int tot,ch[3587][2],fa[3587],val[3587];
void insert(char s[],int n){
int x=0;
for(int i=1;i<=n;++i){
int c=s[i]-'0';
if(!ch[x][c]) ch[x][c]=++tot;
x=ch[x][c];
}
val[x]|=1<<(n-1);
}
int dp[2][3587][1<<8];
int main(){
int n=read<int>(),L=read<int>();
for(int i=1;i<=n;++i){
static char s[10];scanf("%s",s+1);
insert(s,strlen(s+1));
}
deque<int> Q;
for(int c=0;c<2;++c)
if(ch[0][c]) Q.push_back(ch[0][c]);
while(Q.size()){
int x=Q.front();Q.pop_front();
val[x]|=val[fa[x]];
for(int c=0;c<2;++c){
if(!ch[x][c]) ch[x][c]=ch[fa[x]][c];
else{
fa[ch[x][c]]=ch[fa[x]][c];
Q.push_back(ch[x][c]);
}
}
}
dp[0&1][0][1]=1;
for(int i=0;i<L;++i){
for(int x=0;x<=tot;++x) fill(dp[(i+1)&1][x],dp[(i+1)&1][x]+(1<<8),0);
for(int j=0;j<=tot;++j)for(int k=0;k<1<<8;++k)
if(dp[i&1][j][k])for(int l=0;l<2;++l){
int nj=ch[j][l];
bool f=k&val[nj];
int nk=(k<<1&255)|f;
dp[(i+1)&1][nj][nk]=add(dp[(i+1)&1][nj][nk],dp[i&1][j][k]);
}
}
int ans=0;
for(int j=0;j<=tot;++j)for(int k=0;k<1<<7;++k)
ans=add(ans,dp[L&1][j][k<<1|1]);
printf("%d
",ans);
return 0;
}
R
把走两次看成两个节点同时走即可。
CO int N=310;
namespace G{
vector<int> to[N];
int pos[N],low[N],dfn;
int stk[N],top,ins[N];
int col[N],scc;
void tarjan(int u){
pos[u]=low[u]=++dfn;
stk[++top]=u,ins[u]=1;
for(int v:to[u]){
if(!pos[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v]) low[u]=min(low[u],pos[v]);
}
if(low[u]==pos[u]){
++scc;
do{
int x=stk[top];
col[x]=scc,ins[x]=0;
}while(stk[top--]!=u);
}
}
void main(int n){
for(int i=1;i<=n;++i)
if(!pos[i]) tarjan(i);
}
}
int val[N],eg[N][N];
vector<int> to[N];
int deg[N],idx[N];
int dp[N][N];
int main(){
int n=read<int>();
for(int u=1;u<=n;++u)for(int v=1;v<=n;++v)
if(read<int>()) G::to[u].push_back(v);
G::main(n);
for(int u=1;u<=n;++u){
++val[G::col[u]];
for(int v:G::to[u])if(G::col[v]!=G::col[u]){
if(eg[G::col[u]][G::col[v]]) continue;
to[G::col[u]].push_back(G::col[v]),++deg[G::col[v]];
eg[G::col[u]][G::col[v]]=1;
}
}
n=G::scc;
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
eg[i][j]|=eg[i][k]&eg[k][j];
deque<int> Q;
for(int i=1;i<=n;++i)
if(!deg[i]) Q.push_back(i);
while(Q.size()){
int u=Q.front();Q.pop_front();
idx[++idx[0]]=u;
for(int v:to[u])if(--deg[v]==0)
Q.push_back(v);
}
for(int i=1;i<=n;++i)for(int j=1;j<i;++j){
int u=idx[i],v=idx[j];
dp[u][v]=max(dp[u][v],val[u]+val[v]);
for(int k=i+1;k<=n;++k){
int w=idx[k];
if(eg[u][w]) dp[w][v]=max(dp[w][v],dp[u][v]+val[w]);
if(eg[v][w]) dp[w][u]=max(dp[w][u],dp[u][v]+val[w]);
}
}
int ans=0;
for(int u=1;u<=n;++u)for(int v=1;v<=n;++v)
ans=max(ans,dp[u][v]);
printf("%d
",ans);
return 0;
}
S
需要用复杂的状态记录连通性。
https://suikaba.hatenablog.com/entry/2017/08/24/164134
struct DisjointSet{
vector<int> fa;
DisjointSet(int n):fa(n){
for(int i=0;i<n;++i) fa[i]=i;
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
IN void merge(int x,int y){
fa[find(x)]=find(y);
}
};
int main(){
int H=read<int>(),W=read<int>();
vector<int> pw(8);
pw[0]=1;
for(int i=1;i<8;++i) pw[i]=pw[i-1]*7;
vector<int> cur(pw[H]);
for(int i=0;i<1<<H;++i)if(i&1){
int s=1;
int label=1;
for(int j=1;j<H;++j){
if(i>>j&1) s+=label*pw[j];
else if(i>>(j-1)&1) ++label;
}
cur[s]=1;
}
for(int i=0;i<W-1;++i){
vector<int> nxt(pw[H]);
for(int j=0;j<pw[H];++j)if(cur[j])
for(int k=0;k<1<<H;++k){
DisjointSet uf(H);
vector<int> p(H);
for(int l=0;l<H;++l)if(k>>l&1){
if(j/pw[l]%7==1) p[l]=1;
for(int m=l+1;m<H;++m)if(k>>m&1){
if(m==l+1) uf.merge(l,m);
else{
int u=j/pw[l]%7,v=j/pw[m]%7;
if(u>0 and u==v) uf.merge(l,m);
}
}
}
for(int l=0;l<H;++l)if(p[l]==1)
p[uf.find(l)]=1;
int nj=0;
int label=2;
for(int l=0;l<H;++l)if(k>>l&1){
int u=uf.find(l);
if(p[u]==0) p[u]=label++;
nj+=pw[l]*p[u];
}
nxt[nj]=add(nxt[nj],cur[j]);
}
cur.swap(nxt);
}
int ans=0;
for(int i=0;i<pw[H];++i)if(i/pw[H-1]%7==1)
ans=add(ans,cur[i]);
printf("%d
",ans);
return 0;
}
T
齐次线性递推模板题。
poly operator*(CO poly&a,CO poly&b){
int n=a.size()-1,m=b.size()-1;
poly ans(n+m+1);
for(int i=0;i<=n;++i)for(int j=0;j<=m;++j)
ans[i+j]=add(ans[i+j],mul(a[i],b[j]));
return ans;
}
poly operator%(poly a,CO poly&b){
int n=a.size()-1,m=b.size()-1;
if(n<m) return a;
for(int i=n;i>=m;--i){
int coef=mul(mod-a[i],fpow(b[m],mod-2));
for(int j=i;j>=i-m;--j) a[j]=add(a[j],mul(coef,b[j-(i-m)]));
}
return poly(a.begin(),a.begin()+m);
}
int main(){
int k=read<int>(),n=read<int>();
if(n<=k){
puts("1");
return 0;
}
poly a(k+1);
for(int i=1;i<=k;++i) a[k-i]=1;
a[k]=mod-1;
poly f(k+1);
for(int i=1;i<=k;++i) f[i]=1;
poly rmd={1},tmp={0,1};
for(--n;n;n>>=1,tmp=tmp*tmp%a)
if(n&1) rmd=rmd*tmp%a;
int ans=0;
for(int i=0;i<k;++i) ans=add(ans,mul(rmd[i],f[i+1]));
printf("%d
",ans);
return 0;
}