UVALive 6529

题意：

　　给你一个串数字，可以按任意顺序排列，求有几种排列可以使他们组成的数字可以被11整除。

思路：

　　和前几天那个被9整除的思想类似，1%11=1,10%11=10,100%11=1,1000%11=10.....容易观察出，设奇数位的和为x，偶数位的和为y，则(x+10y)%11的值为0就可以了--> (x-y+11y)%11=0 --> (x-y)%11=0。

　　然后就可以dp做了dp[i][j][k]分别表示，当前在放数字i-1，之前已经放了j个数字，现在(x-y)%11的值为k。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MOD 1000000007
typedef long long LL;
LL C[110][110],num[15];
LL dp[11][101][11];

char ch[110];
void init(){
    C[0][0]=C[1][0]=C[1][1]=1;
    for(int i=2;i<=100;i++){
        for(int j=0;j<=i;j++){
            if(j==0) C[i][j] = 1;
            else C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
}

LL cal(int len){
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;
    int sum = 0; int need = (len+1)>>1;
    for(int i=1;i<=10;i++){
        for(int j=0;j<=sum && j<=need;j++){
            for(int k=0;k<=num[i-1] && (j+k)<=need;k++){
                int change = (2*k-num[i-1])*(i-1)%11;
                if(change<0) change+=11;
                for(int l=0;l<11;l++){
                    int next = (change + l)%11;
                    dp[i][j+k][next] = (dp[i][j+k][next] + dp[i-1][j][l] * C[need-j][k] %MOD* C[len-need-sum+j][num[i-1]-k] %MOD)%MOD;
                }
            }
        }
        sum+=num[i-1];
    }
    return dp[10][need][0];
}

void solve(){
    memset(num,0,sizeof(num));
    for(int i=0;ch[i];i++){
        num[ch[i]-'0']++;
    }
    int len=strlen(ch);
    LL ans = cal(len);
    if(num[0]){
        num[0]--;
        LL ans2 = cal(len-1);
        ans=((ans-ans2)%MOD+MOD)%MOD;
    }
    cout<<ans<<endl;
}

int main(){
    init();
    while(scanf("%s",ch)!=EOF){
        solve();
    }
    return 0;
}