0_0_21606035_1448.cpp: In function 'LL getCount(char*, int)':
0_0_21606035_1448.cpp:2:1941: error: expected '}' at end of input
using namespace std; typedef long long LL; const LL Mod = 998244353; const int maxFacs = 5000; LL fac[maxFacs], lenL, lenR; char L[10000], R[10000]; inline void init() {fac[0] = 1; for (LL i = 1; i < maxFacs; ++i) fac[i] = (fac[i-1] * i)%Mod; } bool vis[maxFacs]; inline void trans2LessMax(LL s[], int len) {int i, j; memset(vis, false, sizeof(vis)); for (i = 0; i < len; ++i) if (!vis[s[i]]) vis[s[i]] = true; else break; if (i == len) return; for (j = s[i]-1; j >= 0; --j) {if (!vis[j]) {vis[j] = true; s[i] = j; break; } } if (j < 0) for (--i; i >= 0; --i) {vis[s[i]] = false; for (j = s[i]-1; j >= 0; --j) {if (!vis[j]) {vis[j] = true; s[i] = j; break; } } if (j >= 0) break; } j = len - 1; for (++i; i < len; ++i) for (; j>=0; --j) if (!vis[j]) {vis[j] = true; s[i] = j; break; } } inline LL countContoNum(LL s[], int len) {LL ans = 0; LL tmp; for (int i = 0; i < len - 1; i++) {tmp = 0; for (int j = i + 1; j < len; j++) if (s[j] < s[i]) ++tmp; ans = (ans + (tmp * fac[len - i - 1])%Mod)%Mod; } return ans - fac[len - 1] + 1; } inline LL cantor(char s[], int len, LL d) {LL num[maxFacs], ansNum[maxFacs]; for (int i = 0; i < len; ++i) num[i] = s[i] - '0'; int tot = 0, p = 0; while (true) {while (p < len && num[p]==0) ++p; if (p == len) break; LL yu = 0, tmp; for (int i = p; i < len; ++i) {tmp = yu*10 + num[i]; yu = tmp % d; num[i] = tmp / d; } ansNum[tot++] = yu; } for (int i = 0; i < tot - i - 1; ++i) swap(ansNum[i], ansNum[tot - i - 1]); if (tot != d) return fac[d] - fac[d-1]; trans2LessMax(ansNum, tot); if (s[0] == 0) return 0; return countContoNum(ansNum, tot); } inline LL getCount(char s[], int len) {if ((s[0] == '0' || s[0] == '1') && s[1] == 0) return 0; if (s[0] == '2' && s[1] == 0) return 1; LL ans = 0, i; double b = s[0] - '0'; for (i = 1; i < len && i < 100; ++i) {b *= 10; b += s[i] - '0'; } b /= pow(10.0, i-1); b = len - 1 + log10(b); for (i = 2; b / log10(i) > i-1; ++i); --i; ans = (fac[i-1] - 1 + Mod)%Mod; // printf("# %lld\n", ans); ans = (ans + cantor(s, len, i))%Mod; return ans; } int main() {int T; scanf("%d", &T); init(); while (T--) {scanf("%s%s", L, R); lenL = strlen(L); lenR = strlen(R); --L[lenL-1]; for (int i = lenL-1; i >= 0; --i) if (L[i] < '0') L[i] += 10, --L[i-1]; else break; if (L[0]=='0') {--lenL; for(int i=0;i<lenL;++i)L[i]=L[i+1]; } printf("%lld\n", (getCount(R, lenR)-getCount(L, lenL)+Mod)%Mod); } return 0; }
^
|
