自动搬运

查看原文

来自洛谷，原作者为

	hdxrie **

搬运于2025-08-24 22:05:53，当前版本为作者最后更新于2018-10-12 14:29:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

注意：

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

$$q=\sum_{i=1}^{k-1}C_k^i\times \sum_{j=1}^{k-i}C_{k-i}^j $$

算法1：

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

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

算法2：

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

$$f[i][S]=\sum_{S',S'\cap S=\varnothing}f[i-1][S']$$

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

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

算法3：

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

$$ans=\begin{cases}2\ (n\geq1,p=2)\\0\ (n>1,p<2)\\1\ (n=1,p=1)\end{cases} $$

特判回答即可。

时间复杂度$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$好猛...