AtCoder Beginner Contest 276 G - Count Sequences 差分

题意：

问你有多少序列 $A=(a_1,a_2,...,a_n)$
满足：

• $a[i]\%3\ne a[i-1]\%3$
• $a[i-1]\le a[i]\le M$

前言：

乍一看，好像要dp，可能可以用数据结构瞎搞，但是$1e7$的数据，只能想其他方法

思路：

step0 转换为差分数组

$B=(b_1,b_2,...,b_n)$
$b_1=a_1$
$b_i=a[i]-a[i-1](i\ge 2)$

• $b_i\ge 0$
• 对$b[i]\%3$, 有 b 2 , b 3 , . . . , b n ∈ { 1 , 2 } b2,b3,...,b_n \in \{1,2\} b2,b3,...,bn​∈{1,2}
• $\sum b_i\le M$

那么问题就转换为了 $B$有多少种方案。

step1

对$b[i]\%3$, 有 b 2 , b 3 , . . . , b n ∈ { 1 , 2 } b2,b3,...,b_n \in \{1,2\} b2,b3,...,bn​∈{1,2}
b i = { 1 ∣ 2 } + k i ∗ 3 ( i ≥ 2 ) b_i = \{1|2\} + k_i*3 (i \ge 2) bi​={1∣2}+ki​∗3(i≥2)
b 1 = { 0 ∣ 1 ∣ 2 } + k 1 ∗ 3 b_1 = \{0|1|2\} + k_1*3 b1​={0∣1∣2}+k1​∗3
那么我们先计算出，每个位置的可能结果，之后再乘上对于3的分配

step2

用dp去分配1，2

• 通过枚举 $b_1\%3$和余数

long dp1[] = new long[Math.max(n*3,m+1)];
        for(int o = 0; o < 3;o ++ ) for(int p = 0; p < 3; p ++ ){
            for(int i = 0; i <= n - 1; i ++ ){
                int nxt = i + o + p + (n-1);
                dp1[nxt] += C(i,n-1);
                dp1[nxt] %= mod;
            }
        }
1
2
3
4
5
6
7
8

step3

计算 $k_i$：的分配方法
可以转换为经典的分小球问题

x个小球，放入n个盒子(盒子中允许有空球）
ans = $C_{x+n-1}^{n-1}$
小球数为$\mathrm{0...}x$
ans = $C_{n-1}^{n-1}$ + $C_n^{n-1}$ + $C_{n+1}^{n-1}$+…+$C_{x+n-1}^{n-1}$
ans = $C_{n+x}^n=C_{n+x}^x$

for(int i = 0; i*3 <= M; i ++) {
	dp2[i*3] = C(i,n+i);
}
1
2
3

What‘s more

组合数学常用公式总结-更新中
这位大佬的MINT，的一些相关的函数

AC：

package com.hgs.atcoder.abc.contest276.g;

/**
 * @author youtsuha
 * @version 1.0
 * Create by 2022/11/5 23:51
 */
import java.util.*;
import java.io.*;
public class Main {
    static FastScanner cin;
    static PrintWriter cout;
    static long mod = 998244353;
    static long finv[];
    static long fact[];
    static long qpow(long a, long k, long p){
        long res = 1;
        while(k > 0){
            if(k%2==1) res = res*a%p;
            a = a*a%p;
            k >>= 1;
        }
        return res;
    }
    private static void init()throws IOException {
        cin = new FastScanner(System.in);
        cout = new PrintWriter(System.out);
        int mx = (int) (3e7+10);
        fact = new long[mx];
        finv = new long[mx];
        fact[0] = 1;
        for(int i = 1; i < mx; i ++ ) fact[i] = fact[i-1]*i%mod;
        finv[mx-1] = qpow(fact[mx-1], mod-2,mod);
        for(int i = mx - 2; i >= 0; i -- ) finv[i] = finv[i+1]*(i+1)%mod;
    }
    static long C(int a, int b){
        return fact[b]*finv[a]%mod*finv[b-a]%mod;
    }
    private static void close(){
        cout.close();
    }
    private static void sol()throws IOException {
        int n = cin.nextInt(), m = cin.nextInt();
        //dp1
        long dp1[] = new long[m+1];
        for(int o = 0; o < 3;o ++ ) for(int p = 0; p < 3; p ++ ){
            for(int i = 0; i <= n - 1; i ++ ){
                int nxt = i + o + p + (n-1);
                if(nxt > m) continue;
                dp1[nxt] += C(i,n-1);
                dp1[nxt] %= mod;
            }
        }
        //dp2
        long dp2[] = new long[m+1];
        for(int i = 0; i*3<= m; i ++ ) {
            dp2[i*3] = C(i,n+i);
        }
        //cal
        long ans = 0;
        for(int i = 0; i <= m; i ++ ) {
            ans += dp1[i]*dp2[m-i]%mod;
            ans %= mod;
        }
        cout.println(ans);
    }
    public static void main(String[] args) throws IOException {
        init();
        sol();
        close();
    }
}
class FastScanner {
    BufferedReader br;
    StringTokenizer st = new StringTokenizer("");

    public FastScanner(InputStream s) {
        br = new BufferedReader(new InputStreamReader(s));
    }

    public FastScanner(String s) throws FileNotFoundException {
        br = new BufferedReader(new FileReader(new File(s)));
    }

    public String next() throws IOException {
        while (!st.hasMoreTokens()){
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) { e.printStackTrace(); }
        }
        return st.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106