結果
問題 | No.3136 F,B in FizzBuzzString16 |
ユーザー |
|
提出日時 | 2025-05-02 22:06:45 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,545 bytes |
コンパイル時間 | 6,229 ms |
コンパイル使用メモリ | 332,944 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2025-05-02 22:06:55 |
合計ジャッジ時間 | 6,426 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 7 |
other | AC * 32 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; typedef long long int ll; typedef long double ld; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<vvl> vvvl; typedef vector<vvvl> vvvvl; typedef vector<bool> vb; typedef vector<vb> vvb; typedef vector<vvb> vvvb; typedef vector<vvvb> vvvvb; typedef pair<ll,ll> pl; typedef pair<ll,pl> ppl; typedef pair<ll,ppl> pppl; typedef pair<ll,pppl> pppppl; #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--) #define all(a) begin(a),end(a) #define sz(a) (int)(a).size() #define F first #define S second #define bs(A,x) binary_search(all(A),x) #define lb(A,x) (ll)(lower_bound(all(A),x)-A.begin()) #define ub(A,x) (ll)(upper_bound(all(A),x)-A.begin()) #define cou(A,x) (ll)upper_bound(all(A),x)-lower_bound(all(A),x)) template<typename T>using min_priority_queue=priority_queue<T,vector<T>,greater<T>>; template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;} template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;} //* using mint=modint998244353; const ll mod=998244353; //*/ /* using mint=modint1000000007; const ll mod=1000000007; //*/ //using mint=modint; //* typedef vector<mint> vm; typedef vector<vm> vvm; typedef vector<vvm> vvvm; typedef vector<vvvm> vvvvm; ostream&operator<<(ostream&os,mint a){os<<a.val();return os;} istream&operator>>(istream&is,mint&a){int x;is>>x;a=mint(x);return is;} //*/ template<typename T1,typename T2>ostream&operator<<(ostream&os,pair<T1,T2>p){os<<p.F<<" "<<p.S;return os;} template<typename T1,typename T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.F>>p.S;return is;} template<typename T>ostream&operator<<(ostream&os,vector<T>v){rep(i,0,sz(v))os<<v[i]<<(i+1!=sz(v)?" ":"");return os;} template<typename T>istream&operator>>(istream&is,vector<T>&v){for(T&in:v)is>>in;return is;} string to_hex_string(int64_t i){ stringstream s; s<<uppercase<<hex<<i; return s.str(); } 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); } ll length(ll N){ //1,2,...,Nの長さ ll ans=0; for(ll l=1,d=1;l<=N;l*=16,d++){ ll r=min(N,16*l-1); ll f=r/3-(l-1)/3; ll b=r/5-(l-1)/5; ll fb=r/15-(l-1)/15; ans+=d*(r-l+1-f-b+fb); ans+=f*4+b*4; } return ans; } ll g(ll N){ //[1,N]までのfbの和 ll ans=N/3+N/5; vl T(12); for(ll n=N,i=0;i<12;i++,n/=16)T[i]=n%16; //mod15で0,3,5,6,9,10,12でない数だけをみる,FBは何個現れる? vvl dp(12,vl(15)),ep(12,vl(15)); vvl _dp(12,vl(15)),_ep(12,vl(15)); dp[11][0]=1; rrep(i,0,11)rep(j,0,15)rep(k,0,16){ ll d=(k==11||k==15); ll l=(16*j+k)%15; //ep->ep ep[i][l]+=ep[i+1][j]; _ep[i][l]+=_ep[i+1][j]+d*ep[i+1][j]; if(T[i]>k){ //dp->ep ep[i][l]+=dp[i+1][j]; _ep[i][l]+=_dp[i+1][j]+d*dp[i+1][j]; } if(T[i]==k){ //dp->dp dp[i][l]+=dp[i+1][j]; _dp[i][l]+=_dp[i+1][j]+d*dp[i+1][j]; } } rep(i,0,15)if(i%3&&i%5)ans+=_dp[0][i]+_ep[0][i]; return ans; } ll f(ll N){ //N文字目までのfbの和 ll l=0,r=N+10; while(r-l>1){ ll m=(l+r)/2; if(length(m)>N)r=m; else l=m; } ll q=length(l); string s=FizzBuzz16(l+1); ll ans=g(l); rep(i,0,N-q)if(s[i]=='F'||s[i]=='B')ans++; return ans; } int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); ll X,Y;cin>>X>>Y; cout<<f(Y)-f(X-1)<<endl; return 0; }