Codeforces Round #235 (Div. 二)

Codeforces Round #235 (Div. 2)

A,B,C水题，没啥好说的。

D:

dp[i][j]:现在用的数的状态为i，余数为j的数量

st[i]:使用数i，需要增加的状态

need[i]:使用数i最多可以增加到的状态。

pan[i]:状态i所在的区间。

dp[k+st[j]][(i*10+j)%m]+=dp[k][i];

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL __int64
LL dp[1<<18][101];
LL st[10];
LL pan[10];
LL num[11];
LL need[11];
int main()
{
    LL n,m;
    LL i,j,k,t;
    while(~scanf("%I64d%I64d",&n,&m))
    {
        memset(num,0,sizeof(num));
        memset(pan,0,sizeof(pan));
        LL len=0;
        while(n)
        {
            len++;
            num[n%10]++;
            n=n/10;
        }
        LL ls=0;
        LL as=0;
        for(i=0; i<=9; i++)
        {
            if(num[i]==0)continue;
            LL li=0;
            LL tt;
            tt=num[i];
            while(tt)
            {
                li++;
                tt=tt/2;
            }
            tt=num[i];
            st[i]=(1<<ls);
            as=as+(tt<<ls);
            need[i]=tt<<ls;
            ls+=li;
            pan[i]=((1<<ls)-1)-(st[i]-1);
        }
        dp[0][0]=1;
        k=as;
        for(k=0;k<=as;k++)
        {
            for(j=0;j<=9;j++)
            {
                if(k==0&&j==0)continue;
                if((k&pan[j])>=need[j])continue;
                for(i=0;i<m;i++)
                {
                    dp[k+st[j]][(i*10+j)%m]+=dp[k][i];
                }
            }
        }
        LL sum=0;
        sum=dp[as][0];
        cout<<sum<<endl;
    }
    return 0;
}