题解：P12607 三叉求和

SamHJD · 2025-05-27 19:24:26 · 题解

点 3x+y+1 的点权为 3a_x+y，统计每个点权相对于父节点点权的三倍多出的 y 的贡献，发现是 y\times \sum\limits_{i=0}^{d-dep} 3^i（根节点深度为 0）。于是可以从低位向高位进行 dp，设 f_{i,j,k} 表示考虑到深度为 i 时，剩余路径上选择的 y 的和为 j，进位到这一位的值为 k 的方案数。每次向后一位转移，将 j 减去 y\in[0,2]，进到后一位的值即为 \lfloor\frac{k}{3}\rfloor+(j-y)。

注意到有用状态数远小于 n^3，只转移非 0 的 f 即可通过，复杂度近似 O(n^2)。

#include <bits/stdc++.h>
#define rep(i,k,n) for(int i=k;i<=n;++i)
#define per(i,n,k) for(int i=n;i>=k;--i)
using namespace std;
template<typename T>
inline void read(T &x){
    x=0;int f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c-'0');
    x*=f;
}
template<typename T,typename ...Args>
inline void read(T &x,Args &...rest){read(x);read(rest...);}
const int N=3e3+10,MOD=1e9+7;
int n,a[N*3],vis[N*3],f[2][2*N][2*N];
vector<pair<int,int> > use[2];
string s;
vector<int> tran[2][N*2];
signed main(){
    read(n);
    cin>>s;
    reverse(s.begin(),s.end());
    rep(i,1,n){
        if(s[i-1]=='?') a[i]=-1;
        else a[i]=s[i-1]-'0';
    }
    rep(i,0,2*n) if(a[1]==-1||(i%3)==(a[1]%3)){
        f[1][i][i]=1,tran[1][i].push_back(i),use[1].push_back({i,i});
    }
    int i1=0,i2=1;
    rep(i,1,n){
        i1^=1;i2^=1;
        for(auto p:use[i2]) f[i2][p.first][p.second]=0;
        use[i2].clear();
        rep(j,0,2*(n-i+2)) tran[i2][j].clear();
        rep(j,0,2*(n-i+1)){
            for(auto k:tran[i1][j]){
                if(vis[k]) continue;vis[k]=1;
                if(f[i1][j][k]==0) continue;
                rep(x,0,2){
                    int j2=j-x;if(j2<0) break;
                    int num=(k/3)+j2;
                    if(a[i+1]!=-1&&a[i+1]%3!=num%3) continue;
                    (f[i2][j2][num]+=f[i1][j][k])%=MOD;
                    use[i2].push_back({j2,num});
                    tran[i2][j2].push_back(num);
                }
            }
            for(auto k:tran[i1][j]) vis[k]=0;
        }
    }
    printf("%d\n",f[i2][0][0]);
    return 0;
}