1416번: 팬 서비스

https://www.acmicpc.net/problem/1416


$O(k^2)$

먼저, a1+..+an=s 인 경우의 수를 구해주어야 한다.
이는 점화식
dp[0][0]=1
dp[n][s]=sum(가능한 j에 대해)(dp[n-1][s-j])
를 통해 구할 수 있다.
답은 (1조건)+(2조건)-(1조건&2조건)이다.
(1조건), (2조건) 경우의 수는 sum(i)(dp[k][i])로 같다.
(1조건&2조건)를 구하기 위해
처음 k개의 수 중 홀수 번째 항 합:s1, 짝수 번째 항 합:s2
나중 k개의 수 중 홀수 번째 항 합:s3, 짝수 번째 항 합:s4 라고 하면
가능한 임의의 합 s에 대해
s1+s2=s3+s4=s
s1+s3=s2+s4=s
즉, s1=s4, s2=s3가 성립한다.
따라서 (1조건&2조건)의 경우의 수는 sum(i,j)((dp[k/2][i]*dp[(k+1)/2][j])^2)이다.(여기서 나눗셈은 소수를 버린다.)

#include<cstdio>
#define mod 999983
const int MAX_K = 50;
int m, dp[MAX_K + 1][9 * MAX_K + 1], ck[10], r, s, c;
int main() {
    scanf("%d", &m);
    while (scanf("%1d", &c) != -1) ck[c] = 1;
    dp[0][0] = 1;
    for (int i = 1; i <= m; i++)
        for (int j = 0; j < 10; j++)
            if (ck[j]) for (int k = 9 * m; k >= j; k--) dp[i][k] = (dp[i][k] + dp[i - 1][k - j]) % mod;
    for (int i = 0; i <= 9 * m; i++) r = (r + 2LL * dp[m][i] * dp[m][i]) % mod;
    for (int i = 0; i <= 9 * m; i++) {
        for (int j = 0; j <= 9 * m; j++) {
            int t1 = dp[m / 2][i], t2 = dp[m - m / 2][j];
            r = (r + mod - (long long)t1*t2%mod*t1%mod*t2%mod) % mod;
        }
    }
    printf("%d", r);
    return 0;
}