結果

問題 No.3136 F,B in FizzBuzzString16
ユーザー 沙耶花
提出日時 2025-05-02 22:18:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 11 ms / 2,000 ms
コード長 2,279 bytes
コンパイル時間 4,732 ms
コンパイル使用メモリ 262,204 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-05-02 22:18:44
合計ジャッジ時間 5,771 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 7
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000005
#define Inf64 4000000000000000001LL
long long count(long long n,int b){
	vector<int> t;
	while(n!=0){
		t.push_back(n%16);
		n /= 16;
	}
	reverse(t.begin(),t.end());
	vector dp(15,vector(2,vector(2,vector<long long>(2))));
	dp[0][0][0][0] = 1;
	rep(i,t.size()){
		vector ndp(15,vector(2,vector(2,vector<long long>(2))));
		rep(j,15){
			rep(k,2){
				rep(l,2){
					rep(ll,2){
						rep(m,16){
							int nj = (j * 16 + m)%15;
							int nk = k;
							if(k==0 && t[i] < m)continue;
							if(t[i] > m)nk = 1;
							int nl = l;
							int nll = ll;
							if(m != 0)nll = 1;
							ndp[nj][nk][nl][nll] += dp[j][k][l][ll];
							if(nl==0 && (m==b || b==-1) && nll){
								ndp[nj][nk][1][nll] += dp[j][k][l][ll];
							}
						}
					}
				}
			}
		}
		swap(dp,ndp);
	}
	long long res = 0;
	rep(i,15){
		if(i%3==0 || i%5==0)continue;
		rep(j,2){
			res += dp[i][j][1][0] + dp[i][j][1][1];
		}
	}
	return res;
}
long long fizbuzzs(long long n){
	return n / 15;
}
long long buzzs(long long n){
	return n/5 - n/15;
}
long long fizzs(long long n){
	return n/3 - n/15;
}
std::string to_hex_string(int64_t i) {
    std::stringstream s;
    s << std::uppercase << std::hex << i;
    return s.str();
}

std::string FizzBuzz16(int64_t i) {
    if (i % 15 == 0) {
        return "FizzBuzz";
    } else if (i % 3 == 0) {
        return "Fizz";
    } else if (i % 5 == 0) {
        return "Buzz";
    } else {
        return to_hex_string(i);
    }
}
long long len(long long n){
	return count(n,-1) + fizbuzzs(n)*8 + fizzs(n)*4 + buzzs(n)*4;
}
long long get(long long n){
	if(n<=0)return 0;
	long long ok = 0,ng= n+1;
	while(ng-ok>1){
		long long mid = (ok+ng)/2;
		if(len(mid) >n)ng= mid;
		else ok = mid;
	}
	long long res = 0;
	res += fizbuzzs(ok) * 2;
	res += fizzs(ok);
	res += buzzs(ok);
	res += count(ok,11);
	res += count(ok,15);
	n -= len(ok);
	string ress = FizzBuzz16(ok+1);
	rep(i,n){
		if(ress[i]=='B' || ress[i]=='F')res++;
	}
	return res;
}

int main(){
	
	long long X,Y;
	cin>>X>>Y;
	//cout<<count(Y,-1)<<endl;
	cout<<get(Y) - get(X-1)<<endl;
	return 0;
}
0