싫다

제목 링크
제목: m에서 n까지 출력하는 데 62와 4의 숫자가 포함되지 않습니다.
예를 들어 n=1, m=100, 그러면 62는 불법이고 41, 42, 43......다 불법이야.
사고방식: 우리는 0에서 m까지의 답안을 계산한 다음에 0에서 n까지의 답안을 계산한다. 상감하면 최종적으로 구하는 것이다.
그렇다면 어떻게 0에서 m의 답을 구할 수 있을까?물론 우리의 신기한 디지털 dp를 빌려서
우리는 우선 n의 숫자를 미리 처리해야 한다(예를 들어 100, 숫자는 3)
dp 방정식을 설정하고 dp[pos][sta][limit];pos: 이 수의 수위,sta=1은 현재 수위의 첫 번째 수위가 6,limit=0이라는 것을 나타낸다. 이것은 이 자리에 제한이 없다는 것을 의미한다. 1은 제한이 있고 제한이 있는 상계는 a[pos]이다. 그렇지 않으면 9이다.
예를 들어 n=2345,pos=2시, 즉 세 번째 숫자는 현재 두 자리만 23이고 세 번째만 제한이 있다. 즉, i===a[pos] & &limit==1,limit은 1이고 앞의 숫자는 a[pos],i=a[pos]는 현재 위치가 a[pos]이고 이때 다음 위치의 limit는 1이다.
그러면 우리는 dfs가 매 글자의 합법성을 매거할 수 있다.
그럼 문제 왔어요. 시간 초과할까요?이때 우리는 기억화 검색을 도입해야 하기 때문에 여러분도 왜 분명히 dfs 매거진이고 왜 d수 그룹이 있는지 이상하게 생각하지 않을 것입니다.
 
 

#include
using namespace std;
int n,m;
int d[20][2][2],a[20];

long long dfs(int pos,int sta,int limit)
{
    if(pos==0)return 1;//  ，       
    if(d[pos][sta][limit]) return d[pos][sta][limit];
    int up=(limit==1)?a[pos]:9;
    long long ans=0;
    for(int i=0;i<=up;i++)
    {
        if(i==4||(sta&&i==2))continue;
        ans+=dfs(pos-1,(i==6),limit&&(i==up));
    }
    return d[pos][sta][limit]=ans;
}

long long gao(int n)//   
{
    memset(d,0,sizeof(d));
    int cnt=0;
    while(n)
    {
        a[++cnt]=n%10;
        n/=10;
     }
    return dfs(cnt,0,1);
}

int main()
{
    while(~scanf("%d%d",&n,&m)&&n&&m)
    {
        cout<

ccsu

제목 링크
제목: 26진수 n을 드리겠습니다. a-z에서 0에서 n까지 ccsu를 포함하는 모든 개수를 구하십시오.
사고방식: 우리는 62를 본떠서 0에서 n의 모든 수를 계산한 다음ccsu를 포함하는 수를 빼면 답이다.
dp[pos][sta][limit]를 설정합니다.pos는 문자열의 하표를 대표하고sta가 1일 때 이 자리의 앞자리를 대표하는 것은'c'이며sta=2는 앞쪽이'cc'이고sta=3은 앞쪽이'ccs'임을 대표한다.limit=0은 이 자리에 제한이 없다는 것을 의미한다. 1은 제한이 있고 제한이 있으면 a[pos]이다. 그렇지 않으면'z'이다.
물론 기억어로 검색해야 한다. 그렇지 않으면 시간이 초과될 것이다.

#include
using namespace std;
const int maxn = 1e4 + 10;
 
char a[maxn];
int d[maxn][5][2],n;
 
long long mod=1e9+7;
int dfs(int pos,int sta,int limit)
{
    if(pos==n+1)return 1;
    if(d[pos][sta][limit])return d[pos][sta][limit];
    char up=(limit==1)?a[pos]:'z';
    long long ans=0;
    for(char i='a';i<=up;i++)
    {
        int tmp=0;
        if(i=='c'&&sta!=1)tmp=1;
        else if(sta==1&&i=='c')tmp=2;
        else if(sta==2&&i=='s')tmp=3;
        else if(sta==3&&i=='u')
        {
            continue;
        }
        ans=(ans+dfs(pos+1,tmp,limit&&i==up))%mod;
    }
    return d[pos][sta][limit]=ans;
}
  
int main()
{
    cin>>a+1;
    n=strlen(a+1);
    long long an=0;
    for(int i=1;i<=n;i++)
    {
        an=(an*26+(a[i]-'a'))%mod;
    }
    an+=1;
    long long tot=an-dfs(1,0,1)+mod;
    cout<

CCSU라는 문제에 대해 나는 또 새로운 해법을 발견했다. 우리는 왜 한 자릿수의 불법성을 매거한 다음에 총수로 줄여야 하는지. 우리는 한 자릿수의 합법성을 직접 매거할 수 있다. 구체적인 코드는 다음과 같다.

#include
using namespace std;
#define ll long long
char a[100004];
int n,d[10004][5][2];
const int mod=1e9+7;
int dfs(int pos,int sta,int limit)
{
    if(pos==n+1)return sta==4?1:0;
    if(d[pos][sta][limit])return d[pos][sta][limit];

    char up=limit?a[pos]:'z';
    long long ans=0;
    for(char i='a';i<=up;i++)
    {
        int tmp = 0;
        if(i == 'c' && sta != 1) tmp = 1;
        else if(i == 'c' && sta == 1) tmp = 2;
        else if(i == 's' && sta == 2) tmp = 3;
        else if(i == 'u' && sta == 3) tmp = 4;
        if(sta==4) tmp = 4;
        ans=(ans+dfs(pos+1,tmp,limit&&i==up))%mod;
    }
    return d[pos][sta][limit]=ans;
}
int main()
{
    cin>>a+1;
    n=strlen(a+1);
    long long an=dfs(1,0,1);
    cout<

 
 
마지막으로, 특히 고마워 ccsucat, 저에게 디지털 dp를 가르쳐 주시고 템플릿을 주셔서 감사합니다.