题解-P5196

本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

题面大意

想略过这一部分，因为和后面的讲解重合了，而且题目有点绕，我认为三言两语我讲不通，所以烦请各位自行理解。

解题思路

解题主要分两部分。

首先因为每行的字数相同，所以我们可以预处理出长度为 $k$ 音节的句子每种韵部的方案数。

定义一个 $f$ 数组来解决这个问题吧，先不考虑韵部，令 $f_i$ 为能凑成长度为 $k$ 的句子的方案数。

我们显然可以用 $O(nk)$ 的复杂度预处理出 $f$ 数组。

然后再想每个韵部，设当前的单词长为 $s_i$，归属于韵部 $c_i$，则我们可以对 $r_i$（长度为 $k$ 的句子结尾恰好为韵部 $i$ 的方案数）累加 $f_{k-s_i}$，这段的代码实现如下：

f[0]=1;
for(int i=0;i<=k;i++)
    for(int type=1;type<=n;type++)
        if(i+s[type]<=k){
            f[i+s[type]] = (f[i+s[type]]+f[i])%mod;
            if(i+s[type]==k)
                r[c[type]] = (r[c[type]]+f[i])%mod;
        }

这一部分解决了，我们来看第二部分。

这一部分限定了押韵方式，但是容易发现方式与顺序无关，所以我们用一个数组 $a$ 来存下每种押韵方式有几行。

for(int i=1;i<=m;i++){
    do{
        ch=getchar();
    }while(ch<'A' || ch>'Z');
    a[ch]++;
}

然后遍历押韵方式，对于每一种押韵方式 $k$，都有 $n$ 种可能的取值，所以答案需要累乘 $\sum_{i=1}^n r_i^{a_k}$。

for(int i='A';i<='Z';i++)
    if(a[i]){
        tr=0;
        for(i64 j=1;j<=n;j++)
            tr = (tr + fpow(r[j],a[i])%mod)%mod;
        res = (res*(tr%mod))%mod;
    }

最终代码如下：

#include<stdio.h>

#define maxn 6007
#define mod 1000000007
typedef long long i64;

i64 s[maxn],c[maxn],f[maxn],r[maxn],n,m,k,res=1,tr,a[300];

char ch;

i64 fpow(i64 x,i64 p){
    i64 res=1;
    while(p){
        if(p&1)
            res = (res*x) % mod;
        p>>=1;
        x = (x*x) % mod;
    }
    return res % mod;
}

int main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",s+i,c+i);

   f[0]=1;
    for(int i=0;i<=k;i++)
        for(int type=1;type<=n;type++)
            if(i+s[type]<=k){
                f[i+s[type]] = (f[i+s[type]]+f[i])%mod;
                if(i+s[type]==k)
                    r[c[type]] = (r[c[type]]+f[i])%mod;
            }

    for(int i=1;i<=m;i++){
        do{
            ch=getchar();
        }while(ch<'A' || ch>'Z');
        a[ch]++;
    }

    for(int i='A';i<='Z';i++)
        if(a[i]){
            tr=0;
            for(i64 j=1;j<=n;j++)
                tr = (tr + fpow(r[j],a[i])%mod)%mod;
            res = (res*(tr%mod))%mod;
        }

    printf("%lld",res%mod);
    return 0;
}