結果

問題 No.260 世界のなんとか3
ユーザー 👑 CleyLCleyL
提出日時 2023-10-24 11:33:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 36 ms / 2,000 ms
コード長 5,001 bytes
コンパイル時間 1,259 ms
コンパイル使用メモリ 124,284 KB
実行使用メモリ 7,572 KB
最終ジャッジ日時 2024-09-23 03:53:05
合計ジャッジ時間 2,661 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,328 KB
testcase_01 AC 4 ms
7,440 KB
testcase_02 AC 4 ms
7,204 KB
testcase_03 AC 30 ms
7,268 KB
testcase_04 AC 30 ms
7,328 KB
testcase_05 AC 8 ms
7,328 KB
testcase_06 AC 7 ms
7,404 KB
testcase_07 AC 22 ms
7,396 KB
testcase_08 AC 16 ms
7,368 KB
testcase_09 AC 10 ms
7,252 KB
testcase_10 AC 24 ms
7,232 KB
testcase_11 AC 23 ms
7,304 KB
testcase_12 AC 15 ms
7,424 KB
testcase_13 AC 7 ms
7,204 KB
testcase_14 AC 20 ms
7,264 KB
testcase_15 AC 9 ms
7,296 KB
testcase_16 AC 19 ms
7,572 KB
testcase_17 AC 15 ms
7,256 KB
testcase_18 AC 15 ms
7,380 KB
testcase_19 AC 19 ms
7,436 KB
testcase_20 AC 14 ms
7,388 KB
testcase_21 AC 14 ms
7,424 KB
testcase_22 AC 21 ms
7,292 KB
testcase_23 AC 5 ms
7,296 KB
testcase_24 AC 17 ms
7,424 KB
testcase_25 AC 20 ms
7,236 KB
testcase_26 AC 14 ms
7,420 KB
testcase_27 AC 3 ms
7,192 KB
testcase_28 AC 24 ms
7,296 KB
testcase_29 AC 36 ms
7,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

//yukicoder@cpp17
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <climits>
#include <cassert>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <bitset>
#include <complex>
#include <utility>
#include <numeric>
#include <functional>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
const ll MOD = 998244353;
const ll MODx = 1000000007;
const int INF = (1<<30)-1;
const ll LINF = (1LL<<62LL)-1;
const double EPS = (1e-10);
P ar4[4] = {{0,1},{0,-1},{1,0},{-1,0}};
P ar8[8] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); }
/*
cout << fixed << setprecision(n) << //n
min(max)_element(iter,iter)()
count(iter,iter,int)intiteriter
*/
/*
function corner below
*/
/*
Function corner above
*/
/* comment outed because can cause bugs
__attribute__((constructor))
void initial() {
cin.tie(0);
ios::sync_with_stdio(false);
}
*/
template <int mod>
struct ModInt{
int n;
ModInt():n(0){}
ModInt(long long n_):n(n_ >= 0 ? n_%mod : mod - ((-n_)%mod) ){}
ModInt(int n_):n(n_ >= 0 ? n_%mod : mod - ((-n_)%mod) ){}
ModInt &operator+=(const ModInt &p){
if((n+=p.n) >= mod)n-=mod;
return *this;
}
ModInt &operator-=(const ModInt &p){
n+=mod-p.n;
if(n >= mod)n-=mod;
return *this;
}
ModInt &operator*=(const ModInt &p){
n = (int) ((1LL*n*p.n)%mod);
return *this;
}
ModInt &operator/=(const ModInt &p){
*this *= p.inverse();
return *this;
}
ModInt operator-() const {return ModInt(-n);}
ModInt operator+(const ModInt &p) const {return ModInt(*this) += p;}
ModInt operator-(const ModInt &p) const {return ModInt(*this) -= p;}
ModInt operator*(const ModInt &p) const {return ModInt(*this) *= p;}
ModInt operator/(const ModInt &p) const {return ModInt(*this) /= p;}
bool operator==(const ModInt &p) const {return n==p.n;}
bool operator<(const ModInt &p) const {return n<p.n;}
bool operator>(const ModInt &p) const {return n>p.n;}
bool operator>=(const ModInt &p) const {return n>=p.n;}
bool operator<=(const ModInt &p) const {return n<=p.n;}
bool operator!=(const ModInt &p) const {return n!=p.n;}
ModInt inverse() const {
int a = n,b = mod,u = 1,v = 0;
while(b){
int t = a/b;
a -= t*b; swap(a,b);
u -= t*v; swap(u,v);
}
return ModInt(u);
}
ModInt pow(int64_t z) const {
ModInt ret(1),mul(n);
while(z > 0){
if(z & 1) ret *= mul;
mul *= mul;
z >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const ModInt &p){
return os << p.n;
}
friend istream &operator>>(istream &is, ModInt &a){
int64_t t;
is >> t;
a = ModInt<mod> ((long long)t);
return (is);
}
};
using mint = ModInt<MODx>;
bool isX(string s){
int k = 0;
bool ist = false;
for(int i = 0; s.size() > i; i++){
if(s[i] == '3')ist=true;
k = (k*10+s[i]-'0')%24;
}
return (ist && k%8 != 0) || (k%3 == 0 && k%8 != 0);
}
mint dp[10010][25][2][2];
mint f(string x){
for(int i = 0; x.size() >= i; i++){
for(int j = 0; 24 > j; j++)dp[i][j][0][0] = dp[i][j][0][1] = dp[i][j][1][0] = dp[i][j][1][1] = 0;
}
dp[0][0][0][1] = 1;
for(int i = 0; x.size() > i; i++){
for(int j = 0; 24 > j; j++){
//isEqual
if(x[i] != '3'){
dp[i+1][(j*10+x[i]-'0')%24][0][1] += dp[i][j][0][1];
dp[i+1][(j*10+x[i]-'0')%24][1][1] += dp[i][j][1][1];
}else{
dp[i+1][(j*10+x[i]-'0')%24][1][1] += dp[i][j][0][1] + dp[i][j][1][1];
}
//lower than equal
for(int k = 0; x[i]-'0' > k; k++){
if(k != 3){
dp[i+1][(j*10+k)%24][0][0] += dp[i][j][0][1];
dp[i+1][(j*10+k)%24][1][0] += dp[i][j][1][1];
}else{
dp[i+1][(j*10+k)%24][1][0] += dp[i][j][0][1] + dp[i][j][1][1];
}
}
//isNotEqual
for(int k = 0; 10 > k; k++){
if(k != 3){
dp[i+1][(j*10+k)%24][0][0] += dp[i][j][0][0];
dp[i+1][(j*10+k)%24][1][0] += dp[i][j][1][0];
}else{
dp[i+1][(j*10+k)%24][1][0] += dp[i][j][0][0] + dp[i][j][1][0];
}
}
}
}
mint res = 0;
for(int i = 0; 24 > i; i++){
if(i%8 == 0)continue;
if(i%3 == 0)res += dp[x.size()][i][0][0] + dp[x.size()][i][0][1] + dp[x.size()][i][1][0] + dp[x.size()][i][1][1];
else res += dp[x.size()][i][1][0] + dp[x.size()][i][1][1];
}
return res;
}
int main(){
string a,b;cin>>a>>b;
cout << f(b)-f(a)+isX(a) << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0