結果

問題 No.1417 100の倍数かつ正整数(2)
ユーザー LayCurseLayCurse
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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);
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0