結果
問題 |
No.1417 100の倍数かつ正整数(2)
|
ユーザー |
![]() |
提出日時 | 2023-09-05 20:06:36 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 3,000 ms |
コード長 | 1,251 bytes |
コンパイル時間 | 4,904 ms |
コンパイル使用メモリ | 313,120 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-23 15:30:49 |
合計ジャッジ時間 | 5,999 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include<bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using mint=modint1000000007; using ll=long long; using pp=pair<ll,ll>; #define sr string #define vc vector #define fi first #define se second #define rep(i,n) for(ll i=0;i<(ll)n;i++) #define pb push_back #define all(v) v.begin(),v.end() #define pque priority_queue #define bpc(a) __builtin_popcount(a) int main(){ sr s;cin>>s; vc dp(3,vc<mint>(3,0)); int ta=0,tb=0;bool ok=true,fir=true; for(char c:s){ int x=c-'0'; vc pre(3,vc<mint>(3,0)); swap(pre,dp); if(x==0)ok=false; if(!fir){ dp[0][0]+=4; dp[1][0]+=2; dp[0][1]++; dp[2][0]+=2; } if(ok)for(int i=1;i<x;i++){ int a=ta,b=tb; if(i==2||i==6)a++; if(i==5)b++; if(i==4||i==8)a+=2; a=min(a,2); b=min(b,2); dp[a][b]++; } rep(i,3)rep(j,3){ for(int t=1;t<10;t++){ int ni=i,nj=j; if(t==2||t==6)ni++; if(t==5)nj++; if(t==4||t==8)ni+=2; ni=min(ni,2); nj=min(nj,2); dp[ni][nj]+=pre[i][j]; } } fir=false; if(x==2||x==6)ta++; if(x==5)tb++; if(x==4||x==8)ta+=2; ta=min(ta,2); tb=min(tb,2); } mint ans=dp[2][2]; if(ta==2&&tb==2&&ok)ans++; cout<<ans.val(); }