codeforces 1073 E.Segment Sum(디지털 dp 통계 와)

2066 단어 dp
제목 링크:http://codeforces.com/problemset/problem/1073/E
사고방식:디지털 dp 위치 에 따라 공헌 계산 과
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll inff = 0x3f3f3f3f3f3f3f3f;
#define FOR(i,a,b) for(int i(a);i<=(b);++i)
#define FOL(i,a,b) for(int i(a);i>=(b);--i)
#define REW(a,b) memset(a,b,sizeof(a))
#define inf int(0x3f3f3f3f)
#define si(a) scanf("%d",&a)
#define sl(a) scanf("%I64d",&a)
#define sd(a) scanf("%lf",&a)
#define ss(a) scanf("%s",a)
#define mod ll(998244353)
#define pb push_back
#define eps 1e-6
#define lc d<<1
#define rc d<<1|1
#define Pll pair
#define P pair
#define pi acos(-1)
ll a[20],n,m,k,b[20];
Pll dp[20][1028];
Pll dfs(int pos,int qw,bool zero,bool limit)
{
    if(!pos) return Pll(1,0);
    if(!limit&&dp[pos][qw].second!=-1) return dp[pos][qw];
    int up=limit?a[pos]:9;
    Pll res=Pll(0,0),tmp;
    FOR(i,0,up)
    {
        int zz=qw|((zero||i)<k) continue;
        tmp=dfs(pos-1,zz,zero||i,limit&&i==a[pos]);
        res.first=(res.first+tmp.first)%mod;
        res.second=(res.second+tmp.second+1ll*i*b[pos-1]%mod*tmp.first%mod)%mod;//tmp.first              
    }
    if(!limit) dp[pos][qw]=res;
    return res;
}
ll query(ll n)
{
    a[0]=0;
    while(n) a[++a[0]]=n%10,n/=10;
    return dfs(a[0],0,0,1).second;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    REW(dp,-1);
    b[0]=1;FOR(i,1,19) b[i]=b[i-1]*10ll%mod;
    sl(n),sl(m),sl(k);
    ll x=query(m);
    ll y=query(n-1);
    printf("%I64d
",((x-y)%mod+mod)%mod);
    return 0;
}

RestTemplate 와 Feign 통신 사용 하기
Leetcode sql 알고리즘 문제

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage