程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LA 6529 Eleven dp

LA 6529 Eleven dp

編輯：關於C++

題意：給一個數字串，可以調換數字，問有多少種組合可以讓組成的數能被11整除。

思路：窩們觀察到1%11=1, 10%11=10,100%11=1,1000%11=10，以此類推。。窩們將一偶一奇看作一對，這一對組成對11的余數

×100對11的余數(也就是1)，所以實質還是這一對對11的余數，那麼奇偶數位的和就可以了。我們可以設奇數位的和為x，偶數位的

和為y，則(x+10y)%11的值為0就可以了--> (x-y+11y)%11=0 --> (x-y)%11=0。所以設dp[i][j][k]表示處理完0到i-1，已在奇數位放了j個

數字,(奇數位數字和-偶數位數字和)%11=k的種數，詳見代碼：

/*********************************************************
  file name: LA6529.cpp
  author : kereo
  create time:  2015年02月04日 星期三 20時39分19秒
*********************************************************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=15;
const int MAXN=100+10;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=1000000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair
#define mk(x,y) make_pair((x),(y))
char str[MAXN];
int num[N];
ll C[MAXN][MAXN];
ll dp[N][MAXN][N];//dp[i][j][k]表示處理完0到i-1，已在奇數位放了j個數字,(奇數位數字和-偶數位數字和)%11=k的種數
void init(){
    for(int i=0;i>1;
    for(int i=0;i<10;i++){ //處理的數位
        for(int j=0;j<=sum && j<=n;j++){ //已放在奇數位的個數
            for(int k=0;k<=num[i] && k<=n-j;k++){ //這次在奇數位放的個數
                int x=((2*k-num[i])*i)%11;
                if(x<0)
                    x+=11;
                for(int st=0;st<=10;st++){
                    dp[i+1][j+k][(st+x)%11]=((((dp[i][j][st]*C[n-j][k])%mod)*C[len-sum-(n-j)][num[i]-k])%mod+dp[i+1][j+k][(st+x)%11])%mod;
                }
            }
        }
        sum+=num[i];
    }
    return dp[10][n][0];
}
int main(){
    init();
    while(~scanf("%s",str)){
        memset(num,0,sizeof(num));
        int n=strlen(str);
        for(int i=0;i