引言

啊！又是没好的一天

题目大意

已知k(1<=k<=64)，对于每个仅包含[0,k-1]区间的整数的数组，定义其优美度为非空连续子数组之和为k的倍数的数量。 求有多少长的为n的数组，其优美都为t，答案对998244353取模。

思路

暴力枚举 本题我采用dp的做法 首先，正向模拟一波。随便给出一个数组，暴力枚举出非空连续子数组之和为k的倍数的数量，显然不行。首先想到是用前缀和（用sum表示）解决。而对于前缀和，由于它是k的几倍不重要，所以可以直接mod k 。

接下来计算方案数，可设numinum_i表示有多少sumx=isum_x=i 要使方案数：∑i=1k−1Cnumi2=t\sum_{i=1}^{k-1}C_{num_i}^{2}=t (组合数不知怎么打......) 另：根据前缀和，可以填出唯一的原数组。 所以，做题时可以只算前缀和数组，不考虑原数组。 现在，我们已经知道了计算方法，接下来就可以构造dp了

dp构造

设dpi,j,kdp_{i,j,k}， 表示已经使用了[0,i]区间内的数，填了j个位置，合法数为k的方案数。 转移方程：dpi,j,k=∑s=0jdpi−1,j−s,k−Cs2Cn−j+ssdp_{i,j,k}=\sum_{s=0}^jdp_{i-1,j-s,k-C_s^2}C_{n-j+s}^s 其中s=numis=num_i 最后答案为ans=dpk−1,n,tans=dp_{k-1,n,t}

献上代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=110;
const int M=(1<<12)+10;
const int mod=998244353;
ll c[N][N];
ll dp[N][N][M];
ll n,k,t;
void init(){
    for(int i=0;i<=100;i++) {
        for (int j=0;j<=i;j++) {
            if(!j)c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;//整前缀
        }
    }
    for(int j=0;j<=n;j++)
        dp[0][j][c[j+1][2]]=1;//初始化
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k>>t;
    init();
    for (int i=1;i<k;i++)
    	for (int j=0;j<=n;j++)
    		for (int u=0;u<=t;u++)
    			for (int l=0;l+j<=n;l++)
    				(dp[i][j+l][u+c[l][2]]+=dp[i-1][j][u]*c[j+l][l])%=mod;//转移
    cout<<dp[k-1][n][t];
    return 0;
}

另

这么搞时间复杂度O(n5)O(n^5)，容易超 这里另附来自 二巨佬带我一废物 的3毫秒代码（强） 我大为震撼。其实看不懂。 有兴趣研究研究？

#include<bits/stdc++.h>
typedef long long ll; 
const int MAXN=10086,N=10000,M=998244353;
int n,k,t,cnt,b[MAXN];
ll fac[MAXN],inv[MAXN],d[MAXN],ans;
ll fp(ll x,int a)
{
    ll p=1;
    for(;a;a>>=1,x=x*x%M)if(a&1)p=p*x%M;
    return p;
}
ll C(ll a,ll b)
{
    return (ll)fac[a]*inv[b]%M*inv[a-b]%M;
}
void work(int m)
{
    int i,j,kk,now1=n,now2=k;
    ll tot=1;
    for(i=1;i<=m;i++)
    {
        for(j=i;j<m&&b[j]==b[j+1];j++);
        tot=tot*C(now2,j-i+1)%M;now2-=j-i+1;
        for(kk=i;kk<=j;kk++)tot=tot*C(now1,b[kk]+1)%M,now1-=b[kk]+1;
        i=j;
    }
    if(now2<now1)return;
    tot=tot*C(now2,now1)%M*fac[now1]%M;
    ans=(ans+tot)%M;
}
void dfs(int x,int dep,int tot,int min)
{
    int i;
    if(d[n-tot-1]<x)return;
    if(dep>k)return;
    if(!x){work(dep);return;}
    for(i=min;i+1+tot<=n&&d[i]<=x;i++)b[dep+1]=i,dfs(x-d[i],dep+1,tot+i+1,i);
}
int main()
{
    int i;
    for(i=1;i<=N;i++)d[i]=i*(i+1)/2;
    for(fac[0]=i=1;i<=N;i++)fac[i]=(ll)fac[i-1]*i%M;
    inv[N]=fp(fac[N],M-2);
    for(i=N;i;i--)inv[i-1]=(ll)inv[i]*i%M;
    scanf("%d%d%d",&n,&k,&t),n++;
    dfs(t,0,0,1);
    printf("%lld",ans*fp(k,M-2)%M);
    return 0;
}

点个赞！