[DP] ABC262 D - I Hate Non-integer Number

传送门
$f_{k,j,l}$中$k$为已选数个数，$j$为要求选数个数，也是模数（对于一个数只有其对选数个数的模数有效），$l$是目前这些数模$j$的余数，于是又状移方程
$$f_{k,j,l}\to f_{k+1,j,(l+a[i])modj}$$
初状态f[0][j][0]=1
$ans=\sum f_{j,j,0}$

数据小，考虑DP

#include
using namespace std;
#define in Read()

int in{
    int i=0,f=1; char ch=0;
    while(!isdigit(ch)&&ch!='-') ch=getchar();
    if(ch=='-') f=-1, ch=getchar();
    while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48, ch=getchar();
    return i*f;
}

const int N=110;
const int MOD=998244353;
int n,a[N],ans,f[N][N][N];

int main(){

    // freopen("1.in","r",stdin);

    n=in;
    for(int i=1;i<=n;++i) a[i]=in;
    for(int j=1;j<=n;++j){
        f[0][j][0]=1;
        for(int i=1;i<=n;++i){
            int m=a[i]%j;
            for(int k=i-1;k>=0;--k)
                for(int l=0;l<j;++l){
                    (f[k+1][j][(l+m)%j]+=f[k][j][l])%=MOD;
                }
        }
    }

    for(int i=1;i<=n;++i) (ans+=f[i][i][0])%=MOD;
    printf("%d\n",ans);
    return 0;
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38