1 条题解

  • 0
    @ 2024-6-19 15:23:09

    首先我们得意识到一个事实:假设当前已经播放过xx种歌了,那么下一首新歌的概率都是1nx\frac{1}{n-x}

    n8n\leq 8

    我们直接dfsdfs,每次爆搜新听到的歌是哪一首,顺便记一下概率是多少,一旦S\geq S就把答案累计进去即可。

    n20,S100n\leq 20,S\leq 100

    不知道我为什么设置了这么个范围。

    n20n\leq 20

    我们考虑dpstadp_{sta}表示当前听到的歌构成了stasta这个二进制状态的概率是多少。

    转移的时候直接枚举下一首歌是谁即可。

    dp[0]=1;
    for (int sta=0;sta<(1<<n);sta++)
    {
        ll x=popcount(sta); //x:sta二进制下1的个数
        if (sum[sta]>=S) continue; //sum[sta]:sta这个集合的和
        x=pw(n-x,mod-2); //每一个数字都是1/(n-x)的概率被选到。
        for (int i=0;i<n;i++)
            if (((sta>>i)&1)==0)
            {
                if (sum[sta]+a[i]<S) add(dp[sta|(1<<i)],dp[sta]*x);
                else add(ans[i],dp[sta]*x);
            }
    }
    for (int i=0;i<n;i++) cout<<ans[i]<<" "; cout<<endl;
    

    n100,S1000n\leq 100,S\leq 1000

    我们考虑这样一个事实:对于一个集合1010110101来说,它出现的概率根本不需要dp来计算,直接可以等价成这样一个数学模型:

    你有55个元素需要排列,问前三个数字恰好是135135或者153,315,351,513,531153,315,351,513,531的概率是多少。

    这个概率直接就是3!A53\frac{3!}{A_5^3}。(此处,A53A_5^3就是从55个元素里面,有序的取出33个元素的概率)。

    也就是说:集合里11的元素个数相同,出现的概率就是相同的

    那么我们直接枚举结束时候听到的歌是谁(假设是xx),然后把其余的歌拿出来。

    dpi,j,kdp_{i,j,k}表示考虑了前ii首歌,当前一共选中了jj首,它们的和是kk的方案数有多少种。

    这个是个经典0101背包,时间复杂度O(n2S)O(n^2S),空间复杂度可以优化到O(nS)O(nS),也就是我们直接用dpj,kdp_{j,k}来算答案。

    当计算完这个之后,xx的答案就是:

    $\sum_j\sum_{k<S,k+a[x]\geq S}dp_{j,k}\times \frac{j!}{A_n^{j+1}}$

    由于对每一个xx都要做一遍背包,复杂度是O(n3S)O(n^3S)

    ll dp[105][10005];
    void add(ll &x,ll y) {x=((x+y)%mod+mod)%mod;}
    void ins(int i)
    {
        for (int j=n-1;j>=0;j--)
    	for (int k=0;k<S-a[i];k++)
    	{
    		add(dp[j+1][k+a[i]],dp[j][k]);
    	}
    }
    void work(int id)
    {
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for (int i=1;i<=n;i++) if (i!=id) ins(i);
        //上面是在计算不含id的方案数
        
        ll ret=0;
        for (int j=0;j<=n-1;j++)
            for (int s=S-a[i];s<S;s++) //枚举合法的状态,算答案
            {
                //j!/A(n,j+1)
                //fac[j]:j!   inv[j]:1/A(n,j) 也就是A(n,j)^(n-2)%mod
                ll gai=dp[j][s]*fac[j]%mod*inv[j+1]%mod;
                add(ret,gai);
            }
    	cout<<ret<<" ";
    }
    for (int i=1;i<=n;i++) work(i);
    

    正解

    我们在上述基础上考虑。

    实际上那个dp,我们按任意顺序添加元素,最终的dp数组都是那个最终的数组。

    那么我们考虑一下,能否把ins(i)ins(i)的影响,在最终的dp数组里面拿掉呢?

    我们来看看ins(i)ins(i)干了个啥。

    void ins(int i)
    {
        for (int j=n-1;j>=0;j--)
    	for (int k=0;k<S-a[i];k++)
    	{
    		add(dp[j+1][k+a[i]],dp[j][k]);
    	}
    }
    

    这不就是顺着一行一行递推上去的吗?我们再倒着一行一行撤销回来不就可以了?

    void del(int i)
    {
    	for (int j=0;j<=n-1;j++) //刚才从n-1到0,现在从0到n-1
    	for (int k=0;k<S-a[i];k++)
    	{
    		add(dp[j+1][k+a[i]],-dp[j][k]);	
    	}	
    }
    

    这样,对于每一个xx,我们只需要O(nS)O(nS)的速度就可以得到最终的dp数组,再通过O(nS)O(nS)的速度还原回去即可。

    复杂度O(n2S)O(n^2S)

    #include<bits/stdc++.h>
    #define ll long long
    #define maxn 100005
    #define mod 998244353
    using namespace std;
    int n,S,a[maxn];
    ll ni;
    ll pw(ll x,ll mi)
    {
    	ll ret=1;
    	while (mi)
    	{
    		if(mi&1) ret=ret*x%mod;
    		x=x*x%mod; mi=mi>>1;
    	}
    	return ret;
    }
    void add(ll &x,ll y) {x=((x+y)%mod+mod)%mod;}
    ll dp[105][10005]; //听了i首歌,共j的愉悦程度的方案数 
    
    void del(int i)
    {
    	for (int j=0;j<=n-1;j++)
    	for (int k=0;k<S-a[i];k++)
    	{
    		add(dp[j+1][k+a[i]],-dp[j][k]);	
    	}	
    }
    
    void ins(int i)
    {
    	for (int j=n-1;j>=0;j--)
    	for (int k=0;k<S-a[i];k++)
    	{
    		add(dp[j+1][k+a[i]],dp[j][k]);
    	}
    }
    
    void init() 
    {
    	dp[0][0]=1;
    	for (int i=1;i<=n;i++) ins(i);
    }
    ll fac[105],inv[105];
    void work()
    {
    	for (int i=1;i<=n;i++)
    	{
    		del(i);
    		ll ret=0;
    		for (int j=0;j<=n-1;j++)
    		for (int s=S-a[i];s<S;s++) //听了a[i]就超啦
    		{
    			//j!/A(n,j+1)
    			ll gai=dp[j][s]*fac[j]%mod*inv[j+1]%mod;
    			add(ret,gai);
    		} 
    		ins(i);
    		cout<<ret<<" ";
    	}
    	cout<<endl;
    }
     
    int main()
    {
    	cin>>n>>S; 
    	fac[0]=1;
    	for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod; //i!
    	inv[0]=1;
    	for (int i=1;i<=n;i++) inv[i]=inv[i-1]*(n-i+1)%mod; //A(n,i)
    	for (int i=1;i<=n;i++) inv[i]=pw(inv[i],mod-2); //1/A(n,i)
    	for (int i=1;i<=n;i++) cin>>a[i];
    	init();
    	work();
    }
    
    • 1

    信息

    ID
    1429
    时间
    2000ms
    内存
    512MiB
    难度
    8
    标签
    (无)
    递交数
    13
    已通过
    6
    上传者