結果
| 問題 | No.1631 Sorting Integers (Multiple of K) Easy |
| ユーザー |
 arahi10
|
| 提出日時 | 2021-07-30 22:40:47 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2,923 ms / 3,000 ms |
| コード長 | 20,460 bytes |
| コンパイル時間 | 4,291 ms |
| コンパイル使用メモリ | 274,708 KB |
| 最終ジャッジ日時 | 2025-01-23 12:22:21 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 28 |
コンパイルメッセージ
main.cpp: In function ‘void scanner::scan(char*)’:
main.cpp:325:37: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
325 | void scan(char a[]) { std::scanf("%s", a); }
| ~~~~~~~~~~^~~~~~~~~
ソースコード
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
template <class T>
struct BIT2{
public:
vector<unordered_map<long long,T>> data;
long long H,W;
long long fidx=0;
BIT2(long long H,long long W,long long first_index=0):data(H),H(H),W(W),fidx(first_index){}
T sum(const long long x,const long long y){
T ret=0;
long long i=x,j=y;
//if (fidx==0){i++;j++;}
while (i>0){
long long k=j;
while (k>0){
ret+=this->data[i][k];
k -= k&-k;
}
i -= i& -i;
}
return ret;
}
void add(const long long x,const long long y,const T &delta){
long long i=x,j=y;
//if (fidx==0){i+=1;j+=1;}
while (i<=H){
long long k = j;
while (k<=W){
this->data[i][k]+=delta;
k += k&-k;
}
i += i& -i;
}
}
T range_sum(long long x0,long long x1,long long y0, long long y1){
/*x0-=fidx;
x1-=fidx;
y0-=fidx;
y1-=fidx;*/
return this->sum(x1, y1) - this->sum(x1, y0) - this->sum(x0, y1) + this->sum(x0, y0);
}
T get(long long x, long long y){
return this->range_sum(x,x+1,y,y+1);
}
};
template <class T>
struct matrix
{
std::valarray<T> value;
size_t N;
matrix(size_t size, T init) : value(init, size * size), N(size) {}
matrix(size_t size) : value(size * size), N(size) {}
matrix(matrix *M) : value(M->value), N(M->N) {}
matrix(valarray<T> v, size_t size) : value(v), N(size) {}
public:
matrix &operator=(const matrix &B)
{
this->value = std::valarray<T>(B.value);
return *this;
}
/*const std::valarray<T>& operator [](const size_t i)const{
return *std::valarray<T>(value[std::slice(N*i,N,1)]);
}
std::valarray<T>& operator [](const size_t i){
//書き込み用
return *(value[std::slice(N*i,N,1)]);
}*/
const matrix operator+(const matrix &B) const
{
return matrix(value + B.value, N);
}
const matrix operator-(const matrix &B) const
{
return matrix(value - B.value, N);
}
const matrix operator*(const matrix &B) const
{
std::valarray<T> ret(N * N);
for (size_t i = 0; i < N; i++)
{
for (size_t j = 0; j < N; j++)
{
ret[N * i + j] = (T)(value[std::slice(N * i, N, 1)] * (B.value[std::slice(j, N, N)])).sum();
}
}
return matrix(ret, N);
}
matrix &operator+=(const matrix &B)
{
value += B.value;
return *this;
}
matrix &operator-=(const matrix &B)
{
value -= B.value;
return *this;
}
matrix &operator*=(const matrix &B)
{
*this = (*this) * B;
return *this;
}
matrix &operator=(const T &v)
{
std::valarray<T> ret(N * N);
for (size_t i = 0; i < N * N; i += N + 1)
ret[i] = v;
value = ret;
return *this;
}
const matrix operator+(const T &v) const
{
std::valarray<T> delta(N * N);
for (size_t i = 0; i < N * N; i += N + 1)
delta[i] = v;
return matrix(value + delta, N);
}
const matrix operator-(const T &v) const
{
std::valarray<T> delta(N * N);
for (size_t i = 0; i < N * N; i += N + 1)
delta[i] = v;
return matrix(value - delta, N);
}
const matrix operator*(const T &v) const
{
return matrix(value * v, N);
}
const matrix operator/(const T &v) const
{
return matrix(value / v, N);
}
const matrix operator^(long long n) const
{
assert(n >= 0);
matrix<T> a(N), ret(N);
ret = (T)1;
a.value = this->value;
while (n)
{
if (n & 1)
ret *= a;
a *= a;
n >>= 1;
}
return matrix(ret.value, N);
}
matrix &operator^=(long long n)
{
*(this) = *(this) ^ n;
return *this;
}
const matrix Transpose() const
{
std::valarray<T> ret(N * N);
for (size_t i = 0; i < N; i++)
for (size_t j = 0; j < N; j++)
ret[N * i + j] = value[j * N + i];
return matrix(ret, N);
}
};
#pragma region Macros
// rep macro
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload3(_1, _2, _3, name, ...) name
#define rep1(i, n) for (ll i = 0; i < n; ++i)
#define rep2(i, a, b) for (ll i = a; i < b; ++i)
#define rep3(i, a, b, c) for (ll i = a, _bb = b; (a <= i && i < _bb) or (a >= i && i > _bb); i += c)
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define each1(i, a) for (auto &&i : a)
#define each2(x, y, a) for (auto &&[x, y] : a)
#define each3(x, y, z, a) for (auto &&[x, y, z] : a)
#define each(...) overload4(__VA_ARGS__, each3, each2, each1)(__VA_ARGS__)
#define extrep(v, ...) for (auto v : __MAKE_MAT__({__VA_ARGS__}))
vector<vector<long long>> __MAKE_MAT__(vector<long long> v)
{
if (v.empty())
return vector<vector<long long>>(1, vector<long long>());
long long n = v.back();
v.pop_back();
vector<vector<long long>> ret;
vector<vector<long long>> tmp = __MAKE_MAT__(v);
for (auto e : tmp)
for (long long i = 0; i < n; ++i)
{
ret.push_back(e);
ret.back().push_back(i);
}
return ret;
} //extrep(v,3,4,5)->v=[0,3)x[0,4)x[0,5)
#define vep(i, v) for (auto(i) = std::begin(v); std::distance(std::begin(i), (std::end(v))) > 0; ++(i))
// name macro
#define all(v) std::begin(v), std::end(v)
#define rall(v) std::rbegin(v), std::rend(v)
template <class T = int>
using V = std::vector<T>;
template <class T = int>
using VV = std::vector<std::vector<T>>;
template <class T>
using pqup = std::priority_queue<T, std::vector<T>, std::greater<T>>;
using ld = long double;
using int128 = __int128_t;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;
using ll = long long;
using Int = long long;
#define eb emplace_back
#define pb push_back
//py macro
#define elif else if
#define Sum(...) accumulate(all(__VA_ARGS__), 0LL)
template <class T>
int bisect_left(const std::vector<T> &a, const T x)
{
return std::distance(std::begin(a), std::lower_bound(std::begin(a), std::end(a), (x)));
}
template <class T>
int bl(const std::vector<T> &a, const T x) { return std::distance(std::begin(a), std::lower_bound(std::begin(a), std::end(a), (x))); }
template <class T>
int bisect_right(const std::vector<T> &a, const T x) { return std::distance(std::begin(a), std::upper_bound(std::begin(a), std::end(a), (x))); }
template <class T>
int br(const std::vector<T> &a, const T x) { return std::distance(std::begin(a), std::upper_bound(std::begin(a), std::end(a), (x))); }
#define Sort(x) sort(std::begin(x), std::end(x))
#define Reverse(x) reverse(std::begin(x), std::end(x))
#define len(x) (ll) x.size()
#define popcnt(x) __builtin_popcountll(x)
// input macro
template <class T, class U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p)
{
is >> p.first >> p.second;
return is;
}
template <class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v)
{
for (T &i : v)
is >> i;
return is;
}
template <class T>
std::istream &operator>>(std::istream &is, std::valarray<T> &v)
{
for (T &i : v)
is >> i;
return is;
}
template <class T>
std::istream &operator>>(std::istream &is, matrix<T> &v)
{
for (T &i : v.value)
is >> i;
return is;
}
std::istream &operator>>(std::istream &is, __int128_t &a)
{
std::string s;
is >> s;
__int128_t ret = 0;
for (int i = 0; i < s.length(); i++)
if ('0' <= s[i] and s[i] <= '9')
ret = 10 * ret + s[i] - '0';
a = ret * (s[0] == '-' ? -1 : 1);
return is;
}
#if __has_include(<atcoder/all>)
std::istream &operator>>(std::istream &is, atcoder::modint998244353 &a)
{
long long v;
is >> v;
a = v;
return is;
}
std::istream &operator>>(std::istream &is, atcoder::modint1000000007 &a)
{
long long v;
is >> v;
a = v;
return is;
}
template <int m>
std::istream &operator>>(std::istream &is, atcoder::static_modint<m> &a)
{
long long v;
is >> v;
a = v;
return is;
}
template <int m>
std::istream &operator>>(std::istream &is, atcoder::dynamic_modint<m> &a)
{
long long v;
is >> v;
a = v;
return is;
}
#endif
namespace scanner
{
void scan(int &a) { std::cin >> a; }
void scan(long long &a) { std::cin >> a; }
void scan(std::string &a) { std::cin >> a; }
void scan(char &a) { std::cin >> a; }
void scan(char a[]) { std::scanf("%s", a); }
void scan(double &a) { std::cin >> a; }
void scan(long double &a) { std::cin >> a; }
template <class T, class U>
void scan(std::pair<T, U> &p) { std::cin >> p; }
template <class T>
void scan(std::vector<T> &a) { std::cin >> a; }
template <class T>
void scan(std::valarray<T> &a) { std::cin >> a; }
template <class T>
void scan(matrix<T> &a) { std::cin >> a; }
void INPUT() {}
template <class Head, class... Tail>
void INPUT(Head &head, Tail &...tail)
{
scan(head);
INPUT(tail...);
}
} // namespace scanner
#define VEC(type, name, size) \
std::vector<type> name(size); \
scanner::INPUT(name)
#define VAL(type, name, size) \
std::valarray<type> name(size); \
scanner::INPUT(name)
#define VVEC(type, name, h, w) \
std::vector<std::vector<type>> name(h, std::vector<type>(w)); \
scanner::INPUT(name)
#define MAT(type, name, n) \
matrix<type> name(n); \
scanner::INPUT(name)
#define INT(...) \
int __VA_ARGS__; \
scanner::INPUT(__VA_ARGS__)
#define LL(...) \
long long __VA_ARGS__; \
scanner::INPUT(__VA_ARGS__)
#define STR(...) \
std::string __VA_ARGS__; \
scanner::INPUT(__VA_ARGS__)
#define CHAR(...) \
char __VA_ARGS__; \
scanner::INPUT(__VA_ARGS__)
#define DOUBLE(...) \
double __VA_ARGS__; \
scanner::INPUT(__VA_ARGS__)
#define LD(...) \
long double __VA_ARGS__; \
scanner::INPUT(__VA_ARGS__)
struct input
{
input(){};
template <class T>
operator T()
{
T t;
cin >> t;
return t;
}
};
// output-macro
template <class T, class U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p)
{
os << p.first << " " << p.second;
return os;
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &a)
{
for (int i = 0; i < int(a.size()); ++i)
{
if (i)
os << " ";
os << a[i];
}
return os;
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::valarray<T> &a)
{
for (int i = 0; i < int(a.size()); ++i)
{
if (i)
os << " ";
os << a[i];
}
return os;
}
std::ostream &operator<<(std::ostream &dest, __int128_t &value)
{
std::ostream::sentry s(dest);
if (s)
{
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char *d = std::end(buffer);
do
{
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0)
{
--d;
*d = '-';
}
int len = std::end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len)
{
dest.setstate(std::ios_base::badbit);
}
}
return dest;
}
#if __has_include(<atcoder/all>)
std::ostream &operator<<(std::ostream &os, const atcoder::modint998244353 &a)
{
return os << a.val();
}
std::ostream &operator<<(std::ostream &os, const atcoder::modint1000000007 &a) { return os << a.val(); }
template <int m>
std::ostream &operator<<(std::ostream &os, const atcoder::static_modint<m> &a) { return os << a.val(); }
template <int m>
std::ostream &operator<<(std::ostream &os, const atcoder::dynamic_modint<m> &a) { return os << a.val(); }
#endif
template <class T>
void print(const T a)
{
std::cout << a << '\n';
}
template <class Head, class... Tail>
void print(Head H, Tail... T)
{
std::cout << H << ' ';
print(T...);
}
template <class T>
void printel(const T a) { std::cout << a << '\n'; }
template <class T>
void printel(const std::vector<T> &a)
{
for (const auto &v : a)
std::cout << v << '\n';
}
template <class Head, class... Tail>
void printel(Head H, Tail... T)
{
std::cout << H << '\n';
printel(T...);
}
inline void Yes(const bool b = true) { std::cout << (b ? "Yes\n" : "No\n"); }
inline void No() { std::cout << "No\n"; }
inline void YES(const bool b = true) { std::cout << (b ? "YES\n" : "NO\n"); }
inline void NO() { std::cout << "NO\n"; }
inline void err(const bool b = true)
{
if (b)
std::cout << "-1\n", exit(0);
}
inline void First(const bool b = true) { std::cout << (b ? "First\n" : "Second\n"); }
inline void first(const bool b = true) { std::cout << (b ? "first\n" : "second\n"); }
template <class T>
inline void Case(const long long &number, T ans)
{
printf("Case #%d: ", number);
cout << ans << "\n";
}
//debug macro
namespace debugger
{
template <class T>
void view(const std::vector<T> &a)
{
std::cerr << "{ ";
for (const auto &v : a)
{
std::cerr << v << ", ";
}
std::cerr << "\b\b }";
}
template <class T>
void view(const std::valarray<T> &a)
{
std::cerr << "{ ";
for (const auto &v : a)
{
std::cerr << v << ", ";
}
std::cerr << "\b\b }";
}
template <class T>
void view(const std::vector<std::vector<T>> &a)
{
std::cerr << "{\n";
for (const auto &v : a)
{
std::cerr << "\t";
view(v);
std::cerr << "\n";
}
std::cerr << "}";
}
template <class T>
void view(const matrix<T> &a)
{
std::cerr << "{\n";
for (int i = 0; i < a.N; i++)
{
std::cerr << "\t";
valarray<T> inner = a.value[std::slice(i * a.N, a.N, 1)];
view(inner);
std::cerr << "\n";
}
std::cerr << "}";
}
template <class T, class U>
void view(const std::vector<std::pair<T, U>> &a)
{
std::cerr << "{\n";
for (const auto &p : a)
std::cerr << "\t(" << p.first << ", " << p.second << ")\n";
std::cerr << "}";
}
template <class T, class U>
void view(const std::map<T, U> &m)
{
std::cerr << "{\n";
for (const auto &p : m)
std::cerr << "\t[" << p.first << "] : " << p.second << "\n";
std::cerr << "}";
}
template <class T, class U>
void view(const std::pair<T, U> &p) { std::cerr << "(" << p.first << ", " << p.second << ")"; }
template <class T>
void view(const std::set<T> &s)
{
std::cerr << "{ ";
for (auto &v : s)
{
view(v);
std::cerr << ", ";
}
std::cerr << "\b\b }";
}
template <class T>
void view(const T &e) { std::cerr << e; }
} // namespace debugger
#ifdef LOCAL
void debug_out()
{
}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
debugger::view(H);
std::cerr << ", ";
debug_out(T...);
}
#define debug(...) \
do \
{ \
std::cerr << __LINE__ << " [" << #__VA_ARGS__ << "] : ["; \
debug_out(__VA_ARGS__); \
std::cerr << "\b\b]\n"; \
} while (false)
#else
#define debug(...) (void(0))
#endif
// vector macro
template <class T>
void uniq(std::vector<T> &a)
{
std::sort(std::begin(a), std::end(a));
a.erase(std::unique(std::begin(a), std::end(a)), std::end(a));
}
template <class T>
std::vector<T> press(std::vector<T> &a)
{
auto res = a;
UNIQUE(res);
for (auto &v : a)
v = lb(res, v);
return res;
}
#define SORTname(a, b, c, ...) c
#define SORT(...) SORTname(__VA_ARGS__, SORT1, SORT0, ...)(__VA_ARGS__)
#define SORT0(a) std::sort(std::begin(a), std::end(a))
#define SORT1(a, c) std::sort(std::begin(a), std::end(a), [](const auto x, const auto y) { return x c y; })
// math macro
template <class T>
inline T GCD(T a, T b) { return b ? GCD(b, a % b) : a; }
template <class T>
inline T LCM(T a, T b) { return a / GCD(a, b) * b; }
template <class T>
inline T modinv(T a, T M) { return (1 - M * modinv(M % a, a)) / a + M; }
template <class T, class U>
inline bool chmin(T &a, const U &b) { return a > b ? a = b, true : false; }
template <class T, class U>
inline bool chmax(T &a, const U &b) { return a < b ? a = b, true : false; }
template <class T>
inline T ceildiv(T x, T y) { return (x + y - 1) / y; }
template <class T>
T POW(T a, long long n)
{
T ret = 1;
while (n)
{
if (n & 1)
ret *= a;
a *= a;
n >>= 1;
}
return ret;
}
// modpow
long long POW(long long a, long long n, const int mod)
{
long long ret = 1;
while (n)
{
if (n & 1)
(ret *= a) %= mod;
(a *= a) %= mod;
n >>= 1;
}
return ret;
}
// find integer x s.t. x^2<=n<(x+1)^2
template <class T>
T isqrt(T n)
{
if (n == 0)
return 0;
if (n < 0)
return -1;
unsigned long long int m = n;
m |= m >> 1;
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
T x = 1 << ((__builtin_popcount(m) + 1) / 2);
T y = (x + n / x) / 2;
while (y < x)
{
x = y;
y = (x + n / x) / 2;
}
return x;
}
//部分集合の列挙
std::vector<unsigned int> subset(unsigned int S)
{
unsigned int cnt = __builtin_popcount(S);
std::vector<unsigned int> ret(1 << cnt, 0);
int head = (1 << cnt) - 1;
for (unsigned int T = S; T != 0; T = S & (T - 1), head--)
{
ret[head] = T;
}
return ret;
}
//N桁の二進数のうち丁度Kbitだけ立っている数の列挙
std::vector<unsigned long long> bits(long long N, long long K)
{
unsigned long long v = (1 << K) - 1, MAX = 1 << N;
std::vector<unsigned long long> ret(0);
unsigned long long x, y;
while (v < MAX)
{
ret.emplace_back(v);
x = v & (-v);
y = v + x;
v = (v & ~y) / x >> 1 | y;
}
return ret;
}
int bit_length(unsigned long long x)
{
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
return __builtin_popcountll(x);
}
vector<pair<long long,int>> childs( long long S){
long long tmp=S;
vector<pair<long long,int>> ret(0);
while(tmp){
unsigned long long v=tmp&(-tmp);
tmp^=v;
ret.emplace_back( pair<long long,int>(S^v,bit_length(v)-1));
}
return ret;
}
// others
struct fast_io
{
fast_io()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} fast_io_;
inline std::vector<std::pair<long long, long long>> NEXT(long long x, long long y) { return {{x - 1, y}, {x, y - 1}, {x, y + 1}, {x + 1, y}}; }
inline std::vector<std::pair<long long, long long>> NEXT8(long long x, long long y) { return {{x - 1, y - 1}, {x - 1, y}, {x - 1, y + 1}, {x, y - 1}, {x, y + 1}, {x + 1, y - 1}, {x + 1, y}, {x + 1, y + 1}}; }
constexpr const int inf = 1e9;
constexpr const long long linf = 10e17;
//int |x|<=2*10**9 long |x|<= 9*10**18
//constexpr const long long mod2 = 998244353;
//constexpr const long long mod = 1000000007;
using mint = modint1000000007;
int main()
{
fast_io();
INT(N);
LL(K);
VEC(int,C,9);
V<> nums(0);
rep(i,9)rep(j,C[i])nums.eb(i+1);
V<unordered_map<ll,ll>> dp(1<<N);
dp[0][0]=1;
rep(S,1,1<<N){
for(auto p:childs(S)){
long long P=p.first;
int num=nums[p.second];
for(auto O:dp[P]){
long long k=O.first,v=O.second;
dp[S][(10*k+num)%K]+=v;
}
}
}
V<long long> fact(15,1ll);
rep(i,1,15){
fact[i]=fact[i-1]*i;
}
long long f=dp[(1<<N)-1][0];
for(auto v:C){
f/=fact[v];
}
print(f);
}