結果
問題 | No.3136 F,B in FizzBuzzString16 |
ユーザー |
![]() |
提出日時 | 2025-05-02 21:49:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,071 bytes |
コンパイル時間 | 2,022 ms |
コンパイル使用メモリ | 200,440 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2025-05-02 21:49:38 |
合計ジャッジ時間 | 3,460 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 7 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; } #define vi vector<int> #define vl vector<ll> #define vii vector<pair<int,int>> #define vll vector<pair<ll,ll>> #define vvi vector<vector<int>> #define vvl vector<vector<ll>> #define vvii vector<vector<pair<int,int>>> #define vvll vector<vector<pair<ll,ll>>> #define vst vector<string> #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define all(x) (x).begin(),(x).end() #define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end()) #define fi first #define se second #define mp make_pair #define si(x) int(x.size()) const int mod=998244353,MAX=300005,INF=15<<26; string fi16(ll a){ if(a%15==0) return "FizzBuzz"; else if(a%3==0) return "Fizz"; else if(a%5==0) return "Buzz"; else{ string res; while(a){ if(a%16<10) res+=char('0'+(a%16)); else res+=char('A'+(a%16-10)); a/=16; } reverse(all(res)); return res; } } ll dp[17][15][17][2]; int main(){ std::ifstream in("text.txt"); std::cin.rdbuf(in.rdbuf()); cin.tie(0); ios::sync_with_stdio(false); ll L,R;cin>>L>>R; auto CNT=[&](ll n){ ll res=0; res+=n/3*4; res+=n/5*4; for(ll a=1;a<=15;a++){ ll l=(1LL<<(4*(a-1)))-1,r=(1LL<<(4*a))-1; chmin(r,n); if(l>r) break; res+=((r-r/3-r/5+r/15)-(l-l/3-l/5+l/15))*a; } return res; }; auto solve=[&](ll X){ ll l=0,r=1000000000000LL; while(r-l>1){ ll m=(l+r)/2; if(CNT(m)<=X) l=m; else r=m; } ll res=0; string Z=fi16(l+1); for(int t=0;t<X-CNT(l);t++){ if(Z[t]=='F'||Z[t]=='B') res++; } res+=l/3; res+=l/5; memset(dp,0,sizeof(dp)); vi S; l++; while(l){ S.pb(l%16); l/=16; } while(si(S)<15) S.pb(0); reverse(all(S)); //for(int a:S) cout<<a<<" "; //cout<<endl; dp[0][0][0][0]=1; for(int i=0;i<15;i++){ for(int j=0;j<15;j++){ for(int k=0;k<15;k++){ for(int f=0;f<2;f++){ if(dp[i][j][k][f]==0) continue; for(int x=0;x<16;x++){ if(f==0&&x>S[i]) continue; dp[i+1][(j*16+x)%15][k+(x==11)+(x==15)][f||(x<S[i])]+=dp[i][j][k][f]; } } } } } for(int j=0;j<15;j++){ for(int k=0;k<15;k++){ if(j%3!=0&&j%5!=0) res+=dp[15][j][k][1]*k; } } return res; }; cout<<solve(R)-solve(L-1)<<"\n"; }