UVA 12672 Eleven(DP)

12672 - Eleven

Time limit: 5.000 seconds

In this problem, we refer to the digits of a positive integer as the sequence of digits required to write
it in base 10 without leading zeros. For instance, the digits of N = 2090 are of course 2, 0, 9 and 0.
Let N be a positive integer. We call a positive integer M an eleven-multiple-anagram of N if and
only if (1) the digits of M are a permutation of the digits of N, and (2) M is a multiple of 11. You are
required to write a program that given N, calculates the number of its eleven-multiple-anagrams.
As an example, consider again N = 2090. The values that meet the first condition above are 2009,
2090, 2900, 9002, 9020 and 9200. Among those, only 2090 and 9020 satisfy the second condition, so
the answer for N = 2090 is 2.

Input
The input file contains several test cases, each of them as described below.
A single line that contains an integer N (1 ≤ N ≤ 10^100).

Output
For each test case, output a line with an integer representing the number of eleven-multiple-anagrams
of N . Because this number can be very large, you are required to output the remainder of dividing it
by 109 + 7.

Sample Input
2090
16510
201400000000000000000000000000

Sample Output
2
12
0

一条很好的DP题。

问一个数重排后（不包括前序0），有多少个数能够被整除11。

对于11的倍数，可以发现一个规律就是:

( 奇数位数字的总和 - 偶数为数字的总和）% 11 == 0的数能够被11整除

因为作为11的倍数，都符合：

77000 85481是可以被11整除的。　　　　　　　　　　　　

7700 因为它各个相邻位都有一个相等的性质。

770 对于奇数位要进位的话，相当于少加了10（即-10），同时偶数为多了1（即-1），还是符合被11整除

11 偶数为亦然，偶数为进位，相当于少减10 ，（即+10），同时奇数位多了1（即+1）。

------------

85481

那么，设一个 dp[i][j][k] 表示用了i位（0~9）数字，奇数位有j个数，余数是k的组合成的数有多少个。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int mod = 1e9+;

const int N =  ;

const int M =  ;

LL cnt[M] , dp[M][N][M] , C[N][N];

string s;

void Init() {

    C[][] =  ;

    for( int i =  ; i < N ; ++i ){

        for( int j =  ; j <= i ; ++j ){

            C[i][j]=(j==)?:(C[i-][j]+C[i-][j-])%mod ;

        }

    }

}

void Run() {

    memset( cnt ,  ,sizeof cnt ) ;

    memset( dp ,  ,sizeof dp ) ;

    int n = s.size() , n2 = n /  , n1 = n - n2 ;

    for( int i =  ; i < n ; ++i ) cnt[ -(s[i]-'') ]++ ;

    dp[][][] =  ; LL sum =  ;

    for( int i =  ; i <  ; ++i ) {                // digit

        for( int j =  ; j <= n1 ; ++j ) {           // odd used

            for( int k =  ; k <  ; ++k ) {        // remainder

                if( !dp[i][j][k] || j > sum ) continue ;

                int j1 = j , j2 = sum - j;

                for( int z =  ; z <= cnt[i] ; ++z ){

                    int z1 = z , z2 = cnt[i] - z ;

                    if( j1 + z1 > n1 || j2 + z2 > n2 ) continue ;

                    LL tmp = dp[i][j][k];

                    if( (n&) && i== ) tmp = tmp * C[j1+z1-][z1] % mod ;

                    else tmp = tmp * C[j1+z1][z1] % mod ;

                    if(!(n&) && i== ) tmp = tmp * C[j2+z2-][z2] % mod ;

                    else tmp = tmp * C[j2+z2][z2] % mod;

                    int _i = i +  , _j = j1 + z1 , _k = ( k + z1*(-i)-z2*(-i)+*)%;

                    dp[_i][_j][_k] = ( dp[_i][_j][_k] + tmp ) % mod ;

                }

            }

        }

        sum += cnt[i];

    }

    cout << dp[][n1][] << endl ;

}

int main(){

    Init(); while( cin >> s ) Run();

}

巴特西

UVA 12672 Eleven(DP)

12672 - Eleven

最新文章

热门文章