UOJ Logo AntiLeaf的博客

博客

UOJ#259 子集计数问题 题解（雾

2017-07-11 15:21:07 By AntiLeaf

话说为什么没找到题解咧……算了我自己写一个好了……

由于弱菜AntiLeaf能力有限，部分测试点无法通过，见谅……

测试点1

一眼看见$n=24$，$k=8$，用Python算了算发现$n\choose k$才几十万，那直接暴力就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=35;
bool a[maxn][maxn],b[maxn];
int n,m,k,p;
int main(){
    freopen("subset1.in","r",stdin);
    freopen("subset1.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&k,&p);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[y][x]=true;
    }
    for(int i=1;i<=k;i++)b[i]=true;
    next_permutation(b+1,b+n+1);
    int ans=0;
    do{
        bool ok=true;
        for(int i=1;i<=n;i++)if(b[i]){
            for(int j=i+1;j<=n;j++)if(b[j]&&a[i][j]){
                ok=false;
                break;
            }
        }
        if(ok)ans++;
    }while(next_permutation(b+1,b+n+1));
    printf("%d",ans%p);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

测试点2

$n=40$，$k=11$，看上去不太好搞……？

其实只要在暴搜的时候判一下加上这个点是否合法就行了……

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=55;
void dfs(int,int);
bool a[maxn][maxn];
int n,m,k,p,v[maxn],ans=0;
int main(){
    freopen("subset2.in","r",stdin);
    freopen("subset2.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&k,&p);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[y][x]=true;
    }
    dfs(1,0);
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void dfs(int x,int t){
    if(t==k){
        if(++ans==p)ans=0;
        return;
    }
    if(x==n+1)return;
    bool ok=true;
    for(int i=1;i<=t;i++)if(a[x][v[i]]){
        ok=false;
        break;
    }
    if(ok){
        v[t+1]=x;
        dfs(x+1,t+1);
    }
    dfs(x+1,t);
}

测试点3

$n=100$，$k=32$，看来暴搜没戏……

不过注意到$m=n-1$，猜想这是一棵树，仔细观察之后发现它确实是一棵树，那么跑一个树形DP即可：$f_{i,j,0/1}$表示$i$的子树中选了$j$个点，是否选了$i$的方案数，合并的时候搞一搞即可。

数据范围比较小，因此直接写$O(n^3)$的DP也可以过。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=105;
void dfs(int);
void add(int,int);
vector<int>G[maxn];
int n,m,k,p,f[maxn][maxn][2],g[maxn][2];
int main(){
    freopen("subset3.in","r",stdin);
    freopen("subset3.out","w",stdout);
    scanf("%d%*d%d%d",&n,&k,&p);printf("n=%d\n",n);
    for(int i=2,x;i<=n;i++){
        scanf("%d%*d",&x);
        G[x].push_back(i);
    }
    dfs(1);
    printf("%d",(f[1][k][0]+f[1][k][1])%p);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void dfs(int x){
    f[x][0][0]=f[x][1][1]=1;
    for(int i=0;i<(int)G[x].size();i++){
        dfs(G[x][i]);
        add(x,G[x][i]);
    }
}
void add(int x,int y){
    memset(g,0,sizeof(g));
    for(int i=0;i<=n;i++)for(int j=0;i+j<=n;j++){
        g[i+j][0]=(g[i+j][0]+(long long)f[x][i][0]*(f[y][j][0]+f[y][j][1]))%p;
        g[i+j][1]=(g[i+j][1]+(long long)f[x][i][1]*f[y][j][0])%p;
    }
    memcpy(f[x],g,sizeof(g));
}

测试点4

不难发现这也是一棵树，那继续用上面的树形DP即可。

为了压内存，用vector开DP数组，同时在合并之后清空原数组即可。

（注释掉了的那些东西是为了防止被卡内存写的找直径后DP每个子树最后再DP序列的做法，然而好像写挂了，WA……换成直接DP就过了，浪费了我十分钟……并不知道直接暴力空间对不对，不过我跑的时候并没有费很多的内存）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=100005;
struct DP{
    vector<int>f[2];
    DP(){}
    void operator+=(DP&);
}f[maxn];
void bfs(int);
void dfs(int);
vector<int>G[maxn];
bool vis[maxn];
int n,k,mod,p[maxn],d[maxn],vec[maxn],q[maxn];
int main(){
    freopen("subset4.in","r",stdin);
    freopen("subset4.out","w",stdout);
    scanf("%d%*d%d%d",&n,&k,&mod);
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    /*bfs(1);
    int u=1;
    for(int i=1;i<=n;i++)if(d[i]>d[u])u=i;
    bfs(u);
    int v=1;
    for(int i=1;i<=n;i++)if(d[i]>d[v])v=i;
    bfs(v);
    int cnt=0;
    while(u){
        vec[++cnt]=u;
        vis[u]=true;
        u=p[u];
    }
    fprintf(stderr,"u=%d v=%d cnt=%d\n",vec[1],vec[cnt],cnt);
    for(int i=1;i<=cnt;i++){
        dfs(vec[i]);
        fprintf(stderr,"i=%d dfs(%d) OK\n",i,vec[i]);
    }fprintf(stderr,"OK...\n");
    DP ans=f[vec[1]];
    for(int i=2;i<=cnt;i++)ans+=f[vec[i]];
    printf("%d",(ans.f[0][k]+ans.f[1][k])%mod);*/
    dfs(1);
    printf("%d",(f[1].f[0][k]+f[1].f[1][k])%mod);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void bfs(int x){
    int head=0,tail=0;
    q[tail++]=x;
    p[x]=d[x]=0;
    while(head!=tail){
        x=q[head++];
        for(int i=0;i<(int)G[x].size();i++)if(G[x][i]!=p[x]){
            p[G[x][i]]=x;
            d[G[x][i]]=d[x]+1;
            q[tail++]=G[x][i];
        }
    }
}
int cnt=0;
void dfs(int x){
    vis[x]=true;fprintf(stderr,"%d\n",++cnt);
    f[x].f[0].resize(2);
    f[x].f[1].resize(2);
    f[x].f[0][0]=f[x].f[1][1]=1;
    for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]){
        dfs(G[x][i]);
        f[x]+=f[G[x][i]];
    }
}
#include<cassert>
void DP::operator+=(DP &b){
    DP c;
    c.f[0].resize(min(k+1,(int)(f[0].size()+b.f[0].size())-1));
    c.f[1].resize(min(k+1,(int)(f[0].size()+b.f[0].size())-1));
    for(int i=0;i<(int)f[0].size();i++)for(int j=0;j<(int)b.f[0].size()&&i+j<(int)c.f[0].size();j++){
            /*if(j>=(int)b.f[0].size())fprintf(stderr,"a=%d b=%d c=%d\n",f[0].size(),b.f[0].size(),c.f[0].size());
              assert(j<(int)b.f[0].size());*/
        c.f[0][i+j]=(c.f[0][i+j]+(long long)f[0][i]*(b.f[0][j]+b.f[1][j]))%mod;
        c.f[1][i+j]=(c.f[1][i+j]+(long long)f[1][i]*b.f[0][j])%mod;
    }
    f[0].clear();
    f[1].clear();
    b.f[0].clear();
    b.f[1].clear();
    *this=c;
}

测试点5

$n=144$，$k=20$，暴搜肯定也没戏……（之后直接忽略暴搜）

手动观察一下输入数据可以发现一些规律，比如缺某条边的点是等距分布的，再写个东西瞎xx判一下就可以发现这其实是一个$12\times 12$的网格图缺了一些边，然后写一个状压DP就好了。

判断程序：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
using namespace std;
const int maxn=255;
bool a[maxn][maxn];
int n,m,k,p,ans=0,id[35][35];
int main(){
    freopen("subset5.in","r",stdin);
    //freopen("what.out","w",stdout);
    int r=12,c=12,n=0;
    for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)id[i][j]=++n;
    scanf("%*d%d%d%d",&m,&k,&p);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[y][x]=true;
    }
    for(int i=1;i<=r;i++)for(int j=1;j<=c;j++){
            if(i){
                a[id[i][j]][id[i-1][j]]=false;
                a[id[i-1][j]][id[i][j]]=false;
            }
            if(j){
                a[id[i][j]][id[i][j-1]]=false;
                a[id[i][j-1]][id[i][j]]=false;
            }
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)assert(!a[i][j]);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

状压DP：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
bool a[255][255],down[75][255],right[75][255],ok[25][5005];
int n=12,m=12,e,k,p,id[75][255],f[25][5005][25];
int main(){
    freopen("subset5.in","r",stdin);
    freopen("subset5.out","w",stdout);
    int cnt=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)id[i][j]=++cnt;
    scanf("%*d%d%d%d",&e,&k,&p);
    while(e--){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[y][x]=true;
    }
    for(int i=1;i<n;i++)for(int j=1;j<=m;j++)if(a[id[i][j]][id[i+1][j]])down[j][i-1]=true;
    for(int i=1;i<=n;i++)for(int j=1;j<m;j++)if(a[id[i][j]][id[i][j+1]])right[j][i-1]=true;
    for(int j=1;j<=m;j++){
        for(int s=0;s<(1<<n);s++){
            bool bad=false;
            for(int i=0;i<n-1;i++)if(down[j][i]&&((s>>i)&1)&&((s>>(i+1))&1)){
                bad=true;
                break;
            }
            ok[j][s]=!bad;
        }
    }
    ok[0][0]=true;
    f[0][0][0]=1;
    for(int j=0;j<m;j++)for(int s=0;s<(1<<n);s++)if(ok[j][s]){
                //for(int l=0;l<=k;l++)if(f[j][s][l])fprintf(stderr,"f[%d][%d][%d]=%d\n",j,s,l,f[j][s][l]);
        for(int t=0;t<(1<<n);t++)if(ok[j+1][t]){
            bool bad=false;
            for(int i=0;i<n;i++)if(right[j][i]&&(((s&t)>>i)&1)){
                bad=true;
                break;
            }
            if(bad)continue;
            int siz=__builtin_popcount(t);
            for(int l=0;l+siz<=k;l++)f[j+1][t][l+siz]=(f[j+1][t][l+siz]+f[j][s][l])%p;
        }
    }
    int ans=0;
    for(int s=0;s<(1<<n);s++)ans=(ans+f[m][s][k])%p;
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

UPD：

我好像逗比了……这个网格图是满的，并不缺边……囧囧囧，我还是太菜了……

测试点7

点数和边数都比较大，不过发现$m-n$才有$4$，猜想这个图可以表示成任意一棵生成树+5条非树边。大力判一波之后可以发现图确实是连通的，那么$3^5$大力枚举每条边的状态之后再套一个$O(n^2)$的树形DP即可。

这次跑的时间比较长，为了不浪费时间，可以在跑暴力的时候来一发tetris（逃

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cassert>
using namespace std;
const int maxn=6005;
int findroot(int);
void mergeset(int,int);
void dfs(int);
void add(int,int);
vector<int>G[maxn];
bool vis[maxn];
int n,m,K,p,a[maxn],size[maxn],f[maxn][maxn][2],anc[maxn];
int main(){
    freopen("subset7.in","r",stdin);
    freopen("subset7.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&K,&p);
    for(int i=1;i<=n;i++)anc[i]=i;
    int u[55]={0},v[55]={0},cnt=0;
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        if(findroot(x)==findroot(y)){
            u[cnt]=x;
            v[cnt]=y;
            fprintf(stderr,"(%d,%d) cnt=%d\n",u[cnt],v[cnt],cnt);
            cnt++;
        }
        else{
            G[x].push_back(y);
            G[y].push_back(x);
            mergeset(x,y);
        }
    }
    memset(a,-1,sizeof(a));
    int ans=0;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)for(int k=0;k<3;k++)for(int l=0;l<3;l++)for(int m=0;m<3;m++){
                        if((!u[0]&&i)||(!u[1]&&j)||(!u[2]&&k)||(!u[3]&&l)||(!u[4]&&m))continue;
        memset(a,-1,sizeof(a));
        fprintf(stderr,"i=%d j=%d k=%d l=%d m=%d\n",i,j,k,l,m);

        if(i==0){
            a[u[0]]=1;
            a[v[0]]=0;
        }
        else if(i==1){
            a[u[0]]=0;
            a[v[0]]=1;
        }
        else a[u[0]]=a[v[0]]=0;

        if(j==0){
            a[u[1]]=1;
            a[v[1]]=0;
        }
        else if(j==1){
            a[u[1]]=0;
            a[v[1]]=1;
        }
        else a[u[1]]=a[v[1]]=0;

        if(k==0){
            a[u[2]]=1;
            a[v[2]]=0;
        }
        else if(k==1){
            a[u[2]]=0;
            a[v[2]]=1;
        }
        else a[u[2]]=a[v[2]]=0;

        if(l==0){
            a[u[3]]=1;
            a[v[3]]=0;
        }
        else if(l==1){
            a[u[3]]=0;
            a[v[3]]=1;
        }
        else a[u[3]]=a[v[3]]=0;

        if(m==0){
            a[u[4]]=1;
            a[v[4]]=0;
        }
        else if(m==1){
            a[u[4]]=0;
            a[v[4]]=1;
        }
        else a[u[4]]=a[v[4]]=0;

        memset(vis,0,sizeof(vis));
        memset(f,0,sizeof(f));
        memset(size,0,sizeof(size));
        dfs(1);assert(size[1]==n);
        ans=(ans+(f[1][K][0]+f[1][K][1])%p)%p;
        fprintf(stderr,"ans+=%d\n",(f[1][K][0]+f[1][K][1])%p);
    }
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
int findroot(int x){return x==anc[x]?x:(anc[x]=findroot(anc[x]));}
void mergeset(int x,int y){anc[findroot(x)]=findroot(y);}
void dfs(int x){
    //memset(f[x],0,sizeof(int)*(n+3));
    vis[x]=true;
    size[x]=1;
    if(a[x]==0)f[x][0][0]=1;
    else if(a[x]==1)f[x][1][1]=1;
    else f[x][0][0]=f[x][1][1]=1;
    for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]){
            dfs(G[x][i]);
            add(x,G[x][i]);
        }
}
void add(int x,int y){
    static int g[maxn][2];
    memset(g,0,sizeof(g));
    for(int i=0;i<=size[x];i++)for(int j=0;j<=size[y];j++){
        g[i+j][0]=(g[i+j][0]+(long long)f[x][i][0]*((f[y][j][0]+f[y][j][1])%p)%p)%p;
        g[i+j][1]=(g[i+j][1]+(long long)f[x][i][1]*f[y][j][0]%p)%p;
    }
    //for(int i=0;i<=size[x];i++)printf("(%d,%d) ",f[x][i][0],f[x][i][1]);printf("\n");
    //for(int i=0;i<=size[y];i++)printf("(%d,%d) ",f[y][i][0],f[y][i][1]);printf("\n");
    memcpy(f[x],g,sizeof(g));
    size[x]+=size[y];
    //for(int i=0;i<=size[x];i++)printf("(%d,%d) ",f[x][i][0],f[x][i][1]);printf("\n\n");
}

话说在这个点上因为几个NC错误卡了至少一个小时，我是不是菜得没救了……

好吧……还是高估了我的水平，除了这6个点之外剩下的似乎并不会做……

（其实测试点8是可以%论文来做的，然而我懒得学了，毕竟感觉NOI不一定用得上，还是好好复习比较好……逃）


由于填坑人弱菜AntiLeaf在这个坑里摔出*了，此坑已弃

评论

immortalCO
orz！ @WrongAnswer 把题解发上来吧
zhouyi
http://www.cnblogs.com/zzqsblog/p/6937081.html @fjzzq2002
matthew99
来做做http://uoj.ac/problem/208吧

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

Server time: 2024-11-21 14:39:03