結果
問題 | 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();}