2019hongkongicpc J - Junior Mathematician(压缩状态的数位DP)
看起来似乎是很裸的数位dp
不难想到我们需要维护一个数位前缀和 s u m n sumn sumn用于计算 f ( x ) f(x) f(x)
我们还需要记录当前枚举值 f ( x ) % m f(x)\%m f(x)%m的值
我们还需要记录 x % m x\%m x%m的值
但是这样复杂度超标
我们发现可以直接维护 f ( x ) − x f(x)-x f(x)−x的值,因为模数相同
如果第 l e n len len位选择的是 i i i
由 于 我 们 维 护 了 l e n − 1 位 时 的 f ( x ) − x 由于我们维护了len-1位时的f(x)-x 由于我们维护了len−1位时的f(x)−x
那 么 此 时 转 移 就 是 ( f ( x ) + s u m n ∗ i ) − ( x + i ∗ 1 0 l e n ) 那么此时转移就是(f(x)+sumn*i)-(x+i*10^{len}) 那么此时转移就是(f(x)+sumn∗i)−(x+i∗10len)
这样优化掉一维度,就可以了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=3e5+10;
char l[maxn],r[maxn];
ll dp[5009][75][75];
int ppow[5009],a[5009],en,n,m;
int dfs(int len,int limit,int nowmod,int sumn)
{
//nowmod是当前数对m的和,he是前缀和,
if( len==0 ) return !nowmod;
if( !limit&&dp[len][nowmod][sumn]!=-1 )
return dp[len][nowmod][sumn];
ll last=limit?a[len]:9,ans=0;
for(int i=0;i<=last;i++)
{
int fx=nowmod+sumn*i-i*ppow[len-1]+m;
ans+=dfs(len-1,limit&&(i==a[len]),(fx%m+m)%m,(sumn+i)%m);
}
ans=(ans%mod+mod)%mod;
if( !limit ) dp[len][nowmod][sumn]=ans;
return ans;
}
int solve(char b[])
{
en=strlen(b+1);
for(int i=0;i<=en;i++)
for(int j=0;j<m;j++)
for(int q=0;q<m;q++)
dp[i][j][q]=-1;
for(int i=1;i<=en;i++)
a[i]=b[en-i+1]-'0';
return dfs(en,1,0,0);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ppow[0]=1;
int t; cin >> t;
while( t-- )
{
cin >> (l+1) >> (r+1);
cin >> m;
int rr=strlen(r+1);
for(int i=1;i<=rr;i++) ppow[i]=ppow[i-1]*10%m;
int en=strlen(l+1);
l[en]--;
for(int i=en;i>=1;i--)
if( l[i]<'0' ) l[i]+=10,l[i-1]--;
else break;
cout << ( solve(r)-solve(l)+mod )%mod << '\n';
}
}
本文地址:https://blog.csdn.net/jziwjxjd/article/details/108567471
上一篇: Android自定义验证码输入框