提出 #40051023

---

ソースコード 拡げる

#include <bits/stdc++.h>
 
#pragma GCC optimization ("O2")
#pragma GCC optimization ("unroll-loops")
 
using namespace std;

long long dp[17][2][17][17][2];
vector < int > lcp;
string s;
string a;
int n , m;
void reset() {
    for(int i = 0;i<17;i++){
        for(int j = 0;j<2;j++){
            for(int k = 0;k<17;k++){
                for(int l = 0;l<17;l++){
                    dp[i][j][k][l][0] = dp[i][j][k][l][1] = -1;
                }
            }
        }
    }
}

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

long long memo(int i , int small , int done , int j , int start) {
    
    if(j == m) {
        done++;
        j = lcp[j - 1];
    }
    if(i == n) {
        return done * start;
    }


    long long int &ans = dp[i][small][done][j][start];
    if(ans != -1) {
        return ans;
    }

    ans = 0;

    if(small == 0) {
            if(start == 0) {
                ans += memo(i + 1 , 1 , 0 , 0 , 0);
            }
            int val = (s[0] - '0');
            int nxj = 1;
            if(j) {
                val = s[lcp[j - 1]] - '0';
                nxj = lcp[j - 1] + 1;
            }
            for(int num = (start==0);num<(a[i] - '0');num++) {
                if(num == (s[j] - '0')) {
                    ans += memo(i + 1 , 1, done , j + 1 , 1);
                } else {
                    int nxj = j;
                    while(nxj && num != (s[nxj] - '0')) nxj = lcp[nxj - 1];
                    if(num == (s[nxj] - '0')) nxj++;
                    ans += memo(i + 1 , 1 , done , nxj , 1); 
                }
            }
            if(a[i] == s[j]) {
                ans += memo(i + 1 , 0 , done , j + 1 , 1);
            } else if(a[i] == s[nxj - 1]) {
                ans += memo(i + 1 , 0 , done , nxj , 1);
            } else {
                ans += memo(i + 1 , 0 , done , 0 , 1);
            }
    } else {
            if(start == 0) {
                ans += memo(i + 1 , 1 , done , 0 , 0);
            }
            int val = (s[0] - '0');
            int nxj = 1;
            
            for(int num = (start==0);num<10;num++) {

                if(num == (s[j] - '0')) {
                    ans += memo(i + 1 , 1, done , j + 1 , 1);
                } else {
                    int nxj = j;
                    while(nxj > 0 && num != (s[nxj] - '0')) nxj = lcp[nxj - 1];
                    if(num == (s[nxj] - '0')) nxj++;
                    ans += memo(i + 1 , 1 , done , nxj , 1); 
                }
            }
    }
    return ans;
}

void Solve() {
    
    cin >> s;
    lcp = prefix_function(s);
    long long l , r;
    cin >> l >> r;
    a = to_string(r);
    n = a.size();
    m = s.size();
    reset();
    long long ans = memo(0 , 0 , 0 , 0 , 0);
    //cout << ans << "\n" ;
    if(l > 1) {
        l--;
        a = to_string(l);
        reset();
        n = a.size();
        ans -= memo(0 , 0 , 0 , 0 , 0);
    }
    cout << ans << "\n" ;
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int test;
    cin >> test;
    for(int i = 0;i<test;i++) {
        Solve();
    }
 
    return 0;
}

提出情報

コンパイルエラー

./Main.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O2")
      | 
./Main.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
./Main.cpp: In function ‘long long int memo(int, int, int, int, int)’:
./Main.cpp:61:17: warning: variable ‘val’ set but not used [-Wunused-but-set-variable]
   61 |             int val = (s[0] - '0');
      |                 ^~~
./Main.cpp:88:17: warning: unused variable ‘val’ [-Wunused-variable]
   88 |             int val = (s[0] - '0');
      |                 ^~~
./Main.cpp:89:17: warning: unused variable ‘nxj’ [-Wunused-variable]
   89 |             int nxj = 1;
      |                 ^~~

ジャッジ結果