SDOI2022 D2T1 题解

· · 题解

很好的签到题，为啥 SX 没人过呢？

本文中的 m 是题目中的 k

考场做法

考虑 DP。设 f[u,i,j] 为子树 u，选/不选 u 的最大权独立集为 i,j 的方案数。转移：f'[u,i+l,j+\max(k,l)]\leftarrow f[u,i,j]\times f[v,k,l]，注意顺序。

状态数 O(n^{3}m^{2})，但实际上远远达不到这个上界（有没有好哥哥教我怎么算复杂度啊/kel）。同时注意到 i\le j 时转移不需要用到 i，可以把这样的状态合并为 ff[u,j]。赛时发现了状态数并不多但认为是二维 FFT 之类的东西就不管了

我使用了 cc_hash_table 保存状态，获得了 80pts

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx;
#define For(i,x,y,...) for(int i=(x),##__VA_ARGS__;i<=(y);++i)
#define rFor(i,x,y,...) for(int i=(x),##__VA_ARGS__;i>=(y);--i)
#define Rep(i,x,y,...) for(int i=(x),##__VA_ARGS__;i<(y);++i)
#define pb emplace_back
#define sz(a) int((a).size())
#define all(a) begin(a),end(a)
#define MT make_tuple
#define MP make_pair
#define fi first
#define se second
typedef long long LL; typedef unsigned uLL;
typedef vector<int> Vi; typedef pair<int,int> Pii;
template<typename X,typename Y>bool ckmin(X &x,Y y) { return y<x ? x=y,1 : 0; }
template<typename X,typename Y>bool ckmax(X &x,Y y) { return x<y ? x=y,1 : 0; }
sfmt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r) { return uniform_int_distribution<>(l,r)(mt); }
#define endl '\n'
namespace IO { const int L = 1<<22; char a[L],*l=a,*r=a,b[L],*p=b;
auto gc=[]() { if(l==r)r=(l=a)+fread(a,1,L,stdin);return l==r?EOF:*l++; };
auto pc=[](char x) { if(p-b==L)fwrite(b,1,L,stdout),p=b;*p++=x; };
struct IO {
    ~IO() { fwrite(b,1,p-b,stdout); }
    template<typename T>IO& operator >> (T &x) {
        x=0;bool f=1;char c;while(!isdigit(c=gc()))if(c=='-')f=0;
        if(f)do x=x*10+c-48;while(isdigit(c=gc()));
        else do x=x*10-c+48;while(isdigit(c=gc()));
        return *this;
    }
    IO& operator >> (char *s) {
        while(!isgraph(*s=gc())); while(isgraph(*++s=gc()));
        return *s=0, *this;
    }
    IO& operator << (char x) { pc(x); return *this; }
    IO& operator << (char *s) { while(*s)pc(*s++); return *this; }
    IO& operator << (const char *s) { while(*s)pc(*s++); return *this; }
    template<typename T>IO& operator << (T x) {
        if(!x)pc(48);
        else{static char s[44];char *t=s;if(x<0)pc('-'),*t++=-(x%10),x=-(x/10);
        for(;x;x/=10)*t++=x%10;while(s!=t)pc(*--t|48);}
        return *this;
    }
} io; } using IO::io;
const int mod = 1e9+7;
template<typename T>T Mod(T x) { return x<0 ? x+mod : x<mod ? x : x-mod; }
template<typename X,typename Y>void ckadd(X &x,Y y)
    { x = x+y<0 ? x+y+mod : x+y<mod ? x+y : x+y-mod; }
LL Pow(LL x,LL y=mod-2) { LL z=1;for(;y;y>>=1,x=x*x%mod)if(y&1)z=z*x%mod;return z; }

const int N = 1005;
int n,m;
LL ans[N*5];
Vi e[N];
struct Hash {
    size_t operator () (const Pii &x) const
        { return x.fi * 131 + x.se; }
}; cc_hash_table<Pii,LL,Hash> f[N];
cc_hash_table<int,LL> ff[N];

void dfs(int u,int fa) {
    for(int v : e[u]) if( v != fa ) dfs(v,u);
    For(i,1,m) f[u][MP(i,0)] = 1;
    for(int v : e[u]) if( v != fa ) {
        auto g(f[u]); f[u].clear();
        for(auto i : g) {
            for(auto j : f[v])
                (f[u][MP(i.fi.fi+j.fi.se,i.fi.se+j.fi.fi)] +=
                    i.se * j.se) %=mod;
            for(auto j : ff[v])
                (f[u][MP(i.fi.fi+j.fi,i.fi.se+j.fi)] += i.se * j.se) %=mod;
        }
    }
//  cerr<<u<<":\n";
//  for(auto i : f[u]) cerr<<i.fi.fi<<' '<<i.fi.se<<": "<<i.se<<endl;
    auto g(f[u]); f[u].clear();
    for(auto i : g)
        if( i.fi.fi <= i.fi.se ) ckadd(ff[u][i.fi.se],i.se);
        else f[u][i.fi] = i.se;
}

signed main() { freopen("nset.in","r",stdin); freopen("nset.out","w",stdout);
    io>>n>>m; Rep(i,1,n, x,y) io>>x>>y, e[x].pb(y), e[y].pb(x);
    dfs(1,0);
    for(auto i : f[1]) ckadd(ans[max(i.fi.fi,i.fi.se)],i.se);
    for(auto i : ff[1]) ckadd(ans[i.fi],i.se);
    For(i,1,n*m) io<<ans[i]<<endl;
//  int TM=0; For(i,1,n) TM += sz(f[i]); cerr<<TM<<endl;
    return 0;
}

正解

另一个观察是 j\ge i-m（一个选 u 的方案去掉 u 就可以变为不选 u 的方案）。因此有用的状态只有 O(nm^{2}) 种：i\le j 或 1\le i-j\le m。转移复杂度类似树上背包

代码把上文中先转移到 f[u] 再合并到 ff[u] 改为直接转移到 ff[u] 即可，不贴了

另一个能过的思路是发现全程只用到了 j,\max(i,j)，所以把这两个放进 DP 状态，敢写敢 AC

碎碎念：

一开始看错题了，以为 O(n^{2}m) 随便做/kk。后面读对了也没细想，写完暴力就跑了，于是输麻了。几乎写出了正解还是白丢 20pts，完美体现了不带脑子做题，只能说不愧是我。

考场策略也很重要。花了大量时间做 T2，但一个包只有 2,3pts，以放弃思考 T1 T3 为代价其实是不值的

希望读者以我为鉴吧