「雅礼集训 2018-03-31」Max

一个长为 $n$ 的序列 $A$，从 $1$ 开始标号，一开始全为 $0$，现在小 C 想对它进行 $m$ 次操作。对第 $i$ 次操作，他会选定恰好一个二元组 $(j,k)$（$1\leq j\leq n,0\leq k\leq c$）并令 $A_j=A_j+k$，其中选中二元组 $(j,k)$ 的概率为 $P_{i,j,k}$。小 C 本来是想问你区间最大值的历史版本和的历史最大值的期望的，但鉴于这是一道签到题，现在他只想知道 $m$ 次操作后整个序列最大值的期望，对 $10^9+7$ 取模。

Constraints

$n \leq 40$ ， $m \leq 10$ ， $c \leq 3$

Solution

令 $f(i,S,j)$ 表示 $A_{i}$ 在经过集合 $S$ 的操作后，值为 $j$ 的概率。

令 $dp(i,S,j)$ 表示前 $i$ 个元素，用掉了集合 $S$ 的操作，最大值为 $j$ 的概率，可得：

$dp(i,S_{1},j)\times f(i+1,S_{2},k)=dp(i+1,S_{1}+S_{2},max(j,k))$

详见代码。

Code

#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=41;
const int M=11;
const int T=1<<10;
const int mod=1e9+7;
int n,m,c,S,x,y,val,ans;
int p[N][M][4],f[T][M*3],dp[N][T][M*3];
int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
void Mod(int &x,LL val){x=(x+val)%mod;}
int main()
{
    n=read();m=read();c=read();S=(1<<m)-1;
    for(int j=0;j<m;j++)
        for(int i=1;i<=n;i++)
            for(int k=0;k<=c;k++)
                p[i][j][k]=read();
    dp[0][0][0]=1;
    for(int i=1;i<=n;i++)
    {
        memset(f,0,sizeof(f));
        f[0][0]=1;
        for(int s=0;s<=S;s++)
        {
            x=__builtin_popcount(s);
            for(int j=0;j<m;j++)
            {
                if((1<<j)&s)break;
                for(int k=0;k<=c*x;k++)
                    for(int d=0;d<=c;d++)
                        Mod(f[s|(1<<j)][k+d],1ll*f[s][k]*p[i][j][d]);
            }
        }
        for(int s=0;s<=S;s++)
        {
            x=__builtin_popcount(s);
            for(int k=0;k<=c*x;k++)
            {
                val=dp[i-1][s][k];
                if(!val)continue;
                for(int j=s^S;;j=(j-1)&(s^S))
                {
                    y=__builtin_popcount(j);
                    for(int d=0;d<=c*y;d++)
                        Mod(dp[i][s^j][max(k,d)],1ll*val*f[j][d]);
                    if(!j)break;
                }
            }
        }
    }
    for(int i=0;i<=c*m;i++)
        ans=(ans+1ll*i*dp[n][S][i])%mod;
    printf("%d",ans);
    return 0;
}