結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
![]() |
提出日時 | 2021-03-05 21:30:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 32 ms / 3,000 ms |
コード長 | 9,226 bytes |
コンパイル時間 | 3,619 ms |
コンパイル使用メモリ | 217,660 KB |
最終ジャッジ日時 | 2025-01-19 10:39:14 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;#define MD (1000000007U)template<class S, class T> inline S min_L(S a,T b){return a<=b?a:b;}struct Modint{unsigned val;Modint(){val=0;}Modint(int a){val = ord(a);}Modint(unsigned a){val = ord(a);}Modint(long long a){val = ord(a);}Modint(unsigned long long a){val = ord(a);}inline unsigned ord(unsigned a){return a%MD;}inline unsigned ord(int a){a %= (int)MD;if(a < 0){a += MD;}return a;}inline unsigned ord(unsigned long long a){return a%MD;}inline unsigned ord(long long a){a %= (int)MD;if(a < 0){a += MD;}return a;}inline unsigned get(){return val;}inline Modint &operator++(){val++;if(val >= MD){val -= MD;}return *this;}inline Modint &operator--(){if(val == 0){val = MD - 1;}else{--val;}return *this;}inline Modint operator++(int a){Modint res(*this);val++;if(val >= MD){val -= MD;}return res;}inline Modint operator--(int a){Modint res(*this);if(val == 0){val = MD - 1;}else{--val;}return res;}inline Modint &operator+=(Modint a){val += a.val;if(val >= MD){val -= MD;}return *this;}inline Modint &operator-=(Modint a){if(val < a.val){val = val + MD - a.val;}else{val -= a.val;}return *this;}inline Modint &operator*=(Modint a){val = ((unsigned long long)val*a.val)%MD;return *this;}inline Modint &operator/=(Modint a){return *this *= a.inverse();}inline Modint operator+(Modint a){return Modint(*this)+=a;}inline Modint operator-(Modint a){return Modint(*this)-=a;}inline Modint operator*(Modint a){return Modint(*this)*=a;}inline Modint operator/(Modint a){return Modint(*this)/=a;}inline Modint operator+(int a){return Modint(*this)+=Modint(a);}inline Modint operator-(int a){return Modint(*this)-=Modint(a);}inline Modint operator*(int a){return Modint(*this)*=Modint(a);}inline Modint operator/(int a){return Modint(*this)/=Modint(a);}inline Modint operator+(long long a){return Modint(*this)+=Modint(a);}inline Modint operator-(long long a){return Modint(*this)-=Modint(a);}inline Modint operator*(long long a){return Modint(*this)*=Modint(a);}inline Modint operator/(long long a){return Modint(*this)/=Modint(a);}inline Modint operator-(void){Modint res;if(val){res.val=MD-val;}else{res.val=0;}return res;}inline operator bool(void){return val!=0;}inline operator int(void){return get();}inline operator long long(void){return get();}inline Modint inverse(){int a = val;int b = MD;int u = 1;int v = 0;int t;Modint res;while(b){t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}if(u < 0){u += MD;}res.val = u;return res;}inline Modint pw(unsigned long long b){Modint a(*this);Modint res;res.val = 1;while(b){if(b&1){res *= a;}b >>= 1;a *= a;}return res;}inline bool operator==(int a){return ord(a)==val;}inline bool operator!=(int a){return ord(a)!=val;}};inline Modint operator+(int a, Modint b){return Modint(a)+=b;}inline Modint operator-(int a, Modint b){return Modint(a)-=b;}inline Modint operator*(int a, Modint b){return Modint(a)*=b;}inline Modint operator/(int a, Modint b){return Modint(a)/=b;}inline Modint operator+(long long a, Modint b){return Modint(a)+=b;}inline Modint operator-(long long a, Modint b){return Modint(a)-=b;}inline Modint operator*(long long a, Modint b){return Modint(a)*=b;}inline Modint operator/(long long a, Modint b){return Modint(a)/=b;}inline int my_getchar_unlocked(){static char buf[1048576];static int s = 1048576;static int e = 1048576;if(s == e && e == 1048576){e = fread_unlocked(buf, 1, 1048576, stdin);s = 0;}if(s == e){return EOF;}return buf[s++];}inline void rd(char &c){int i;for(;;){i = my_getchar_unlocked();if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){break;}}c = i;}inline int rd(char c[]){int i;int sz = 0;for(;;){i = my_getchar_unlocked();if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){break;}}c[sz++] = i;for(;;){i = my_getchar_unlocked();if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){break;}c[sz++] = i;}c[sz]='\0';return sz;}struct MY_WRITER{char buf[1048576];int s;int e;MY_WRITER(){s = 0;e = 1048576;}~MY_WRITER(){if(s){fwrite_unlocked(buf, 1, s, stdout);}}};MY_WRITER MY_WRITER_VAR;void my_putchar_unlocked(int a){if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);MY_WRITER_VAR.s = 0;}MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;}inline void wt_L(char a){my_putchar_unlocked(a);}inline void wt_L(int x){int s=0;int m=0;char f[10];if(x<0){m=1;x=-x;}while(x){f[s++]=x%10;x/=10;}if(!s){f[s++]=0;}if(m){my_putchar_unlocked('-');}while(s--){my_putchar_unlocked(f[s]+'0');}}inline void wt_L(Modint x){int i;i = (int)x;wt_L(i);}char A[100000+2];int N;Modint dp[2][2][2][3][3];Modint nxt[2][2][2][3][3];int main(){int d, i, x;int nz;int nx;int ny;int ni;int nj;Modint res = 0;N = rd(A);for(i=(0);i<(N);i++){A[i] -= '0';}dp[0][0][0][0][0] = 1;for(d=(0);d<(N);d++){int z;for(z=(0);z<(2);z++){int x;for(x=(0);x<(2);x++){int y;for(y=(0);y<(2);y++){for(i=(0);i<(3);i++){int j;for(j=(0);j<(3);j++){nxt[z][x][y][i][j] = 0;}}}}}for(z=(0);z<(2);z++){int x;for(x=(0);x<(2);x++){int y;for(y=(0);y<(2);y++){for(i=(0);i<(3);i++){int j;for(j=(0);j<(3);j++){int k;for(k=(0);k<(10);k++){auto Q5rsz4fz = ((z));auto GgkpftXM = (( x));auto gEg5UqEA = (( y));auto qSsg05KM = (( i));auto Hjfu7Vx7 = (( j));nz=Q5rsz4fz;nx=GgkpftXM;ny=gEg5UqEA;ni=qSsg05KM;nj=Hjfu7Vx7;if(z == 1 && k == 0){continue;}if(k){nz = 1;}if(ny == 0 && k > A[d]){continue;}if(k < A[d]){ny = 1;}if(k && k%2==0){ni =min_L(2, ni+1);}if(k && k%4==0){ni =min_L(2, ni+1);}if(k && k%5==0){nj =min_L(2, nj+1);}nxt[nz][nx][ny][ni][nj] += dp[z][x][y][i][j];}}}}}}for(z=(0);z<(2);z++){int x;for(x=(0);x<(2);x++){int y;for(y=(0);y<(2);y++){for(i=(0);i<(3);i++){int j;for(j=(0);j<(3);j++){dp[z][x][y][i][j] = nxt[z][x][y][i][j];}}}}}}for(x=(0);x<(2);x++){int y;for(y=(0);y<(2);y++){res += dp[1][x][y][2][2];}}wt_L(res);wt_L('\n');return 0;}// cLay version 20210227-1// --- original code ---// char A[1d5+2]; int N;// Modint dp[2][2][2][3][3], nxt[2][2][2][3][3];//// {// int nz, nx, ny, ni, nj;// Modint res = 0;// rd(A@N);// rep(i,N) A[i] -= '0';// dp[0][0][0][0][0] = 1;// rep(d,N){// rep(z,2) rep(x,2) rep(y,2) rep(i,3) rep(j,3) nxt[z][x][y][i][j] = 0;// rep(z,2) rep(x,2) rep(y,2) rep(i,3) rep(j,3) rep(k,10){// (nz, nx, ny, ni, nj) = (z, x, y, i, j);// if(z == 1 && k == 0) continue;// if(k) nz = 1;// // if(nx == 0 && k < A[d]) continue;// // if(k > A[d]) nx = 1;// if(ny == 0 && k > A[d]) continue;// if(k < A[d]) ny = 1;// if(k && k%2==0) ni = min(2, ni+1);// if(k && k%4==0) ni = min(2, ni+1);// if(k && k%5==0) nj = min(2, nj+1);// nxt[nz][nx][ny][ni][nj] += dp[z][x][y][i][j];// }// rep(z,2) rep(x,2) rep(y,2) rep(i,3) rep(j,3) dp[z][x][y][i][j] = nxt[z][x][y][i][j];// // rep(z,2) rep(x,2) rep(y,2) rep(i,3) rep(j,3) if(dp[z][x][y][i][j]) wt(d,":",z,x,y,i,j,":",dp[z][x][y][i][j]);// }// rep(x,2) rep(y,2) res += dp[1][x][y][2][2];// wt(res);// }