bzoj1799: [Ahoi2009]self 同类分布

数位dp

先从1到162枚举各位数之和

s[i][j][k][l]表示i位数，第一位小于等于j，当前各位数字和为k，当前取模余数为l的方案数

然后脑补一下转移就行了

详见代码

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <algorithm>

#define ll long long

using namespace std;

ll P;

int bin[20];

bool vis[20][180][180];

ll s[20][10][180][180];

ll f(int n,int t,int sum,int mod);

void solve(int n,int sum,int mod){

	if (n<1) return;

	if (vis[n][sum][mod]) return;

	vis[n][sum][mod]=1;

	for (int i=0;i<10;++i)

		s[n][i][sum][mod]=f(n-1,9,sum-i,(mod-bin[n]*i%P+P)%P);

	for (int i=1;i<10;++i) s[n][i][sum][mod]+=s[n][i-1][sum][mod];

}

ll f(int n,int t,int sum,int mod){

	if (sum<0||n*9<sum||t<0) return 0;

	if (n<1) return mod==0;

	solve(n,sum,mod);

	return s[n][t][sum][mod];

}

int a[21],b[21],len0,len1;

int main(){

	ll L,R;

	scanf("%lld%lld",&L,&R);++R;

	for (len0=0;L;L/=10) a[++len0]=L%10;

	for (len1=0;R;R/=10) b[++len1]=R%10;

	bin[1]=1;

	ll ans=0;

	for (P=1;P<=len1*9;++P){

		for (int i=2;i<=len1;++i) bin[i]=bin[i-1]*10%P;

		ll ans0,ans1;

		memset(vis,0,sizeof(vis));

		for (int k=0;k<2;++k){

			swap(ans0,ans1);ans0=0;

			for (int i=1;i<=max(len0,len1);++i) swap(a[i],b[i]);

			swap(len0,len1);

			int now=P,nowmod=0;

			for (int i=len0;i;--i){

				ans0+=f(i,a[i]-1,now,nowmod);

				now-=a[i];nowmod=(nowmod-a[i]*bin[i]%P+P)%P;

			}

		}

		ans+=ans1-ans0;

	}

	printf("%lld\n",ans);

	return 0;

}

　　

代码写的好乱……