hdu5657 CA Loves Math 分块

分块，K小的时候dp，K大的时候直接枚举K的倍数然后判断。

已经尽力优化了，还是没过，，，先留代码，有时间再改。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=1e9+10;

const int MOD=3010;
int A,n,K;
ll dp[12][(1<<11)+10][MOD+10];
int cnt[maxn];

int Cnt(int x)
{
    int res=0;
    while(x){
        if(x%A) res++;
        x/=A;
    }
    return res;
}

ll DP()
{
    if(n==0) return K==1?1:0;
    int len=min(A,n);
    REP(i,0,len) REP(j,0,(1<<A)-1) REP(k,0,K-1) dp[i][j][k]=0;
    dp[0][0][0]=1;
    REP(i,0,len-1){
        REP(j,0,(1<<A)-1){
            if(cnt[j]<i) continue;
            REP(k,0,K-1){
                REP(l,0,A-1){
                    if((j&(1<<l))==0){
                        dp[i+1][j|(1<<l)][(k*A+l)%K]+=dp[i][j][k];
                    }
                }
            }
        }
    }
    ll res=0;
    REP(j,0,(1<<A)-1) res+=dp[len][j][0];
    return res;
}

bool vis[12];
bool check(ll x)
{
    int t=0;
    MS0(vis);
    while(x){
        t=x%A;
        if(vis[t]) return 0;
        vis[t]=1;
        x/=A;
    }
    return 1;
}

ll qpow(ll n,ll k)
{
    ll res=1;
    while(k){
        if(k&1) res*=n;
        n*=n;
        k>>=1;
    }
    return res;
}

ll Force()
{
    ll res=0;
    ll limit=qpow(A,min(n,A));
    for(ll i=K;i<=limit;i+=K){
        if(!check(i)) continue;
        res++;
    }
    return res;
}

void Init()
{
    REP(i,0,(1<<A)) cnt[i]=Cnt(i);
}

int main()
{
    freopen("in.txt","r",stdin);
    int T;cin>>T;
    while(T--){
        scanf("%d%d%d",&A,&n,&K);
        Init();
        ll ans=0;
        if(K<MOD) ans=DP();
        else ans=Force();
        printf("%I64d
",ans);
    }
    return 0;
}
/**
3
10 2 7
11 2 3
2 10 1
*/