結果
| 問題 | No.189 SUPER HAPPY DAY |
| ユーザー |
 bluebery1001
|
| 提出日時 | 2023-09-18 17:59:34 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 23 ms / 5,000 ms |
| コード長 | 7,642 bytes |
| コンパイル時間 | 7,270 ms |
| コンパイル使用メモリ | 336,748 KB |
| 実行使用メモリ | 11,304 KB |
| 最終ジャッジ日時 | 2023-09-18 17:59:58 |
| 合計ジャッジ時間 | 8,420 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,664 KB |
| testcase_01 | AC | 2 ms
5,740 KB |
| testcase_02 | AC | 2 ms
5,664 KB |
| testcase_03 | AC | 2 ms
5,548 KB |
| testcase_04 | AC | 2 ms
5,576 KB |
| testcase_05 | AC | 2 ms
5,540 KB |
| testcase_06 | AC | 2 ms
5,652 KB |
| testcase_07 | AC | 2 ms
5,504 KB |
| testcase_08 | AC | 2 ms
5,500 KB |
| testcase_09 | AC | 2 ms
5,464 KB |
| testcase_10 | AC | 2 ms
5,716 KB |
| testcase_11 | AC | 2 ms
5,452 KB |
| testcase_12 | AC | 2 ms
5,612 KB |
| testcase_13 | AC | 9 ms
7,504 KB |
| testcase_14 | AC | 11 ms
8,220 KB |
| testcase_15 | AC | 11 ms
8,008 KB |
| testcase_16 | AC | 13 ms
8,588 KB |
| testcase_17 | AC | 13 ms
8,688 KB |
| testcase_18 | AC | 11 ms
7,940 KB |
| testcase_19 | AC | 14 ms
9,264 KB |
| testcase_20 | AC | 6 ms
6,480 KB |
| testcase_21 | AC | 6 ms
6,704 KB |
| testcase_22 | AC | 3 ms
5,612 KB |
| testcase_23 | AC | 13 ms
8,512 KB |
| testcase_24 | AC | 12 ms
8,196 KB |
| testcase_25 | AC | 23 ms
11,304 KB |
ソースコード
using namespace std;
#include<bits/stdc++.h>
void _main();int main(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(30);_main();return 0;}
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
typedef long long ll;typedef long double ld;
template<class ll>inline bool chmax(ll&a,ll b){if(a<b){a=b;return 1;}return 0;}
template<class ll>inline bool chmin(ll& a,ll b){if(a>b){a=b;return 1;}return 0;}
#define rep1(a) for(int i = 0; i < (a); i++)
#define rep2(i, a) for(int i = 0; i < (a); i++)
#define rep3(i, a, b) for(int i = (a); i < (b); i++)
#define rep4(i, a, b, c) for(int i = (a); i < (b); i += (c))
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define ALL(x) std::begin(x),std::end(x)
#define rALL(x) std::rbegin(x),std::rend(x)
#define INF ((1LL<<62)-(1LL<<31))
#define bit(x,i) (((x)>>(i))&1)
#define fi first
#define se second
#define pb push_back
#define Endl endl
#define spa " "
#define YesNo(x) cout<<(x?"Yes":"No")<<endl;
#include <atcoder/all>
using namespace atcoder;
//コンパイル時の引数にBLUEBERRYを渡すとdeb関数が使える
#ifdef BLUEBERRY
#define deb print
#else
#define deb
#endif
//可変長引数で入力を受け取りつつ変数を宣言
inline void scan(){}
template<class Head,class... Tail>
inline void scan(Head&head,Tail&... tail){std::cin>>head;scan(tail...);}
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)
//vectorのcin
template<typename T>
std::istream &operator>>(std::istream&is,std::vector<T>&v){for(T &in:v){is>>in;}return is;}
//vectorのcout
template<typename T>
std::ostream &operator<<(std::ostream&os,const std::vector<T>&v){for(auto it=std::begin(v);it!=std::end(v);){os<<*it<<((++it)!=std::end(v)?" ":"");}return os;}
//x,y,x,yを渡すとldで距離を返す
long double my_distance(long double xi,long double yi,long double xj,long double yj){return sqrt(abs((xi-xj)*(xi-xj))+abs((yi-yj)*(yi-yj)));}
//可変長引数のprint関数
void print(){cout << '\n';}
template<class T, class... Ts>
void print(const T& a, const Ts&... b){cout << a;(cout << ... << (cout << ' ', b));cout << '\n';}
//可変長引数のmin
template<class... T>
constexpr auto min(T... a){return min(initializer_list<common_type_t<T...>>{a...});}
//可変長引数のmax
template<class... T>
constexpr auto max(T... a){return max(initializer_list<common_type_t<T...>>{a...});}
//Union-Find from https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/vi((b%2==0?b-1:b)+2-(a%2==0?a+1:a))/2er/union-find
class UnionFind{public:UnionFind()=default;explicit UnionFind(size_t n):m_parentsOrSize(n, -1){}int find(int i){if(m_parentsOrSize[i]<0){return i;}return(m_parentsOrSize[i]=find(m_parentsOrSize[i]));}void merge(int a,int b){a=find(a);b=find(b);if(a!=b){if(-m_parentsOrSize[a]<-m_parentsOrSize[b]){std::swap(a,b);}m_parentsOrSize[a]+=m_parentsOrSize[b];m_parentsOrSize[b]=a;}}bool connected(int a,int b){return (find(a)==find(b));}int size(int i){return -m_parentsOrSize[find(i)];}private:std::vector<int>m_parentsOrSize;};
//こめんとを付け外ししてMODを切り替える
//ll MOD = INF;
//ll MOD = 1000000007;
ll MOD = 998244353;
//回文判定
bool iskaibun(string s){ll k = s.size();rep(i,0,k/2){if(s[i]!=s[k-1-i]){return false;}}return true;}
//二部グラフ判定 重みなしグラフを引数に取り、boolを返す
bool isbipartite_graph(vector<vector<ll>>&g){ll v = g.size();vector<ll>col(v,-1);vector<bool>used(v,false);bool ret = true;rep(i,v){if(used[i])continue;col[i]=0;[DFS([&](auto&&f,ll pos,ll pr)->void{if(used[pos])return;used[pos]=true;for(auto to:g[pos]){if(to==pr)continue;if(used[to]&&col[pos]==col[to]){ret = false;return;}if(used[to])continue;col[to]=col[pos]^1;f(f,to,pos);}}),&i]{DFS(DFS,i,-1);}();}return ret;}
//a~bの和 a<b
ll ran(ll a,ll b){return ((a+b)*(b-a+1))/2;}
//Pythonにあるreplaceみたいなもの 森久保さん作
string replace(const string&moto,const string &from, const string&too) { int from_len = from.size(); string tmp = from + moto; int tmp_len = tmp.size(); vector<int> za = z_algorithm(tmp); string ret = ""; for (int i = from_len; i < tmp_len;) { if (za[i] >= from_len) { ret += too; i += from_len; } else { ret += tmp[i]; i++; } } return ret;}
//座圧する
ll zaatu(vector<ll>&A){ map<ll,ll>m; for(auto&&x:A)m[x]=0; ll ret = 0; for(auto&&[key,val]:m)val=ret++; for(auto&&x:A)x=m[x]; return ret;}
//約数列挙 引数に取った整数の約数のvectorを返す
vector<ll>enumdiv(ll n){ vector<ll>s; for(ll i = 1;i*i<=n;i++){ if(n%i==0){s.push_back(i);if(i*i!=n)s.push_back(n/i);} } return s;}
//トポロジカルソート グラフ、入次数カウント、頂点数を引数で渡すと、トポロジカルソートされた頂点列を返す
vector<ll> topo_sort(vector<vector<ll>>&G,vector<ll>&nyu_cnt,ll v){ vector<ll>ret; priority_queue<ll,vector<ll>,greater<ll>>pq; rep(i,0,v){ if(nyu_cnt[i]==0)pq.push(i); } while(!pq.empty()){ ll pos = pq.top();pq.pop(); for(ll i:G[pos]){ nyu_cnt[i]--; if(nyu_cnt[i]==0)pq.push(i); } ret.push_back(pos); } return ret;}
//素因数分解 pair<素数、指数>のvectorを返す
vector<pair<ll,ll>> soinsu_bunkai(ll x){ vector<pair<ll,ll>>ret; rep(i,2,sqrt(x)+1){ if(x%i==0){ ll cnt{}; while(x%i==0){ x/=i; cnt++; } ret.push_back({i,cnt}); } } if(x!=1)ret.push_back({x,1}); return ret;}
//二項係数MOD MODは上の方で設定、MAXまでのnCrをCOM(n,r)でとれる
const int MAX = 500000;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit(){ fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; }}
long long COM(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; if (k == 0)return 1; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}
//エラトステネスの篩 isprimeには素数かどうかが入っている
vector<bool> isprime;vector<int> Era(int n) { isprime.resize(n, true); vector<int> res; isprime[0] = false; isprime[1] = false; for (int i = 2; i < n; ++i) isprime[i] = true; for (int i = 2; i < n; ++i) { if (isprime[i]) { res.push_back(i); for (int j = i*2; j < n; j += i) isprime[j] = false; } } return res;}
using mint = modint1000000007;
ll dpm[300][2][2000],dpd[300][2][2000];
void _main(){
STR(n,m);
dpm[0][0][0]=1;
ll l = n.length();
rep(i,l){
const int D = n[i]-'0';
rep(j,2){
rep(k,2000){
if(dpm[i][j][k]==0)continue;
rep(d,j?10:D+1){
(dpm[i+1][j||(d<D)][k+d]+=dpm[i][j][k])%=1000000009;
}
}
}
}
ll ml = m.length();
dpd[0][0][0]=1;
rep(i,ml){
const int D = m[i]-'0';
rep(j,2){
rep(k,2000){
if(dpd[i][j][k]==0)continue;
rep(d,j?10:D+1){
(dpd[i+1][j||(d<D)][k+d]+=dpd[i][j][k])%=1000000009;
}
}
}
}
ll ans{};
rep(i,1,2000){rep(j,2)rep(k,2)(ans+=dpm[l][j][i]*dpd[ml][k][i])%=1000000009;}
print(ans);
}