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

题目链接

A-魔改森林

题意：

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

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

#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-神经冲动

题面可能有点难懂，看下样例就懂了：

还是不会写，好难啊，看官方题解：

很妙，大概就是：

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();
}