题解 P4982 【规划】

hdxrie · 2018-10-12 14:29:56 · 题解

注意：

题解中算复杂度所提到的q均为如下公式：

算法1：

暴力搜索所有情况，虽然看起来复杂度为2^{35}，但是很多状态是不合法的，实际上合法方案数不会超过5×10^7，那么暴力搜索的复杂度也不会太多。

时间复杂度O(\text{能过})，期望得分：20分。

算法2：

读题发现m很小，可以想到状压，考虑定义\rm DP转移，令f[i][S]表示考虑到第i天，当天吃的菜品集合为S时的合法方案数，令S'为前一天吃的菜品集合，那么\rm DP转移可以如下表示：

采用子集枚举，则转移的时间复杂度为q，当k=7时取到上界为1932。

时间复杂度为O(nq)，期望得分：45分。

算法3：

观察到m,k很特殊，如果令p为那一天提供的菜品数量，规律可以总结为以下3种情况：

特判回答即可。

时间复杂度O(1)，加上算法2，期望得分：55分。

算法4：

观察后面的测试点，看起来需要一个时间复杂度为O(n)的算法，但是这只是出题人的陷阱，因为转移的复杂度已经不能再优化了只是出题人不知道怎么优化了，我们需要想别的办法。观察所有的状态转移，如果以k天为单位，可以发现转移是一样的，那么可以想到构造矩阵进行优化。对于制定了k天的菜谱，每一天都花q的时间复杂度构造一个2^m×2^m转移矩阵，先将这k天的矩阵乘起来，然后求乘完后矩阵的\left\lfloor\frac{n}{k}\right\rfloor次方，对于剩余的n{\ \rm mod\ }k天，因为不是一个完整的k天，所以在之前合并矩阵的时候记录一下前n{\ \rm mod\ }k天的矩阵合并后的样子，最后再将记录的矩阵乘上去，将所有方案累加就是答案。

预处理时间复杂度O(kq+k2^{3m})，转移时间复杂度O(2^{3m}log\left\lfloor\frac{n}{k}\right\rfloor+2^{2m})，期望得分：70分。

实际上加个循环展开就可以过了。

算法5：

由于合并矩阵的复杂度太高，我们得换一种方式构造一个周期的转移矩阵，实际上我们可以尝试用\rm DP构造，我们枚举开头那一天的所有情况S，然后对于每一个情况S单独进行一次k天的算法4的\rm DP，这样就能求出当状态为S的时候，经过k天后能对哪些状态有贡献且贡献为多少，这样能在O(k2^mq)的时间复杂度内构造出转移矩阵，对于剩下的n{\ \rm mod\ }k天，在\rm DP中途记录一下只转移n{\ \rm mod\ }k天的矩阵，那么只需要在最后再乘上它，我们就得到了答案。

预处理时间复杂度O(k2^mq)，转移时间复杂度O(2^{3m}log\left\lfloor\frac{n}{k}\right\rfloor+2^{2m})，期望得分：100分。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=130,M=310,mod=1e9+7;
int n,m,k,S,l1,l2,out,have[M],ans[N];
int tran[N][N],tem[N][N],day[N][N],dp[2][N];
void merge1()
{
    memset(tem,0,sizeof(tem));
    for(int i=1;i<=S;i++)
     for(int j=1;j<=S;j++)
      for(int p=1;p<=S;p++)
       (tem[i][j]+=1ll*tran[i][p]*tran[p][j]%mod)%=mod;
    for(int i=1;i<=S;i++)
     for(int j=1;j<=S;j++)
      tran[i][j]=tem[i][j];
}
void merge2()
{
    memset(tem[0],0,sizeof(tem[0]));
    for(int i=1;i<=S;i++)
     for(int j=1;j<=S;j++)
      (tem[0][i]+=1ll*ans[j]*tran[j][i]%mod)%=mod;
    for(int i=1;i<=S;i++)
     ans[i]=tem[0][i];
}
void merge3()
{
    memset(tem[0],0,sizeof(tem[0]));
    for(int i=1;i<=S;i++)
     for(int j=1;j<=S;j++)
      (tem[0][i]+=1ll*ans[j]*day[j][i]%mod)%=mod;
    for(int i=1;i<=S;i++)
     ans[i]=tem[0][i];
}
void power(int p)
{
    for(;p;p>>=1,merge1())
     if(p&1)merge2();
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);S=(1<<m)-1;
    for(int i=1;i<=k;i++)
    {
        scanf("%d",&l1);
        for(int j=1;j<=l1;j++)
        {
            scanf("%d",&l2);
            have[i]|=1<<(l2-1);
        }
    }
    for(int i=have[1];i;i=(i-1)&have[1])
    {
        int now=0;
        memset(dp,0,sizeof(dp));dp[now][i]=1;
        for(int j=2;j<=k;j++)
        {
            memset(dp[now^1],0,sizeof(dp[now^1]));
            for(int p=have[j];p;p=(p-1)&have[j])
             for(int q=(have[j-1]|p)^p;q;q=(q-1)&((have[j-1]|p)^p))
              (dp[now^1][p]+=dp[now][q])%=mod;
            now^=1;if((n-1)%k==j-1)
             for(int p=1;p<=S;p++)
              day[i][p]=dp[now][p];
        }
        memset(dp[now^1],0,sizeof(dp[now^1]));
        for(int p=have[1];p;p=(p-1)&have[1])
         for(int q=(have[k]|p)^p;q;q=(q-1)&((have[k]|p)^p))
          (dp[now^1][p]+=dp[now][q])%=mod;
        now^=1;for(int j=1;j<=S;j++)
         tran[i][j]=dp[now][j];
    }
    for(int i=have[1];i;i=(i-1)&(have[1]))ans[i]=1;
    power((n-1)/k);if((n-1)%k!=0)merge3();
    for(int i=1;i<=S;i++)(out+=ans[i])%=mod;
    printf("%d\n",out);
    return 0;
}

顺便吐槽洛谷的\rm O2好猛...