BOJ 1416 - 팬 서비스

BOJ 1416 - 팬 서비스

Solution 1

$O(K \cdot 9K \cdot 18K)$ 정도로 푸는 풀이로 먼저 통과했다.

$dp[i][j][k]$ 를 $i$ 번 째 수까지 채웠을 때 합이 $j$ 이고 짝수 - 홀수 = $k$ 인 경우의 수라고 하자.

포함 배제의 원리로 1번 조건 만족 + 2번 조건 만족 - 1번, 2번 조건 모두 만족을 하는것이 정답이다.

각 $j$와 각 $k$에 대해 포함되는 모든 값을 미리 더해서 전처리해두면 세가지 모두 $O(9 \cdot 18 \cdot K^2)$ 에 구할 수 있다.

공간복잡도를 위해 토글링을 해야한다.

const ll mod = 999983;  
inline ll md(ll x) { return md(mod, x); }  
template<class T>  
inline void mds(T &a, T b) { a = md(a + b); }  
template<class T>  
inline void mdp(T &a, T b) { a = md(a * b); }  
vi in;  
int k;  
// i 번째까지, 총합이 j이고, 짝수 - 홀수가 k인 것의 경우의 수  
int dp[2][455][1000];  
int sum_sum[455];  
int sum_diff[1000];  
const int o = 500;  
void solve() {  
   cin >> k;  
   string s;  
   cin >> s;  
   for (char c: s) in.pb(c - '0');  
   sort(all(in));  
  
   dp[0][0][o] = 1;  
   for (int i = 1; i <= k; i++) {  
      int I = i % 2, J = I ^ 1;  
      memset(dp[I], 0, sizeof dp[I]);  
      for (int d: in) {  
         for (int sum = 0; sum <= 9 * i; sum++) {  
            for (int diff = -i * 9; diff <= i * 9; diff++) {  
               if (sum - d >= 0) {  
                  int nxt = i % 2 == 1 ? diff + d : diff - d;  
                  nxt += o;  
                  if (nxt >= 0 && nxt < 1000)  
                     mds(dp[I][sum][diff + o], dp[J][sum - d][nxt]);  
               }  
            }  
         }  
      }  
   }  
   ll ans_all = 0, ans1 = 0, ans2 = 0;  
  
   for (int sum = 0; sum <= k * 9; sum++) {  
      for (int diff = -k * 9; diff <= k * 9; diff++) {  
         mds(sum_sum[sum], dp[k & 1][sum][diff + o]);  
         mds(sum_diff[diff + o], dp[k & 1][sum][diff + o]);  
      }  
   }  
  
   for (int sum = 0; sum <= k * 9; sum++) {  
      for (int diff = -k * 9; diff <= k * 9; diff++) {  
         mds(ans1, 1ll * dp[k & 1][sum][diff + o] * sum_sum[sum]);  
         mds(ans2, 1ll * dp[k & 1][sum][diff + o] * sum_diff[diff + o]);  
         mds(ans_all, 1ll * dp[k & 1][sum][diff + o] * dp[k & 1][sum][diff + o]);  
      }  
   }  
   cout << md(ans1 + ans2 - ans_all);  
}

Solution 2

조건을 좀 더 살펴보자.

$K$ 가 짝수일 때 기준으로,

$1$번 조건은 $\sum A+\sum B=\sum C + \sum D$ 를 의미한다.

$2$번 조건은 $\sum A + \sum C = \sum B + \sum D$ 를 의미한다.

연립하면 $\sum B=\sum C$ 이다. 또한 이로써 $\sum A = \sum D$ 도 얻는다.

따라서 $dp$를 그냥 $dp[i][j]=i$ 번째 수까지 채웠을 때 합이 $j$ 가 되는 것이라고 해보자. $O(K \cdot 9K)$ 에 구할 수 있다.

$1$번 조건의 경우의 수는 그냥 $\sum dp[k][j]^2$ 이다.

$2$번 조건의 경우의 수도 따지고보면 $1$번 조건의 경우의 수와 다를수 없다.

따라서 구한 값에 $\times2$ 를 해주자.

$3$번 조건의 경우의 수는 $B=C ~ \& ~ A=D$ 를 만드는 경우의 수이다.

$K$의 기우성에 관계없이 $\sum dp[ \left\lfloor \frac{k}{2} \right\rfloor][j]^2$ 와 $\sum dp[ \left\lfloor \frac{k+1}{2} \right\rfloor][j]^2$ 를 곱한값을 $1$번 조건의 경우의 수에 두배한 것에서 빼면 된다.