题解 AT1975 【[ARC058C] 和風いろはちゃん / Iroha and Haiku】

Werner_Yin · 2021-01-01 22:22:43 · 题解

谨以此文纪念2021年我的第一篇题解以及一位文化课选手（无意中看到题目）在想了3天后（当然是一边搞文化课一边想）终于解决了这道题，然后一发最优解（目前的）

upd:

• 1.7 修改部分笔误

更好的阅读体验

题意

求满足

• \forall i \in [0,n-1],a[i] \in [1,10]
• \exists x,y,z,w , 0 \leq x < y < z < w \leq n,\sum_{i=x}^{y-1}=X,\sum_{i=y}^{z-1}=Y,\sum_{i=z}^{w-1}=Z

长度为 n 数组 a

Solution

开始想从 n 下手，然而不太好搞，无意中看到 X,Y,Z 范围X+Y+Z <= 17,范围挺像状压的，然后就有思路了。

从左往右扫 a 数组的每一位来确定答案，那状压什么呢？

我们定义最后我们找的的满足条件的数组中[x,w-1] 为我们需要的部分（当然，一个数组可以有多个这种部分），如图(即有颜色的部分）。

而匹配的部分为[x,y-1] 或者 [x,z-1] , 即黄色部分 或者 黄色 + 蓝色的部分

我们要记录的是，所有可能的 需要的部分 剩下未匹配上的末尾和的可能值。

这个值一定十分小（X+Y+Z <= 17),状压一下就行了。

复杂度 \texttt{O(}2^{X+Y+Z}nt\texttt{)} , 其中 t = 10。

Code

为了节省空间，于是用了滚动数组。

为了方便转移，开了两个数组 ， f 代表的是还没有完成匹配的方案数， g 是代表完成匹配的方案数。

具体见代码吧。

const int mod = 1e9+7;
const int MAXN = 1<<17;

int ok,s[20],x,y,z,n,ful;
int top,f[2][MAXN],g[2],ans;

void add(int &x,int y){x=x+y;if(x>=mod) x-=mod;}

int getstu(int stu,int num){
    //获取新状态
    int newstu = 0;
    for(int i = 0;i + num < x+y+z;i++){
        if(stu >> i & 1){
            if(s[i + num - 1] - s[i] > 0) continue;
            //如果剩下部分的和大于我们所需要的（漏匹配），肯定不行
            newstu |= 1<<(i + num);
        }
    }
    if(num <= x) newstu |= 1<<(num-1);
    return newstu;
}

int main (){
    scanf("%d %d %d %d",&n,&x,&y,&z);
    s[x-1] = s[x+y-1] = s[x+y+z-1] = 1;
    for(int i = 1;i < x+y+z;i++) s[i] = s[i-1] + s[i];
    //前缀和方便判断
    ok = 1<<(x+y+z-1); ful = 1<<(x+y+z);
    f[0][0] = 1;
    for(int o = 0,i = 1;i <= n;i++,o = o^1){
        memset(f[o^1],0,sizeof(f[o^1]));
        g[o^1] = g[o] * 10ll % mod;
        //已经完成匹配的方案数
        for(int stu = 0;stu < ful;stu++)
            if(f[o][stu]){
                for(int j = 1;j <= 10;j++){
                    int ns = getstu(stu,j);
                    if(ns & ok) add(g[o^1],f[o][stu]);
                    else add(f[o^1][ns],f[o][stu]);
                }
            }
        if(i == n) ans = g[o^1];
    }
    printf("%d\n",ans);
    return 0;
}