結果
| 問題 | No.1783 Remix Sum |
| ユーザー |
 sigma425
|
| 提出日時 | 2021-12-14 08:09:44 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 13,043 bytes |
| コンパイル時間 | 3,226 ms |
| コンパイル使用メモリ | 230,484 KB |
| 実行使用メモリ | 51,652 KB |
| 最終ジャッジ日時 | 2024-07-23 09:22:47 |
| 合計ジャッジ時間 | 97,818 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 KB |
| testcase_01 | AC | 2 ms
6,940 KB |
| testcase_02 | AC | 2 ms
6,940 KB |
| testcase_03 | AC | 3 ms
6,944 KB |
| testcase_04 | AC | 1,130 ms
12,260 KB |
| testcase_05 | AC | 781 ms
10,696 KB |
| testcase_06 | AC | 1,764 ms
15,384 KB |
| testcase_07 | AC | 2,357 ms
15,660 KB |
| testcase_08 | AC | 1,012 ms
12,140 KB |
| testcase_09 | AC | 1,174 ms
12,924 KB |
| testcase_10 | AC | 778 ms
10,696 KB |
| testcase_11 | AC | 600 ms
9,892 KB |
| testcase_12 | AC | 2,090 ms
15,016 KB |
| testcase_13 | AC | 786 ms
10,976 KB |
| testcase_14 | AC | 859 ms
11,356 KB |
| testcase_15 | AC | 1,389 ms
29,608 KB |
| testcase_16 | AC | 2,346 ms
15,792 KB |
| testcase_17 | AC | 2,617 ms
16,568 KB |
| testcase_18 | AC | 605 ms
9,788 KB |
| testcase_19 | AC | 1,814 ms
16,172 KB |
| testcase_20 | AC | 968 ms
11,940 KB |
| testcase_21 | AC | 1,800 ms
16,048 KB |
| testcase_22 | AC | 1,660 ms
15,392 KB |
| testcase_23 | AC | 1,716 ms
15,980 KB |
| testcase_24 | AC | 519 ms
10,088 KB |
| testcase_25 | AC | 1,762 ms
15,388 KB |
| testcase_26 | AC | 2,093 ms
14,860 KB |
| testcase_27 | AC | 1,929 ms
16,164 KB |
| testcase_28 | AC | 750 ms
10,700 KB |
| testcase_29 | AC | 1,118 ms
12,856 KB |
| testcase_30 | AC | 972 ms
11,812 KB |
| testcase_31 | AC | 1,640 ms
15,392 KB |
| testcase_32 | AC | 3,092 ms
33,960 KB |
| testcase_33 | AC | 1,116 ms
12,704 KB |
| testcase_34 | AC | 528 ms
9,964 KB |
| testcase_35 | AC | 801 ms
10,980 KB |
| testcase_36 | AC | 840 ms
27,692 KB |
| testcase_37 | AC | 838 ms
27,568 KB |
| testcase_38 | AC | 800 ms
11,080 KB |
| testcase_39 | AC | 531 ms
9,832 KB |
| testcase_40 | AC | 593 ms
9,920 KB |
| testcase_41 | AC | 531 ms
9,964 KB |
| testcase_42 | AC | 533 ms
9,964 KB |
| testcase_43 | AC | 800 ms
10,980 KB |
| testcase_44 | AC | 8,181 ms
43,388 KB |
| testcase_45 | AC | 7,842 ms
43,516 KB |
| testcase_46 | AC | 7,292 ms
43,408 KB |
| testcase_47 | AC | 6,945 ms
43,068 KB |
| testcase_48 | TLE | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb push_back
#define eb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> bool chmax(T& x, U y){
if(x<y){ x=y; return true; }
return false;
}
template<class T,class U> bool chmin(T& x, U y){
if(y<x){ x=y; return true; }
return false;
}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class T> int lwb(const V<T>& v, const T& a){return lower_bound(all(v),a) - v.begin();}
template<class T>
V<T> Vec(size_t a) {
return V<T>(a);
}
template<class T, class... Ts>
auto Vec(size_t a, Ts... ts) {
return V<decltype(Vec<T>(ts...))>(a, Vec<T>(ts...));
}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
o<<"{";
for(const T& v:vc) o<<v<<",";
o<<"}";
return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }
#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
os<<t<<" ~ ";
dmpr(os,args...);
}
#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {"; \
for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif
template<class D> D divFloor(D a, D b){
return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0);
}
template<class D> D divCeil(D a, D b) {
return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0);
}
template<unsigned int mod_>
struct ModInt{
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr static uint mod = mod_;
uint v;
ModInt():v(0){}
ModInt(ll _v):v(normS(_v%mod+mod)){}
explicit operator bool() const {return v!=0;}
static uint normS(const uint &x){return (x<mod)?x:x-mod;} // [0 , 2*mod-1] -> [0 , mod-1]
static ModInt make(const uint &x){ModInt m; m.v=x; return m;}
ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));}
ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));}
ModInt operator-() const { return make(normS(mod-v)); }
ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);}
ModInt operator/(const ModInt& b) const { return *this*b.inv();}
ModInt& operator+=(const ModInt& b){ return *this=*this+b;}
ModInt& operator-=(const ModInt& b){ return *this=*this-b;}
ModInt& operator*=(const ModInt& b){ return *this=*this*b;}
ModInt& operator/=(const ModInt& b){ return *this=*this/b;}
ModInt& operator++(int){ return *this=*this+1;}
ModInt& operator--(int){ return *this=*this-1;}
template<class T> friend ModInt operator+(T a, const ModInt& b){ return (ModInt(a) += b);}
template<class T> friend ModInt operator-(T a, const ModInt& b){ return (ModInt(a) -= b);}
template<class T> friend ModInt operator*(T a, const ModInt& b){ return (ModInt(a) *= b);}
template<class T> friend ModInt operator/(T a, const ModInt& b){ return (ModInt(a) /= b);}
ModInt pow(ll p) const {
if(p<0) return inv().pow(-p);
ModInt a = 1;
ModInt x = *this;
while(p){
if(p&1) a *= x;
x *= x;
p >>= 1;
}
return a;
}
ModInt inv() const { // should be prime
return pow(mod-2);
}
// ll extgcd(ll a,ll b,ll &x,ll &y) const{
// ll p[]={a,1,0},q[]={b,0,1};
// while(*q){
// ll t=*p/ *q;
// rep(i,3) swap(p[i]-=t*q[i],q[i]);
// }
// if(p[0]<0) rep(i,3) p[i]=-p[i];
// x=p[1],y=p[2];
// return p[0];
// }
// ModInt inv() const {
// ll x,y;
// extgcd(v,mod,x,y);
// return make(normS(x+mod));
// }
bool operator==(const ModInt& b) const { return v==b.v;}
bool operator!=(const ModInt& b) const { return v!=b.v;}
bool operator<(const ModInt& b) const { return v<b.v;}
friend istream& operator>>(istream &o,ModInt& x){
ll tmp;
o>>tmp;
x=ModInt(tmp);
return o;
}
friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;}
};
using mint = ModInt<120586241>;
// inplace_fmt (without bit rearranging)
// fft:
// a[rev(i)] <- \sum_j \zeta^{ij} a[j]
// invfft:
// a[i] <- (1/n) \sum_j \zeta^{-ij} a[rev(j)]
// These two are inversions.
// !!! CHANGE IF MOD is unusual !!!
const int ORDER_2_MOD_MINUS_1 = 20; // ord_2 (mod-1)
const mint PRIMITIVE_ROOT = 6; // primitive root of (Z/pZ)*
void fft(V<mint>& a){
static constexpr uint mod = mint::mod;
static constexpr uint mod2 = mod + mod;
static const int H = ORDER_2_MOD_MINUS_1;
static const mint root = PRIMITIVE_ROOT;
static mint magic[H-1];
int n = si(a);
assert(!(n & (n-1))); assert(n >= 1); assert(n <= 1<<H); // n should be power of 2
if(!magic[0]){ // precalc
rep(i,H-1){
mint w = -root.pow(((mod-1)>>(i+2))*3);
magic[i] = w;
}
}
int m = n;
if(m >>= 1){
rep(i,m){
uint v = a[i+m].v; // < M
a[i+m].v = a[i].v + mod - v; // < 2M
a[i].v += v; // < 2M
}
}
if(m >>= 1){
mint p = 1;
for(int h=0,s=0; s<n; s += m*2){
for(int i=s;i<s+m;i++){
uint v = (a[i+m] * p).v; // < M
a[i+m].v = a[i].v + mod - v; // < 3M
a[i].v += v; // < 3M
}
p *= magic[__builtin_ctz(++h)];
}
}
while(m){
if(m >>= 1){
mint p = 1;
for(int h=0,s=0; s<n; s += m*2){
for(int i=s;i<s+m;i++){
uint v = (a[i+m] * p).v; // < M
a[i+m].v = a[i].v + mod - v; // < 4M
a[i].v += v; // < 4M
}
p *= magic[__builtin_ctz(++h)];
}
}
if(m >>= 1){
mint p = 1;
for(int h=0,s=0; s<n; s += m*2){
for(int i=s;i<s+m;i++){
uint v = (a[i+m] * p).v; // < M
a[i].v = (a[i].v >= mod2) ? a[i].v - mod2 : a[i].v; // < 2M
a[i+m].v = a[i].v + mod - v; // < 3M
a[i].v += v; // < 3M
}
p *= magic[__builtin_ctz(++h)];
}
}
}
rep(i,n){
a[i].v = (a[i].v >= mod2) ? a[i].v - mod2 : a[i].v; // < 2M
a[i].v = (a[i].v >= mod) ? a[i].v - mod : a[i].v; // < M
}
// finally < mod !!
}
void invfft(V<mint>& a){
static constexpr uint mod = mint::mod;
static constexpr uint mod2 = mod + mod;
static const int H = ORDER_2_MOD_MINUS_1;
static const mint root = PRIMITIVE_ROOT;
static mint magic[H-1];
int n = si(a);
assert(!(n & (n-1))); assert(n >= 1); assert(n <= 1<<H); // n should be power of 2
if(!magic[0]){ // precalc
rep(i,H-1){
mint w = -root.pow(((mod-1)>>(i+2))*3);
magic[i] = w.inv();
}
}
int m = 1;
if(m < n>>1){
mint p = 1;
for(int h=0,s=0; s<n; s += m*2){
for(int i=s;i<s+m;i++){
ull x = a[i].v + mod - a[i+m].v; // < 2M
a[i].v += a[i+m].v; // < 2M
a[i+m].v = (p.v * x) % mod; // < M
}
p *= magic[__builtin_ctz(++h)];
}
m <<= 1;
}
for(;m < n>>1; m <<= 1){
mint p = 1;
for(int h=0,s=0; s<n; s+= m*2){
for(int i=s;i<s+(m>>1);i++){
ull x = a[i].v + mod2 - a[i+m].v; // < 4M
a[i].v += a[i+m].v; // < 4M
a[i].v = (a[i].v >= mod2) ? a[i].v - mod2 : a[i].v; // < 2M
a[i+m].v = (p.v * x) % mod; // < M
}
for(int i=s+(m>>1); i<s+m; i++){
ull x = a[i].v + mod - a[i+m].v; // < 2M
a[i].v += a[i+m].v; // < 2M
a[i+m].v = (p.v * x) % mod; // < M
}
p *= magic[__builtin_ctz(++h)];
}
}
if(m < n){
rep(i,m){
uint x = a[i].v + mod2 - a[i+m].v; // < 4M
a[i].v += a[i+m].v; // < 4M
a[i+m].v = x; // < 4M
}
}
const mint in = mint(n).inv();
rep(i,n) a[i] *= in; // < M
// finally < mod !!
}
/*
h[i1+j1][i2+j2]..[ik+jk] += f[i1][i2]..[ik] * g[i1][i2]..[ik] をする
ただし 添字の範囲は 0 <= ip,jp < np で、足した結果一箇所でもはみ出た値は捨てる
f,g は flatten されている (i1,i2,..,ik) が i1 + i2n1 + i3n1n2 + .. に対応する
magicはcalc_magicで計算したのを使う
O(knlogn)
各次元を2倍にして愚直にやるとO(2^k nlogn) とかになるはずで、すげ～
*/
V<int> calc_magic(const vector<int>& ns){
int k = si(ns);
if(k == 0) return {};
int n = 1;
for(int ni: ns) n *= ni;
V<int> magic(n);
rep(i,n){
int x = i;
rep(j,k){
magic[i] += x;
x /= ns[j];
}
magic[i] %= k;
}
return magic;
}
vector<mint> multivariate_mult(const vector<mint>& f, const vector<mint>& g, const vector<int>& ns, const vector<int>& magic){
assert(si(f) == si(g));
int n = si(f);
int k = si(ns);
if(k == 0){
return {f[0]*g[0]};
}
int s = 1; while(s<n*2-1) s*=2;
vector<mint> h(n);
vector<vector<mint>> zf(k,vector<mint>(s));
vector<vector<mint>> zg(k,vector<mint>(s));
vector<vector<mint>> zh(k,vector<mint>(s));
rep(i,n) zf[magic[i]][i] = f[i];
rep(i,k) fft(zf[i]);
rep(i,n) zg[magic[i]][i] = g[i];
rep(i,k) fft(zg[i]);
rep(a,k) rep(b,k){
int c = (a+b)%k;
rep(i,s) zh[c][i] += zf[a][i] * zg[b][i];
}
rep(i,k) invfft(zh[i]);
rep(i,n) h[i] = zh[magic[i]][i];
return h;
}
vector<mint> multivariate_log(const vector<mint>& f, const vector<int>& ns, const vector<int>& magic){
exit(1);
}
V<int> tens = {1,10,100,1000,10000,100000};
V<mint> zs;
vector<mint> mult(vector<mint> f, vector<mint> g, int A,int B){
int n = si(f);
auto zeta10 = [&](V<mint> f){
V<mint> g(10);
rep(i,10) rep(j,10) g[i] += f[j] * zs[i*j];
return g;
};
auto izeta10 = [&](V<mint> f){
const static mint i10 = mint(10).inv();
V<mint> g(10);
rep(i,10) rep(j,10) g[i] += f[j] * zs[90-i*j] * i10;
return g;
};
auto zeta = [&](vector<mint> f){
for(int d=A;d<A+B;d++){ // cyclic DFTed dim
rep(s,n) if(s/tens[d]%10 == 0){
V<mint> buf(10);
rep(i,10) buf[i] = f[s+tens[d]*i];
buf = zeta10(buf);
rep(i,10) f[s+tens[d]*i] = buf[i];
}
}
return f;
};
auto izeta = [&](vector<mint> f){
for(int d=A;d<A+B;d++){ // cyclic DFTed dim
rep(s,n) if(s/tens[d]%10 == 0){
V<mint> buf(10);
rep(i,10) buf[i] = f[s+tens[d]*i];
buf = izeta10(buf);
rep(i,10) f[s+tens[d]*i] = buf[i];
}
}
return f;
};
f = zeta(f), g = zeta(g);
V<mint> zf(tens[A]), zg(tens[A]),zh;
V<int> ns(A,10); V<int> magic = calc_magic(ns);
rep(s,si(f)) if(s%tens[A] == 0){
rep(i,tens[A]) zf[i] = f[s+i], zg[i] = g[s+i];
zh = multivariate_mult(zf,zg,ns,magic);
show(zf);show(zg);show(zh);
show(ns);show(magic);
show("------------");
rep(i,tens[A]) f[s+i] = zh[i];
}
f = izeta(f);
return f;
}
template <class T, class Op = multiplies<>>
constexpr T power(T a, uint64_t n, T init = 1, Op op = Op{}) {
while (n) {
if (n & 1) init = op(init, a);
if (n >>= 1) a = op(a, a);
}
return init;
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false); //DON'T USE scanf/printf/puts !!
cout << fixed << setprecision(20);
int N,A,B; ll X;
{
int K;
cin >> N;
cin >> K;
cin >> X;
int T;
cin >> T;
A = T, B = K-T;
}
{
mint z = mint(6).pow((mint::mod-1)/10);
rep(i,91) zs.pb(z.pow(i));
}
V<mint> f(TEN(A+B));
while(N--){
int x; cin >> x; f[x]++;
}
auto mul = [&](auto x,auto y){ return mult(x,y,A,B); };
V<mint> id(TEN(A+B)); id[0] = 1;
// f = power(f,X,id,mul);
// for(auto v: f) cout << v << endl;
V<mint> f0(TEN(A+B)),f1(TEN(A+B));
rep(s,TEN(A+B)){
if(s%TEN(A) == 0) f0[s] = f[s];
else f1[s] = f[s];
}
ll XX = max(X-45,0LL);
ll work = X-XX;
VV<mint> f1pow(work+1);
f1pow[0] = id;
rep1(i,work) f1pow[i] = mul(f1pow[i-1], f1);
int n = si(f);
auto zeta10 = [&](V<mint> f){
V<mint> g(10);
rep(i,10) rep(j,10) g[i] += f[j] * zs[i*j];
return g;
};
auto izeta10 = [&](V<mint> f){
const static mint i10 = mint(10).inv();
V<mint> g(10);
rep(i,10) rep(j,10) g[i] += f[j] * zs[90-i*j] * i10;
return g;
};
auto zeta = [&](vector<mint> f){
for(int d=A;d<A+B;d++){ // cyclic DFTed dim
rep(s,n) if(s/tens[d]%10 == 0){
V<mint> buf(10);
rep(i,10) buf[i] = f[s+tens[d]*i];
buf = zeta10(buf);
rep(i,10) f[s+tens[d]*i] = buf[i];
}
}
return f;
};
auto izeta = [&](vector<mint> f){
for(int d=A;d<A+B;d++){ // cyclic DFTed dim
rep(s,n) if(s/tens[d]%10 == 0){
V<mint> buf(10);
rep(i,10) buf[i] = f[s+tens[d]*i];
buf = izeta10(buf);
rep(i,10) f[s+tens[d]*i] = buf[i];
}
}
return f;
};
show(f0);
show(f1);
show(f1pow);
show(XX);
VV<mint> hs(work+1);
if(true){
auto g0 = zeta(f0);
V<mint> g(TEN(A+B));
rep(s,n) if(s%TEN(A) == 0) g[s] = g0[s].pow(XX);
rep(i,work+1){
hs[work-i] = izeta(g);
rep(s,n) g[s] *= g0[s];
}
}else{
rep(i,work+1){
hs[i] = power(f0,X-i,id,mul);
}
}
show(hs);
V<mint> ans(TEN(A+B));
mint choose = 1;
rep(i,work+1){
auto p = mul(f1pow[i],hs[i]);
rep(s,n) ans[s] += p[s] * choose;
choose *= X-i;
choose /= i+1;
}
rep(s,n) cout << ans[s] << endl;
}