Submission #5630625
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll, int> plli;
typedef pair<int, pii> pipii;
typedef vector<vector<int> > mati;
typedef vector<vector<double> > matd;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef vector<pll> vpll;
#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
inline void IN(void){
return;
}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
cin >> first;
IN(rest...);
return;
}
inline void OUT(void){
cout << "\n";
return;
}
template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
cout << first << " ";
OUT(rest...);
return;
}
template <typename T>
void vec_print(vector<T> VEC){
REP(i, VEC.size()){
cout << VEC[i] << " ";
}
cout << "\n";
};
template <typename T>
void mat_print(vector<vector<T> > MAT){
REP(i, MAT.size()){
REP(j, MAT[i].size()){
cout << MAT[i][j] << " ";
}
cout << "\n";
}
};
template <typename CLASS1, typename CLASS2>
class HOGE{
public:
CLASS1 key;
CLASS2 value;
HOGE(void){
return;
};
HOGE(CLASS1 key, CLASS2 value){
this->key = key;
this->value = value;
};
~HOGE(void){
return;
};
void print(void){
cout << "key : " << key << ", value : " << value << "\n";
return;
};
bool operator==(const HOGE &obj){
return (this->value == obj.value);
};
bool operator<(const HOGE &obj){
return (this->value < obj.value);
};
bool operator>(const HOGE &obj){
return (this->value > obj.value);
};
};
template <typename CLASS1, typename CLASS2>
bool operator==(const HOGE<CLASS1, CLASS2> &hoge1, const HOGE<CLASS1, CLASS2> &hoge2){
return hoge1.value == hoge2.value;
};
template <typename CLASS1, typename CLASS2>
bool operator<(const HOGE<CLASS1, CLASS2> &hoge1, const HOGE<CLASS1, CLASS2> &hoge2){
return hoge1.value < hoge2.value;
};
template <typename CLASS1, typename CLASS2>
bool operator>(const HOGE<CLASS1, CLASS2> &hoge1, const HOGE<CLASS1, CLASS2> &hoge2){
return hoge1.value > hoge2.value;
};
constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
//constexpr ll MOD = (ll)((1E+9)+7);
constexpr ll MOD = (ll)(1000000007);
int main(){
cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)
ll D;
string N;
IN(D,N);
vll digits;
REP(i,N.size()){
digits.pb(N[i]-'0');
}
vll dp1(D, 0);
vll dp2(D, 0);
dp1[0] = 1;
REP(i,digits.size()){
vll dp1_copy = dp1;
vll dp2_copy = dp2;
dp1.assign(D, 0);
dp2.assign(D, 0);
REP(d,D){
dp1[(d+digits[i])%D]+=dp1_copy[d];
dp1[(d+digits[i])%D]%=MOD;
REP(j,10){
dp2[(d+j)%D] += dp2_copy[d];
dp2[(d+j)%D]%=MOD;
}
REP(j,digits[i]){
dp2[(d+j)%D] += dp1_copy[d];
dp2[(d+j)%D]%=MOD;
}
}
}
printf("%lld\n", (dp1[0]+dp2[0]+MOD-1)%MOD);
return 0;
}
Submission Info
Submission Time |
|
Task |
E - 数 |
User |
fockl |
Language |
C++14 (GCC 5.4.1) |
Score |
4 |
Code Size |
3684 Byte |
Status |
AC |
Exec Time |
319 ms |
Memory |
512 KB |
Judge Result
Set Name |
All |
Score / Max Score |
4 / 4 |
Status |
|
Set Name |
Test Cases |
All |
00, 01, 02, 90, 91 |
Case Name |
Status |
Exec Time |
Memory |
00 |
AC |
5 ms |
512 KB |
01 |
AC |
191 ms |
512 KB |
02 |
AC |
319 ms |
512 KB |
90 |
AC |
1 ms |
256 KB |
91 |
AC |
1 ms |
256 KB |