欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客OI周赛14-提高组(A 容斥 计数,B状压dp)

程序员文章站 2023-12-24 22:20:45
...

题目链接

A-魔改森林

题意:

牛客OI周赛14-提高组(A 容斥 计数,B状压dp)

不知道没有障碍的时候怎么计算总和,于是看了一眼官方题解:

牛客OI周赛14-提高组(A 容斥 计数,B状压dp)

所以容斥怎么去搞?  懵了,于是看别人的代码学的,就当学习了:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353,N=2e5+5;
ll f[N],invf[N];
int n,m,k,x[4],y[4];
ll C(int n,int m)
{
    if(n<0||m<0) return 0;
    return f[n]*invf[n-m]%mod*invf[m]%mod;
}
void solve1()
{
    int a[n+10][m+10];
    ll dp[n+10][m+10];
    memset(dp,0,sizeof(dp));
    memset(a,0,sizeof(a));
    for(int i=1;i<=k;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        a[x][y]=1;
    }
    dp[n+1][1]=1;
    for(int i=n+1;i>=1;i--)
        for(int j=1;j<=m+1;j++)
        if(!a[i][j])
        {
            (dp[i][j]+=dp[i+1][j])%=mod;
            (dp[i][j]+=dp[i][j-1])%=mod;
        }
    printf("%lld\n",dp[1][m+1]);
}
ll to(int x1,int y1,int x2,int y2)
{
    return C(x1-x2+y2-y1,y2-y1);
}
void solve2()
{
    for(int i=1;i<=k;i++)
        scanf("%d%d",&x[i],&y[i]);
    ll ans=to(n+1,1,1,m+1);
    for(int i=1;i<=k;i++)
        ans-=to(n+1,1,x[i],y[i])*to(x[i],y[i],1,m+1)%mod;

    ans%=mod;
    for(int i=1;i<=k;i++)
    for(int j=1;j<=k;j++)
    {
        if(i==j) continue;
        if(x[j]<=x[i]&&y[j]>=y[i])//i到j
        ans+=to(n+1,1,x[i],y[i])*to(x[i],y[i],x[j],y[j])%mod*to(x[j],y[j],1,m+1)%mod;
    }

    ans%=mod;
    for(int i=1;i<=k;i++)
    for(int j=1;j<=k;j++)
    for(int s=1;s<=k;s++)
    {
        if(i==j||i==s||j==s) continue;//i=>j=>s
        if(x[j]<=x[i]&&y[j]>=y[i]&&x[s]<=x[j]&&y[s]>=y[j])
        ans-=to(n+1,1,x[i],y[i])*to(x[i],y[i],x[j],y[j])%mod*to(x[j],y[j],x[s],y[s])%mod*to(x[s],y[s],1,m+1)%mod;
    }

    ans=(ans%mod+mod)%mod;
    printf("%lld\n",ans);
}
int main()
{
    f[0]=invf[0]=f[1]=invf[1]=1;
    for(int i=2;i<N;i++) f[i]=f[i-1]*i%mod,invf[i]=(mod-mod/i)*invf[mod%i]%mod;
    for(int i=2;i<N;i++) invf[i]=invf[i-1]*invf[i]%mod;
    scanf("%d%d%d",&n,&m,&k);
    if(n<=1000&&m<=1000) solve1();
    else solve2();
}

B-神经冲动

牛客OI周赛14-提高组(A 容斥 计数,B状压dp)

题面可能有点难懂,看下样例就懂了:

牛客OI周赛14-提高组(A 容斥 计数,B状压dp)

还是不会写,好难啊,看官方题解:

牛客OI周赛14-提高组(A 容斥 计数,B状压dp)

很妙,大概就是:

f[i][j]为 i这个点 到j时刻能影响的点
dp[i][j]为i时刻的j状态是否存在

通过f 预处理每个点每个时刻影响的位置状压预处理一下,然后再跑dp方程得到需要的状态即可

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=25;
int n,need,dp[N][(1<<20)],fa[N],f[N][3*N];
//f[i][j]为 i这个点 到j时刻能影响的点
//dp[i][j]为i时刻的j状态是否存在
void init()
{
    for(int i=1;i<=n;++i){
        f[i][1]=1<<(i-1);
        int x=fa[i];
        for(int j=2;j<=2*n;++j){
            f[i][j]=f[i][j-1];
            if(x) f[i][j]|=(1<<(x-1));
            x=fa[x];
        }
    }
}

void work()
{
    dp[0][need]=1;
    int len=(1<<n);
    for(int i=1;i<=2*n;++i){//枚举时间
        for(int j=0;j<len;++j){//枚举状态
            if(dp[i-1][j]==0) continue;
            for(int k=0;k<=n;++k){//枚举点
                int now=j^f[k][i];
                if(now==0){
                    printf("%d\n",i);
                    return ;
                }
                dp[i][now]=1;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;++i) scanf("%d",&fa[i]);
    int x;
    for(int i=1;i<=n;++i) {
        scanf("%d",&x);
        if(x) need|=(1<<(i-1));
    }
    init();
    work();
}

 

相关标签: dp--状压dp

上一篇:

下一篇: