有道难题测试赛第三题

[higer]

Problem Statement
    
A wicked teacher is trying to fail one of his students. He gives him
the following problem: You are given a String[] numbers containing a
set of distinct integers. You can concatenate some permutation of
these integers to obtain one large integer. For example, the
permutation {5221, 40, 1, 58, 9} can be concatenated to form
5221401589. Find a permutation of the given numbers such that its
concatenation is divisible by the integer K. The student doesn't have
a clue how to solve this problem, so he just answers with some random
permutation. There may be multiple correct answers, and maybe the
student has chosen one of them by chance. Return the probability that
the student has chosen one of the correct answers and return it as a
String in the form of an irreducible fraction "p/q" (quotes for
clarity), where p is the fraction's numerator and q is its
denominator. Assume that each permutation has the same probability of
being chosen.
Definition
    
Class:
WickedTeacher
Method:
cheatProbability
Parameters:
String[], int
Returns:
String
Method signature:
String cheatProbability(String[] numbers, int K)
(be sure your method is public)
    

Constraints
-
numbers will contain between 1 and 15 elements, inclusive.
-
Each element of numbers will contain between 1 and 50 characters,
inclusive.
-
Each element of numbers will contain digits ('0'-'9') only.
-
Each element of numbers will begin with a non-zero digit.
-
Elements of numbers will be distinct.
-
K will be between 1 and 100, inclusive.
Examples
0)

    
{"3","2","1"}
2
Returns: "1/3"
If the student chooses a permutation where the number 2 is the last
element, the concatenation will be divisible by 2.
1)

    
{"10","100","1000","10000","100000"}
10
Returns: "1/1"
No matter which permutation the student chooses, its concatenation
will be divisible by 10.
2)

    
{"11","101","1001","10001","100001"}
10
Returns: "0/1"
It's possible that the teacher is cheating, and no correct answer is
possible.
3)

    
{"13","10129414190271203","102","102666818896","1216","1217","1218","101278001","1000021412678412681"}
21
Returns: "5183/36288"

This problem statement is the exclusive and proprietary property of
TopCoder, Inc. Any unauthorized use or reproduction of this
information without the prior written consent of TopCoder, Inc. is
strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

[higer]

这道题我是按照一般的大整数除法来做的，时间复杂度比较高，所以超时了，不知道大家有没有更好的办法来解决这个问题。
另外，它的除数是在1到100之间，所以简单的使用大整数除法貌似是不行的，但是我也想不到更好的办法了。

[苏峰]

将所有排列按MOD K，分成K类 余数为 0，1，...,K-1;可以考虑状态dp，bit运算遍历集合
考虑dp:  f[1<<n][K] (1<<n)-1 表示集合 状态转移方程 :f[(1<<j)|i][(k*(10^j个元素位数)+(j MOD K)) MOD K ]  +=dp[i][k];f[（1<<n）-1][K-1] 表示n个元素 concat 时，余K-1 的元素个数，结果考虑分子，分母为0时的情况。

代码如下：  

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <utility>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <ctime>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
#define ALL(c) (c).begin(),(c).end()
#define MP(x, y) make_pair((x), (y))

typedef long long ll;typedef vector<int> VI;
typedef vector<string> VS;typedef long double ld;

template<class T>inline int size(const T& c){return c.size();}
template<class T> inline T gcd(T a,T b)//NOTES:gcd(
{if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}

ll dp[1<<15][100];

class WickedTeacher
{
public:
    string cheatProbability(vector<string> numbers,int K);
};

string WickedTeacher::cheatProbability(std::vector<string> numbers, int K)
{
    int n=numbers.size();
    VI v1,v2;
    REP(i,n){
        int m=numbers[i].size();int a=0,b=1;
        REP(j,m){
            a=(a*10+(numbers[i][j]-'0'))%K;
            b*=10;
            b%=K;
        }
        v1.push_back(a);
        v2.push_back(b);
    }
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    REP(i,(1<<n))REP(j,n){
        if(!(i&(1<<j))){
            REP(k,K){
                dp[(1<<j)|i][(v2[j]*k+v1[j])%K]+=dp[i][k];
            }
        }
    }
    ll den=0,nume=0;
    REP(i,K) {den+=dp[(1<<n)-1][i];}
    nume=dp[(1<<n)-1][0];
    ll g=gcd(den,nume);
    den/=g,nume/=g;//cout<<den<<" "<<nume<<" "<<g<<endl;
    if(nume==0LL)return "0/1";
    if(den==0LL) return "0/0";
    else{
        stringstream ss;
        ss<<nume<<"/"<<den;
        return ss.str();
    }
}

2009/5/18 higer <higerin...@gmail.com>

[zhong nanhai]

猛！！！Topcoder上别人给出的答案就是这样的。

[苏峰]

这题我resubmit 一次，第一次才500出头，还是看题后的，真实提交估计也就2，3百

2009/5/25 zhong nanhai <higerin...@gmail.com>

[zhong nanhai]

什么500出头？