uoj#311 【UNR #2】积劳成疾

我不是女神ヾ 2023-10-11 11:17 63阅读 0赞

[题目][Link 1]

考虑直接顺着从\\(1\\)填数填到\\(n\\)发现这是在胡扯

所以考虑一些奇诡的东西，譬如最后的答案长什么样子

显然某一种方案的贡献是一个\\(\\prod\_\{i=1\}^nw\_i^\{t\_i\}\\)状物，\\(t\_i\\)表示\\(i\\)在多少个长度为\\(m\\)的区间里为最大值

而这里又是最大值，所以可以考虑从大到小填数，每次把填完之后相应的分裂区间，同时在这个时候也可以计算一些贡献

于是我们设\\(f\_\{l,r,k\}\\)表示对于区间\\(\[l,r\]\\)最大值为\\(k\\)，我们枚举这个最大值最后一次出现的位置，同时跨过这个位置长度为\\(m\\)的区间的最大值肯定是\\(k\\)了，于是我们在这里就可以计算出\\(w\_k\\)的贡献

于是有

\\\[f\_\{l,r,k\}=\\sum\_\{i=l\}^\{r\}w\_k^\{calc(r-l+1,i)\}\\sum\_\{j=1\}^kf\_\{l,i-1,j\}\\times \\sum\_\{j=1\}^\{k-1\}f\_\{i+1,r,j\}\\\]

其中\\(calc(r-l+1,i)\\)表示对于一个长度为\\(r-l+1\\)的序列，有多少个长度为\\(m\\)的区间跨过\\(i\\)位置

发现这里能维护前缀和就能快速转移了

答案就是\\(\\sum\_\{i=1\}^nf\_\{1,n,i\}\\)

同时我们发现这里维护区间太奢侈了，只要有一个区间长度我们就能转移了，所以我们直接改为维护区间长度

状态数\\(n^2\\)，转移复杂度\\(O(n)\\)，复杂度为\\(O(n^3)\\)

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    const int mod=998244353;
    const int maxn=403;
    int n,m,w[maxn];
    int dp[maxn][maxn],vis[maxn][maxn],a[maxn][maxn],b[maxn][maxn];
    inline int ksm(int a,int b) {
        int S=1;
        for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) S=1ll*S*a%mod;
        return S;
    }
    int f(int l,int k) {
        if(!l) return 1;
        if(!k) return 0;
        if(vis[l][k]) return dp[l][k];
        if(l<m) {
            vis[l][k]=1;
            return dp[l][k]=ksm(k,l);
        }
        if(k>1) dp[l][k]=f(l,k-1);
        for(re int i=0;i<l;i++)
            dp[l][k]=(dp[l][k]+1ll*f(i,k)*f(l-i-1,k-1)%mod*a[k][b[l][i+1]]%mod)%mod;
        vis[l][k]=1;
        return dp[l][k];
    } 
    int main() {
        scanf("%d%d",&n,&m);
        for(re int i=1;i<=n;i++) a[i][0]=1;
        for(re int i=1;i<=n;i++) scanf("%d",&a[i][1]),w[i]=a[i][1];
        for(re int i=1;i<=n;i++) 
            for(re int j=1;j+m-1<=i;j++)
                for(re int k=j;k<=j+m-1;k++)
                    b[i][k]++;
        for(re int i=1;i<=n;i++)
            for(re int j=2;j<=n;j++)
                a[i][j]=1ll*a[i][j-1]*w[i]%mod;
        printf("%d\n",f(n,n));
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11358621.html

[Link 1]: http://uoj.ac/problem/311