• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

题解 【AT5695 [AGC041D] Problem Scores】

开发技术 开发技术 2小时前 2次浏览

(largemathcal{Description})

给定 (n, m), 求有多少个数列 ({A_i}) 长度为 (n) 且满足:

  • 对于任意 (i in [2, n],A_{i-1} leq A_{i}).
  • 对于任意 (i in [1, n],1 leq A_{i} leq n).
  • 对于任意一个大小为 (k(1 leq k < n)) 的子集 (S) 和任意一个大小为 (k+1) 的题目子集 (T),需要满足:(sum_{x in S}A_x < sum_{xin T}A_x).

答案对 (m) 取模。

(largemathcal{Solution})

这题也太妙了吧!

明显第三个条件是比较棘手的。我们贪心地考虑下,是不是要使 (sum_{x in S}A_x) 最大,(sum_{xin T}A_x) 最小?又由第 (1) 个条件,明显 (S) 要取最后 (k) 个数,(T) 要取前 (k + 1) 个数。那么第三个条件就等价于:

[forall 1le k<n rightarrow sum_{i=1}^{k+1}A_i>sum_{i=n-k+1}^nA_i
]

然后我们下面分析一下 (n) 为奇数的情况,偶数同理。

  • (k>n/2) 时,前 (k + 1) 个数跟后面 (k) 个数有重叠部分,相互抵消后就转化成为了 (kle n/2) 的情况。
  • (k<n/2) 时,考虑 (k+1) 的情况,这时左式加上了一个较小的数,右式加上了一个较大的数。这时条件更不容易满足,故我们只需考虑 (k=n/2) 的情况。

现在我们有三个条件((n) 为奇数时)

[begin{cases}i in [2, n],A_{i-1} leq A_{i}\i in [1, n],1 leq A_{i} leq n\sum_{i=1}^{n/2+1}A_i>sum_{i=n/2+2}^nA_iend{cases}
]

这个时候我们就可以令 (X_A=sum_{i=1}^{n/2+1}A_i-sum_{i=n/2+2}^nA_i), 考察它的变化情况。

我们现在我关注点放在第 (1) 个条件上,我们可以这样考虑:

  • (A_i) 初始值都是 (n), 然后操作若干次,每一次操作把前面任意个数减去 (1).

比如说 (A={1,2,3,4}(A_1=1).) 可以这么考虑:

  1. 初始化 (A={4,4,4,4}).
  2. ({4,4,4,4} rightarrow {3,3,3,4})
  3. ({3,3,3,4} rightarrow {2,2,3,4})
  4. ({2,2,4,4} rightarrow {1,2,3,4})

从这种角度出发,初始时 (X_A=n.) 然后对 (1sim i) 操作一次时 (X_A) 的变化 (w_i) 是可以与处理出来的。最后这个问题就变成了一道 完全背包问题

(n) 种物品(即操作),每一种都有无限个,第 (i) 种物品重量为 (w_i),现在要选出一些物品使得总重不超过 (n-1), 求方案数。

然后再不会就自裁吧。

题解 【AT5695 [AGC041D] Problem Scores】

(largemathcal{Code})

int n, m, k, w[N], f[N], ans; 

int main()
{
    cin >> n >> m;

    for (reg int i = 1; i <= (n + 1) / 2; ++ i) w[i] = i;
    for (reg int i = (n + 3) / 2; i <= n; ++ i) w[i] = n + 1 - i;
    
    f[n] = 1;
    for (reg int i = n; i >= 1; -- i)
        for (reg int j = n; j >= w[i]; -- j)
            f[j - w[i]] = (f[j] + f[j - w[i]]) % m;
    for (reg int i = 1; i <= n; ++ i) ans = (ans + f[i]) % m;
    printf("%dn", (ans + m) % m);
    
    return 0;
}

程序员灯塔
转载请注明原文链接:题解 【AT5695 [AGC041D] Problem Scores】
喜欢 (0)