Educational Codeforces Round 8

D. Magic Numbers

계수 모형을 보면 dp를 쓸 줄 안다.우선 문제를 1~x 범위 내에서 요구를 충족시키는 수가 얼마나 되는지로 바꾸어 보자.그리고 디자인 상태 dp(i, j, k), i는 앞의 i자리를 고찰했고 j는 현재 m에 대한 여수를 나타냈다. k는 접두사보다 작거나 접두사(우리가 구한 것은 1~x이기 때문에 이런 방식으로 x를 초과하는 것을 피한다).상태 이동 코드.마지막으로 b와 a의 결과를 나누어 계산하고 a가 합법적인지 검사한다.

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int mod = 1e9+7;

int m,d;
int len;
char stra[2010];
char strb[2010];
int a[2010];
int b[2010];

int dp[2010][2010][2];

int solve(int *num){
    memset(dp,0,sizeof(dp));

    for(int i=1;i<=num[0];i++){
        if(i==d)continue;
        if(i<num[0]){
            dp[0][i%m][1]++;
        }else{
            dp[0][i%m][0]++;
        }
    }

    for(int i=1;i<len;i++){
        for(int j=0;j<m;j++){
            if(i&1){
                dp[i][ (j*10+d)%m ][1] += dp[i-1][j][1];
                dp[i][ (j*10+d)%m ][1] %= mod;
                if(d<num[i]){
                    dp[i][ (j*10+d)%m ][1] += dp[i-1][j][0];
                    dp[i][ (j*10+d)%m ][1] %= mod;
                }else if(d==num[i]){
                    dp[i][ (j*10+d)%m ][0] += dp[i-1][j][0];
                    dp[i][ (j*10+d)%m ][0] %= mod;
                }
            }else{
                for(int k=0;k<10;k++){
                    if(k==d)continue;
                    dp[i][ (j*10+k)%m ][1] += dp[i-1][j][1];
                    dp[i][ (j*10+k)%m ][1] %= mod;
                    if(k<num[i]){
                        dp[i][ (j*10+k)%m ][1] += dp[i-1][j][0];
                        dp[i][ (j*10+k)%m ][1] %= mod;
                    }else if(k==num[i]){
                        dp[i][ (j*10+k)%m ][0] += dp[i-1][j][0];
                        dp[i][ (j*10+k)%m ][0] %= mod;
                    }
                }
            }
        }
    }

    int ans = dp[len-1][0][0]+dp[len-1][0][1];
    ans %= mod;
    return ans;
}

bool checkA(){
    ll cur = 0;
    for(int i=0;i<len;i++){
        cur*=10;
        cur+=a[i];
        cur%=m;
        if(i&1){
            if(a[i]!=d)return 0;
        }else{
            if(a[i]==d)return 0;
        }
    }
    return cur==0;
}

int main(){
    cin>>m>>d;
    scanf("%s",stra);
    scanf("%s",strb);
    len = strlen(stra);

    for(int i=0;i<len;i++){
        a[i]=stra[i]-'0';
        b[i]=strb[i]-'0';
    }

    int l=solve(a);
    int r=solve(b);

    ll ans = (r-l + checkA() +mod)%mod;
    cout<<ans<<endl;
    return 0;
}

E. Zbazi in Zeydabad

우선 각 위치(i, j)를 왼쪽으로, 오른쪽으로, 왼쪽 아래로 몇 개의 연속적인 z가 있는지 미리 처리하고 각각 l(i, j), r(i, j),ld(i, j)로 기록한다.그리고 i+j증가(오른쪽 상-왼쪽 아래 대각선)의 순서에 따라 각 위치를 큰 z의 오른쪽 상각으로 매거하는 경우.각 위치(i, j)에서 형성할 수 있는 큰 z는 대부분이min(l(i, j),ld(i, j))이고 z의 아래의'가로'를 고찰한다. r(i, j)에 따라 오른쪽으로 충분한 줄을 BIT에 추가하여 유지보수한 다음min(l(i, j),ld(i, j)) 범위 내에서 몇 줄이 만족하는지 조회한다.

#include <bits/stdc++.h>

using namespace std;

#define ll long long

char z[3010][3010];

int r[3010][3010];
int l[3010][3010];
int ld[3010][3010];

int c[6010];

inline int lowbit(int x){
    return x&(-x);
}

void update(int x){
    while(x<=6000){
        c[x]++;
        x+=lowbit(x);
    }
}

int query(int l,int r){
    int resl=0;
    l--;
    while(l){
        resl+=c[l];
        l-=lowbit(l);
    }
    int resr=0;
    while(r){
        resr+=c[r];
        r-=lowbit(r);
    }
    return resr-resl;
}


struct node{
    int row;
    int rr;
    node(){
    }
    node(int row,int rr):row(row),rr(rr){
    }
    bool operator<(const node &other)const{
        return rr>other.rr;
    }
};


int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%s",z[i]+1);
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(z[i][j]=='z'){
                l[i][j]=l[i][j-1]+1;
            }
        }
        for(int j=m;j>=1;j--){
            if(z[i][j]=='z'){
                r[i][j]=r[i][j+1]+1;
            }
        }
    }

    ll ans = 0;
    for(int sum=2;sum<=n+m;sum++){
        memset(c,0,sizeof(c));
        int i=min(sum-1,n);
        int j=sum-i;
        vector<node> vec;
        while(j<=m && i>=1){
            if(r[i][j])vec.push_back(node(i,j+r[i][j]-1));
            if(z[i][j]=='z'){
                ld[i][j] = ld[i+1][j-1]+1;
            }
            i--;
            j++;
        }
        sort(vec.begin(),vec.end());
        //
        j=min(sum-1,m);
        i=sum-j;
        int k = 0;
        while(i<=n && j>=1){
            while(k<vec.size() && vec[k].rr>=j){
                update(vec[k].row);
                k++;
            }
            int t = min(l[i][j],ld[i][j]);
            ans+=query(i,i+t-1);
            i++;
            j--;
        }
    }
    cout<<ans<<endl;
    return 0;
}