JSOI2018R2题解
D1T1:潜入行动
裸的树上DP。f[i][j][0/1][0/1]表示以i为根的子树放j个设备，根有没有放，根有没有被子树监听，的方案数。转移显然。
1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 4 typedef long long ll; 5 using namespace std; 6 7 const int N=100010,mod=1e9+7; 8 ll tmp[110][2][2]; 9 int n,k,cnt,u,v,sz[N],dp[N][110][2][2],h[N],to[N<<1],nxt[N<<1]; 10 11 void ins(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } 12 void add(int &x,ll y){ if (x+y>=mod) x=x+y-mod; else x=x+y; } 13 14 void dfs(int x,int fa){ 15 sz[x]=1; dp[x][1][1][0]=1; dp[x][0][0][0]=1; 16 for (int i=h[x]; i; i=nxt[i]){ 17 int v=to[i]; 18 if (v==fa) continue; 19 dfs(v,x); 20 int tx=min(k,sz[x]),tv=min(k,sz[v]); 21 rep(j,0,tx) rep(a,0,1) rep(b,0,1) 22 tmp[j][a][b]=dp[x][j][a][b],dp[x][j][a][b]=0; 23 rep(j,0,tx){ 24 for(int a=0; a<=tv && j+a<=k; a++){ 25 add(dp[x][j+a][0][0],tmp[j][0][0]*dp[v][a][0][1]%mod); 26 add(dp[x][j+a][0][1],(tmp[j][0][0]*dp[v][a][1][1]+tmp[j][0][1]*(dp[v][a][0][1]+dp[v][a][1][1]))%mod); 27 add(dp[x][j+a][1][0],tmp[j][1][0]*(dp[v][a][0][0]+dp[v][a][0][1])%mod); 28 add(dp[x][j+a][1][1],(tmp[j][1][0]*(dp[v][a][1][0]+dp[v][a][1][1])+tmp[j][1][1]*(dp[v][a][0][0]+dp[v][a][1][0])+tmp[j][1][1]*(dp[v][a][0][1]+dp[v][a][1][1]))%mod); 29 } 30 } 31 sz[x]+=sz[v]; 32 } 33 } 34 35 int main(){ 36 freopen("action.in","r",stdin); 37 freopen("action.out","w",stdout); 38 scanf("%d%d",&n,&k); 39 rep(i,2,n) scanf("%d%d",&u,&v),ins(u,v),ins(v,u); 40 dfs(1,-1); 41 printf("%d ",(dp[1][k][1][1]+dp[1][k][0][1])%mod); 42 return 0; 43 }
D2T2:防御网络
https://blog.****.net/scar_lyw/article/details/80410420
首先连接环的桥边的贡献很好算，tarjan过程中可直接求出。然后对于每一个环，求出环上被选中边数的期望。
一个环被选中的边，一定是环长减去最大的一个空隙。我们枚举环上的[s,s+len]中的点被选中（一个点被选中当且仅当子图S中包含这个点或这个点连出的外向树中的点）。设DP状态dp[s][len][k]表示[s,s+len]中有点且这段的最大空隙为k的方案数。求出dp数组后贡献就很容易求得了，注意还有一个空隙是环长-len。
1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 4 #define For(i,x) for (int i=h[x],k; i; i=nxt[i]) 5 using namespace std; 6 7 const int N=1010,mod=1e9+7; 8 int n,m,u,v,cnt,ans,f[N],p2[N],sz[N],vis[N],fa[N]; 9 int dp[N][2],sm[N][2],h[N],to[N],nxt[N],dep[N]; 10 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } 11 12 int ksm(int a,int b){ 13 int res=1; 14 for (; b; a=1ll*a*a%mod,b>>=1) 15 if (b & 1) res=1ll*res*a%mod; 16 return res; 17 } 18 19 void calc(int s,int len,int n){ 20 rep(i,s-1,n) dp[i][0]=dp[i][1]=sm[i][0]=sm[i][1]=0; 21 dp[s][0]=sm[s][0]=f[s]; 22 rep(i,s+1,n){ 23 int l=max(s,i-len+1)-1; 24 if (i-len>=s) dp[i][1]=(dp[i][1]+1ll*(dp[i-len][0]+dp[i-len][1])*f[i])%mod; 25 dp[i][1]=(dp[i][1]+1ll*f[i]*(sm[i-1][1]-sm[l][1]+mod))%mod; 26 dp[i][0]=(dp[i][0]+1ll*f[i]*(sm[i-1][0]-sm[l][0]+mod))%mod; 27 sm[i][0]=(sm[i-1][0]+dp[i][0])%mod; sm[i][1]=(sm[i-1][1]+dp[i][1])%mod; 28 ans=(ans+1ll*min(i-s,n-len)*dp[i][1])%mod; 29 } 30 } 31 32 void solve(int u,int v){ 33 int cur=v,lst=0,tot=0; 34 for (; cur!=u; lst=cur,cur=fa[cur]) 35 f[++tot]=p2[sz[cur]-sz[lst]],vis[cur]=1; 36 f[++tot]=p2[n-sz[lst]]; 37 rep(i,1,tot-1) rep(j,1,tot-i) calc(i,j,tot); 38 } 39 40 void dfs(int x){ 41 dep[x]=dep[fa[x]]+1; sz[x]=1; 42 For(i,x) if (!dep[k=to[i]]) fa[k]=x,dfs(k),sz[x]+=sz[k]; 43 else if (dep[k]>dep[x]) solve(x,k); 44 } 45 46 int main(){ 47 freopen("defense.in","r",stdin); 48 freopen("defense.out","w",stdout); 49 scanf("%d%d",&n,&m); 50 rep(i,1,m) scanf("%d%d",&u,&v),add(u,v),add(v,u); 51 p2[0]=1; rep(i,1,n) p2[i]=p2[i-1]*2ll%mod; 52 rep(i,1,n) p2[i]--; 53 dfs(1); 54 rep(i,2,n) if (!vis[i]) ans=(ans+1ll*p2[sz[i]]*p2[n-sz[i]])%mod; 55 ans=1ll*ans*ksm(p2[n]+1,mod-2)%mod; 56 printf("%d ",ans); 57 return 0; 58 }