AtCoder Beginner Contest 262（D-E)

D - I Hate Non-integer Number

题意：一个长度为n的数组，选择其中的 x项，问其中有多少种选择，这x项的和可以被选择的数目整除，比如，选择3个数，和为6，那么6/3=2，就可以被整除。

题解: 每个数有选与不选两种可能，dp，观察数据，1<=a[i]<=1e9，所以数组中不能存储总和，会爆，而两项之间其实有关系的是被求余之后的数，所以存储余数即可。

dp[i][j][k]表示的是前i个数中，选择j个，然后余数为k的个数，所以 dp[i][j][(k+a[i])%z]+=dp[i-1][j-1][k];

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int N=2e5+5;
const ll inf=1e18;
const ll mod=998244353;
ll dp[105][105][105];
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(0);cout.tie(0);
  ll n;cin>>n;
  vector<ll> a(n+1,0);
  for(ll i=1;i<=n;i++) cin>>a[i];
  ll ans=0;
  for(ll z=1;z<=n;z++){//对于除不同的数之间，他们可以看成不同的部分，之间并不影响，所以可以分开算
  memset(dp,0,sizeof(dp));
  dp[0][0][0]=1;
  for(ll i=1;i<=n;i++){
    for(ll j=0;j<=z;j++){
      for(ll k=0;k<z;k++){
        dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k])%mod;
        if(j) dp[i][j][(k+a[i])%z]=(dp[i][j][(k+a[i])%z]+dp[i-1][j-1][k])%mod;//这里是对z求余，因为求的是最后z个数的情况
      }
    }
   }
   ans=(ans+dp[n][z][0])%mod;
  }
  cout<<ans;
}