冲刺国赛模拟 32

玄学。

树

赛时以为 \(O(mn^22^n),m=200,n=15\) 拿头跑 \(2s\)，结果题解甚至 \(m3^n\) 跑过……蚌埠了。

首先你发现题目要求保留边使得连通的方案数。发现这玩意和 \(\ln\) 长得类似，于是设 \(g_S\) 为一个 \(m\) 次多项式，\(g_{i,S}\) 为 \(S\) 导出子图内选 \(i\) 条边方案，然后取个 \(\ln\) 就得到答案，复杂度 \(O(m^2n^22^n)\)，插点值算可以做到 \(O(mn^22^n)\)，不知道怎么过的。

由于有重边自环，所以懒得写了，贺了份 \(m3^n\) 的，更不知道怎么过的，而且跑的还挺快。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int mod=1000000007;
int n,m,jc[210],inv[210];
int C(int n,int m){
    if(n<m||m<0)return 0;
    return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;
}
vector<int>g[20];
int size[1<<15],tmp[20],dp[1<<15][210],f[210][210];
int main(){
    scanf("%d%d",&n,&m);jc[0]=inv[0]=inv[1]=1;
    for(int i=2;i<=m;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=m;i++)jc[i]=1ll*jc[i-1]*i%mod,inv[i]=1ll*inv[i-1]*inv[i]%mod;
    for(int i=1;i<=m;i++){
        int u,v;scanf("%d%d",&u,&v);
        if(u==v){
            size[1<<u]++;tmp[u]++;
        }
        else g[u].push_back(v),g[v].push_back(u);
    }
    for(int s=1;s<(1<<n);s++){
        int x=__lg(s&-s);
        size[s]=size[s^(s&-s)]+tmp[x];
        for(int v:g[x]){
            if((s>>v)&1)size[s]++;
        }
    }
    for(int i=0;i<=tmp[0];i++)dp[0][i]=C(tmp[0],i);
    for(int s=1;s<(1<<n-1);s++){
        int k=size[s<<1|1];
        for(int i=0;i<=k+1;i++){
            for(int j=0;j<=k+1;j++)f[i][j]=0;
        }
        for(int t=s&(s-1);t;t=s&(t-1)){
            for(int i=0;i<=size[t<<1|1];i++)f[i][size[(s^t)<<1]]=(f[i][size[(s^t)<<1]]+dp[t][i])%mod;
        }
        for(int i=0;i<=size[1];i++)f[i][size[s<<1]]=(f[i][size[s<<1]]+dp[0][i])%mod;
        for(int i=0;i<=k;i++){
            for(int j=k;j>=1;j--){
                f[i+1][j-1]=(f[i+1][j-1]+f[i][j])%mod;
                f[i][j-1]=(f[i][j-1]+f[i][j])%mod;
            }
        }
        for(int i=1;i<=k;i++)dp[s][i]=(C(k,i)-f[i][0]+mod)%mod;
    }
    for(int i=n-1;i<=m;i++)printf("%d ",dp[(1<<n-1)-1][i]);puts("");
    return 0;
}

差

神奇的 dp 构造题。

考虑 \(a\) 的差分 \(c\)，那么 \(b_i=\max(|c_i|,|c_{i+1}|,|c_i+c_{i+1}|)\)。设 \(dp_{i,x}\) 为考虑前 \(i\) 个，\(|c_i|=x\) 是否合法。转移考虑填入 \(c_{i+1}\) 的三种情况：

1. \(|c_i|=b_i\)：需要 \(|c_{i+1}|\le b_i\)。
2. \(|c_{i+1}|=b_i\)：只要有个 \(c_i\) 就行。
3. \(|c_i+c_{i+1}|=b_i\)：\(|c_{i+1}|=b_i-|c_i|\)。

那么发现 dp 的合法部分一定是由一个区间和若干单点组成。前两个操作可以变成删除一个前缀或后缀，第三个是先把整个区间翻转，然后平移 \(b_i\)。于是区间可以直接记录下来。单点的话可以用上个双端队列维护。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <list>
#define int long long
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,B,b[1000010],ans[1000010],lz[1000010];
pair<int,int>dp[1000010],del[1000010];
vector<int>v[1000010],fr[1000010],bk[1000010];
list<int>q;
signed main(){
    scanf("%lld%lld",&n,&B);
    for(int i=1;i<=n-2;i++)scanf("%lld",&b[i]);
    for(int i=0;i<=n-2;i++)del[i]=make_pair(1,0);
    dp[0]=make_pair(0,inf);
    for(int i=1;i<=n-2;i++){
        if(dp[i-1].first<=b[i]&&dp[i-1].second>=b[i]){
            dp[i]=make_pair(0,b[i]);
            while(!q.empty())v[i].push_back(q.front()),q.pop_front();
            continue;
        }
        while(!q.empty()&&q.front()*del[i-1].first+del[i-1].second>b[i])fr[i].push_back(q.front()),q.pop_front();
        while(!q.empty()&&q.back()*del[i-1].first+del[i-1].second>b[i])bk[i].push_back(q.back()),q.pop_back();
        if(!q.empty()&&(q.front()*del[i-1].first+del[i-1].second==b[i]||q.back()*del[i-1].first+del[i-1].second==b[i])){
            dp[i]=make_pair(0,b[i]);
            while(!q.empty())v[i].push_back(q.front()),q.pop_front();
            continue;
        }
        if(del[i-1].first)del[i]=make_pair(-del[i-1].first,b[i]-del[i-1].second);
        else del[i]=make_pair(-1,b[i]);
        if(q.empty()&&dp[i-1].first>b[i]){
            puts("NO");return 0;
        }
        dp[i]=make_pair(b[i]-min(dp[i-1].second,b[i]),b[i]-dp[i-1].first);
        if(dp[i-1].first>b[i])dp[i]=make_pair(inf,inf);
        if(dp[i].second!=b[i]&&(q.empty()||(q.front()*del[i].first+del[i].second!=b[i]&&q.back()*del[i].first+del[i].second!=b[i]))){
            if(q.empty()){
                q.push_back((b[i]-del[i].second)*del[i].first);
                lz[i]=1;
            }
            else{
                if(q.front()*del[i].first+del[i].second>q.back()*del[i].first+del[i].second){
                    q.push_front((b[i]-del[i].second)*del[i].first);
                    lz[i]=-1;
                }
                else{
                    q.push_back((b[i]-del[i].second)*del[i].first);
                    lz[i]=1;
                }
            }
        }
    }
    puts("YES");
    ans[n-1]=dp[n-2].first;
    if(!q.empty())ans[n-1]=min(ans[n-1],min(q.front()*del[n-2].first+del[n-2].second,q.back()*del[n-2].first+del[n-2].second));
    for(int i=n-2;i>=1;i--){
        if(lz[i]>0)q.pop_back();
        if(lz[i]<0)q.pop_front();
        if(v[i].size()){
            q.clear();
            for(int x:v[i])q.push_back(x);
        }
        if((dp[i-1].first<=b[i]&&dp[i-1].second>=b[i])||(!q.empty()&&(!q.empty()&&(q.front()*del[i-1].first+del[i-1].second==b[i]||q.back()*del[i-1].first+del[i-1].second==b[i])))){
            ans[i]=ans[i+1];
            if(ans[i+1]<ans[i+2])ans[i]+=b[i];
            else ans[i]-=b[i];
            while(!fr[i].empty())q.push_front(fr[i].back()),fr[i].pop_back();
            while(!bk[i].empty())q.push_back(bk[i].back()),bk[i].pop_back();
            continue;
        }
        while(!fr[i].empty())q.push_front(fr[i].back()),fr[i].pop_back();
        while(!bk[i].empty())q.push_back(bk[i].back()),bk[i].pop_back();
        int x=abs(ans[i+1]-ans[i+2]),y;
        if(x!=b[i])y=b[i]-x;
        else y=min(dp[i-1].first,min(q.front()*del[i-1].first+del[i-1].second,q.back()*del[i-1].first+del[i-1].second));
        ans[i]=ans[i+1]+(((x!=b[i])^(ans[i+1]<ans[i+2]))?y:-y);
    }
    int mn=inf;
    for(int i=1;i<=n;i++)mn=min(mn,ans[i]);
    for(int i=1;i<=n;i++)printf("%lld ",ans[i]-mn);puts("");
    return 0;
}

贼

对。这玩意 std 不压行 9k，意见是不要改。