Algoogle

Algorithm for Programming Contest

AOJ 2326 Number Sorting

Category: AOJ Tag: dp, math

Number Sorting

問題概要


閉区間[A,B]の間の部分列に順番がその辞書順と同じになるものはいくつあるか

解法


まず簡単なDPを考えると
dp[i] := iが最後になる数列の場合の数
となって2重ループで求められることがわかる

1
2
3
4
for i in [A,B]
    for j in [i+1,B]
        if lex_ord(i,j)
            dp[j] += dp[i]

しかしこれだと間に合わない.
数iより大きくて辞書順で小さくなる数jを考える.
例えばiを27とするとjは[100,270), [1000,2700), [10000,27000), …となる.
このことからそれ以外の区間全体ににdp[i]を足してやることを考えれば良い.
このことを踏まえたDPを考えると
dp[i] := iに足される数の変化量
とすると前の例では足す数をgvとすると
dp[27] += gv
dp[100] -= gv

とやればよい.

コード


(2326.cpp) download
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
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
int A, B, P, dp[100010];
inline void add(int &a, int b){ a=(a+b)%P;}
inline void sub(int &a, int b){ a=(a-b+P)%P;}
inline int f(int n){
    int c = 0;
    while(n > 0) { n/=10; c++;}
    return pow(10,c-1);
}

void calc(int n){
    int gv = dp[n-A], m = n;
    while(m < B){
        add(dp[m-A+(m==n)],gv);
        m *= 10;
        sub(dp[min(f(m),B)-A],gv);
    }
}

int solve(){
    memset(dp,0,sizeof(dp));
    dp[0] = 1;
    int ans = 0; B++;
    repi(i,A,B){
        if(i>A) add(dp[i-A],dp[i-A-1]);
        calc(i);
        add(ans,dp[i-A]);
    }
    return ans;
}

signed main(){
    while(cin >> A >> B >> P, A|B|P)
        cout << solve() << endl;
    return 0;
}

Comments