[ABC262D] I Hate Non-integer Number Solution
目录更好的阅读体验戳此进入
题面
已知一个长度为 \(N\) 的数列 \(a_1,a_2,\cdots a_N\),从数列中选出至少一个数,使选出的数平均数为整数,求有多少种这样的方案。
Solution
经典DP,考虑设状态 $ dp(i, j, p, k) $,表示考虑前 $ i $ 个数里选 $ j $ 个的和模 $ p $ 余 $ k $。
转移显然,即:
\[dp(i, j, p, k) \rightarrow dp(i + 1, j, p, k) \]\[dp(i, j, p, k) \rightarrow dp(i + 1, j + 1, p, (k + a_{i + 1}) \bmod{p}) \]最终答案即为 $ \sum_{i = 1}^n dp(N, i, i, 0) $。
然后需要注意转移过程中存在 $ j = 0 $,但答案不可以 $ j = 0 $,原因显然。
初始值即为 $ dp(1, 0, i, 0) = 1, dp(1, 1, i, a_1 \bmod{i}) = 1 $。
发现空间无法支持,故可以将 $ i $ 维滚动掉。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MOD (998244353ll)
template < typename T = int >
inline T read(void);
int N;
ll a[110];
ll dp[2][110][110][110];
ll ans(0);
int main(){
N = read();
for(int i = 1; i <= N; ++i)a[i] = read();
for(int i = 1; i <= N; ++i)dp[1][0][i][0] = 1, dp[1][1][i][a[1] % i] = 1;
for(int i = 1; i < N; ++i){
for(int j = 0; j <= 100; ++j)for(int p = 0; p <= 100; ++p)for(int k = 0; k <= 100; ++k)dp[!(i & 1)][j][p][k] = 0;
for(int j = 0; j <= i; ++j)
for(int p = 1; p <= N; ++p)
for(int k = 0; k < p; ++k)
(dp[!(i & 1)][j][p][k] += dp[i & 1][j][p][k]) %= MOD,
(dp[!(i & 1)][j + 1][p][(k + a[i + 1]) % p] += dp[i & 1][j][p][k]) %= MOD;
}
for(int i = 1; i <= N; ++i)(ans += dp[N & 1][i][i][0]) %= MOD;
printf("%lld\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
UPD
update-2023_01_07 初稿
标签:Non,return,int,题解,Number,ret,dp,define From: https://www.cnblogs.com/tsawke/p/17124311.html