题解 | #Melborp Elcissalc#

题目大意

alt

解析

因为是数组之和是k的倍数，所以我们在运算时可以对k进行取余减小数字大小，这并不影响结果。然后我们来思考，如果我们直接求[0,P]的优美度那必定要超时，所以这里很容易想到前缀和 ~~差分之类的~~ 我们这里 $p r e_{i}$ =( $a_{i}$ + $pre_{i−1}$ )%mod 所以当 $p r e_{x}$ == $p r e_{y}$ 时 [x,y]区间就是一个提供优美度的（ $p r e_{x}$ 与 $p r e_{y}$ 之前相差了 x倍的k）我们设 $c n t_{x}$ 表示 $p r e_{i}$ =x的数量而提供优美度只需要挑出2个即 $C^2_{cnt_x}$ 由此可以算出优美度是
$\sum\limits_{i=0}^{k-1}C_{cnt_i}^2$

接下来我们用dp动态规划来记录每一个 $c n t_{i}$ 的优美度：设 $dp_{ijk}$ 表示区间[0，i-1]中填充了j个，提供的优美度为k所以转移方程式为：

$dp_{i,j,k}=\sum\limits_{s=0}^{j}dp_{i-1,j-s,k-C^2_s} \times C_{n-(j-s)}^s$
这里s是已填充的数量，所以就是用填充前的 $dp_{i-1,j-s,k-C^2_s}$ ,j-s是现在数量减去现在填充数量， $k - C_{s}^{2} k-C^2_s$ 是现在提供的优美度减去这一次的优美度，再乘上上一次未填充的n-(j-s)中挑s个的优美度，再将这每一次填充不同的数量累加起来。

~~这道题你要是想用dfs直接暴力其实也行，当然你要保证不会炸喽~~

献上代码

首先是组合数，我们可以用杨辉三角形直接求出，逆元自然也可彳亍 ~~（注意这里 ll 是开了define的但是我没放）~~

	yh[0][0]=yh[1][0]=yh[1][1]=1;
	for(ll i=2;i<=104;i++)
	{
		yh[i][0]=yh[i][i]=1;
		for(ll j=1;j<i;j++)	
		yh[i][j]=(yh[i-1][j-1]+yh[i-1][j])%mod;
	}

然后是完全体

#include<bits/stdc++.h> 
using namespace std;
#define mod 998244353
#define ll long long 
ll n,k,t;
ll yh[125][125];
ll dp[70][70][4866];

int main()
{
	scanf("%d%d%d",&n,&k,&t);
	yh[0][0]=yh[1][0]=yh[1][1]=1;
	for(ll i=2;i<=104;i++)
	{
		yh[i][0]=yh[i][i]=1;
		for(ll j=1;j<i;j++)	
		yh[i][j]=(yh[i-1][j-1]+yh[i-1][j])%mod;
	}
	for(ll i=0;i<=n;i++) dp[0][i][yh[i+1][2]]=1;//第0位也可是0所以i+1   
	for(ll i=1;i<k;i++)       
	{
        for(ll to=0;to<=n;to++)  
		{
            for(ll j=to;j<=n;j++)
			{
                for(ll g=yh[to][2];g<=t;g++)
				{
                    dp[i][j][g]=(dp[i][j][g]+yh[j][to]*dp[i-1][j-to][g-yh[to][2]]%mod)%mod;
                }
            }
        }
    }
    cout<<dp[k-1][n][t]<<"\n";
}