Algoogle

Algorithm for Programming Contest

AOJ 2182 Eleven Lover

Category: AOJ Tag: dp

Eleven Lover

問題概要


数列が与えられるので, その中の連続する部分列が11の倍数になっている個数を求めよ.

解法


あまりを考えてdpすればよい.
dp[i][j] := i-1番目の数であまりがjになる場合の数
とすれば更新はdを現在の位置の数とすると
dp[i+1][(10*j+d)%11] += dp[i][j]
となる.
部分列は各位置の数字(0を除く)を先頭にした場合を追加していけばいい.
dp[i+1][d] += d > 0

コード


(2182.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
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
string s;
int dp[80010][11], N;

bool input(){
    cin >> s;
    if(s == "0") return 0;
    return 1;
}

int solve(){
    memset(dp, 0, sizeof(dp));
    N = s.size();
    rep(i,N) {
        int d = s[i]-'0';
        dp[i+1][d] = d > 0;
        rep(j,11) if(dp[i][j])
            dp[i+1][(10*j+d)%11] += dp[i][j];
    }
    int ans = 0;
    rep(i,N) ans += dp[i+1][0];
    return ans;
}

signed main(){
    while(input()){ cout << solve() << endl;}
    return 0;
}

Comments