多校训练营2

E:Falfa with Substring

z3475

标签

DP;数学

题意

求长度为n的由小写字母组成的字符串中恰好包含i个"bit"的数量。

思路

有

可以很快算出来，问题来到了怎么根据右式求。解开组合数得

分割无关系数

建立新数列

用级数表达数列，为了方便令，就变成了

满足卷积形式

可知

则

展开拿ntt算一下多项式乘积即可。

参考代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
#include <bits/stdc++.h>
using namespace std;
struct FAST_IO{
    FAST_IO(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    }
}__fast_io;
#if __cplusplus < 201402L
template<class T, class U=T>
T exchange(T& obj, U&& new_value){
    T old_value=move(obj);
    obj=forward<U>(new_value);
    return old_value;
}
#endif
#define cons(a,...) a=typename decay<decltype(a)>::type(__VA_ARGS__)
using INT=int;
#define DEF_NUM(num) \
using i##num=int##num##_t;using u##num=uint##num##_t;
DEF_NUM(8)DEF_NUM(16)DEF_NUM(32)DEF_NUM(64)
using i128=__int128;using u128=unsigned __int128;
using usize=uintptr_t;using isize=intptr_t;
using f32=float;using f64=double;using f128=long double;
#define x first
#define y second
//#define int long long
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
auto &_=std::ignore;
using ll=long long;
template<class T>
using vec=vector<T>;
template<bool B,class T=void>
using enableif_t=typename enable_if<B,T>::type;

#define DEF_COULD(name,exp) \
template<class U> \
struct name{\
    template<class T>\
    constexpr static auto is(int i)->decltype(exp,true){return true;}\
    template<class T>\
    constexpr static bool is(...){return false;}\
    static const bool value=is<U>(1);\
};
#define DEF_CAN(name,exp) DEF_COULD(can##name,exp)
#define ENABLE(T,name) enableif_t<can##name<T>::value>(1)
#define ENABLEN(T,name) enableif_t<!can##name<T>::value>(1)
#define FOR_TUPLE enableif_t<i!=tuple_size<T>::value>(1)
#define END_TUPLE enableif_t<i==tuple_size<T>::value>(1)
#define FOR_TUPLET(T) enableif_t<i!=tuple_size<T>::value>(1)
#define END_TUPLET(T) enableif_t<i==tuple_size<T>::value>(1)

#define DEF_INF(name,exp)\
constexpr struct{\
    template<class T>\
    constexpr operator T()const {return numeric_limits<T>::exp();}\
} name;

DEF_CAN(Out,(cout<<*(T*)(0))) DEF_CAN(For,begin(*(T*)(0)))
DEF_INF(INF,max) DEF_INF(MINF,min)
DEF_CAN(Array,declval<T>()[0])

template<size_t i,class T>
auto operator>>(istream& is,T &r)->decltype(END_TUPLE,is){
    return is;
}
template<size_t i=0,class T>
auto operator>>(istream& is,T &r)->decltype(FOR_TUPLE,is){
    is>>get<i>(r);
    return operator>> <i+1>(is,r);
}

template<size_t i,class ...Args>
auto operator>>(istream& is,const tuple<Args&...> &r)->decltype(END_TUPLET(tuple<Args&...>),is){
    return is;
}
template<size_t i=0,class ...Args>
auto operator>>(istream& is,const tuple<Args&...> &r)->decltype(FOR_TUPLET(tuple<Args&...>),is){
    is>>get<i>(r);
    return operator>> <i+1>(is,r);
}

template<class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLE(T,Out),c+1);
template<size_t i,class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLEN(T,For),END_TUPLE,c+1);
template<size_t i=0,class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLEN(T,For),FOR_TUPLE,c+1);
template<class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLEN(T,Out),ENABLE(T,For),c+1);


template<class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLE(T,Out),c+1){
    os << cv;
    while (*c!='}') c++;
    return c+1;
}
template<size_t i,class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLEN(T,For),END_TUPLE,c+1){
    return c;
}
template<size_t i,class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLEN(T,For),FOR_TUPLE,c+1){
    while (*c!='{') os << *c++;
    c=__format(os,c,get<i>(cv));
    return __format<i+1>(os,c,cv);
}
template<class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLEN(T,Out),ENABLE(T,For),c+1){
    const char *ct=c+1;
    if (cv.size()==0){
        int b=1;
        while (1){
            if (*ct=='}') b--;
            if (*ct=='{') b++;
            if (!b) break;
            ct++;
        }
    }else{
        for (auto &i:cv){
            const char *cc=c+1;
            while (*cc!='{') os << *cc++;
            cc=__format(os,cc,i);
            while (*cc!='}') os << *cc++;
            ct=cc;
        }
    }
    return ct+1;
}
void _format(ostream &os,const char *c){
    while (*c!='{'&&*c!='\0') os<< *c++;
}
template<class T,class ...Args>
void _format(ostream &os,const char *c,const T &a,const Args& ...rest){
    while (*c!='{'&&*c!='\0') os<< *c++;
    if (*c=='{') c=__format(os,c,a);
    _format(os,c,rest...);
}
template<class ...Args>
string format(const char *c,const Args& ...rest){
    ostringstream os;
    _format(os,c,rest...);
    return os.str();
}
template<class ...Args>
ostream& print(const char *c,const Args& ...rest){return _format(cout,c,rest...),cout;}
template<class ...Args>
ostream& println(const char *c,const Args& ...rest){return print(c,rest...)<<endl;}

#ifndef ONLINE_JUDGE
#define debug(...) cerr<<format(__VA_ARGS__)
#define debugln(...) cerr<<format(__VA_ARGS__)<<endl
#else
#define debug(...) cerr
#define debugln(...) cerr
#endif

template<class T>
uintptr_t flat(T* b){
    return reinterpret_cast<uintptr_t>(b);
}
template<class T>
auto index(const T a[],uintptr_t p)->decltype(ENABLEN(T,Array),tuple<int>()){
    return (p-flat(&a[0]))/sizeof(T);
}
template<class T>
auto index(const T a[],uintptr_t p)->decltype(ENABLE(T,Array),
    tuple_cat(tuple<int>(),index(a[0],p))){
    int i=(p-flat(a))/sizeof(a[0]);
    p-=i*sizeof(a[0]);
    return tuple_cat(tuple<int>(i),index(a[0],p));
}

template<class T,class ...Args>
struct Rtar{
    T& a;tuple<Args...> n;
    Rtar(T& a,tuple<Args...> n):a(a),n(n){}
};
template<class T,class ...Args>
Rtar<T,Args&...> rtar(T &a,Args&... rest){
    return Rtar<T,Args&...>(a,tie(rest...));
}
template<size_t i,class U,class ...Args,class T=tuple<Args&...>>
auto operator>>(istream& is,Rtar<U,Args&...> r)->decltype(END_TUPLE,is){
    return is>>r.a;
}
template<size_t i=0,class U,class ...Args,class T=tuple<Args&...>>
auto operator>>(istream& is,Rtar<U,Args&...> r)->decltype(FOR_TUPLE,is){
    r.a=typename decay<U>::type(get<i>(r.n));
    for (auto &w:r.a)
        operator>> <i+1>(is,Rtar<decltype(w),Args&...>(w,r.n));
    return is;
}
template<class T1,class T2>
bool cmin(T1 &a,const T2 b){return a>b?a=b,1:0;}
template<class T1,class T2>
bool cmax(T1 &a,const T2 b){return a<b?a=b,1:0;}
template<class T1,class T2,class ...T3>
bool cmin(T1 &a,const T2 b,const T3 ...rest){return cmin(a,b)|cmin(a,rest...);}
template<class T1,class T2,class ...T3>
bool cmax(T1 &a,const T2 b,const T3 ...rest){return cmax(a,b)|cmax(a,rest...);}

bool MULTIDATA=true;

int n;

#define ATL_MATH
constexpr ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
constexpr ll lcm(ll a,ll b){return a*b/gcd(a,b);}
template<class T>
T power(T a,size_t b,const T &unit=1){
    if (b==0) return unit;
    if (b&1) return a*power(a*a,b>>1,unit);
    return power(a*a,b>>1,unit);
}
constexpr ll ceildiv(const ll a,const ll b){return a/b+(a%b?1:0);}
tuple<ll,ll,ll> exgcd(ll a,ll b){//a1+b2=gcd(a,b)
    if (b==0) return make_tuple(a,1,0);
    ll g,x,y;
    tie(g,x,y)=exgcd(b,a%b);
    return make_tuple(g,y,x-a/b*y);
}
tuple<ll,ll,ll> Fexgcd(ll a,ll b){//a1+b2=gcd(a,b),ensure 1>0
    auto k=exgcd(a,b);
    if (get<1>(k)<0) {
        get<1>(k)+=b;
        get<2>(k)-=a;
    }
    return k;
}

#ifndef __OP__
#define __OP__
#define def_op(op)\
this_type operator op (const this_type& a)const{this_type k(*this);k op##=a;return k;}
#define def_cmp(op,n2)\
bool operator op (const this_type& a)const{return n2 op a.n2;}
#define def_all_cmp(n2)\
def_cmp(<,n2) def_cmp(>,n2) def_cmp(<=,n2) \
def_cmp(>=,n2) def_cmp(!=,n2) def_cmp(==,n2)
#endif
template<class T,class uT,ll mod>
struct _mint{
    using this_type=_mint;
    T v;
    _mint()=default;
    template<class iT>
    _mint(const iT& a){v=a%mod;v+=v<0?mod:0;}
    _mint& operator+=(const _mint& a){return (v+=a.v)>=mod&&(v-=mod),*this;}
    _mint& operator-=(const _mint& a){return (v-=a.v)<0&&(v+=mod),*this;}
    _mint& operator*=(const _mint& a){return (v=((uT)v*a.v)%mod),*this;}
    def_op(+) def_op(-) def_op(*)
    def_all_cmp(v)
    #ifdef ATL_MATH
    _mint inverse()const{return power(*this,mod-2);}
    _mint& operator/=(const _mint& a){return (*this)*=a.inverse(),*this;}
    def_op(/)
    #endif
};
template<class T,class uT,ll mod>
ostream& operator<<(ostream& os,const _mint<T,uT,mod>& a){return os<<a.v;}
template<class T,class uT,ll mod>
istream& operator>>(istream& os,_mint<T,uT,mod>& a){T k;os>>k;a=_mint<T,uT,mod>(k);return os;}
using mint=_mint<int,long long,998244353>;
using mll=_mint<long long,__int128,998244353>;

template<class T>
struct ntt{
    int size,l,n;
    vector<int> r;
    const int mod{998244353};
    const array<const T,2> P{3,332748118};
    array<vector<T>,2> W;
    int floorintlog2(int i){
        int k=0;
        while (i) i>>=1,k++;
        return k;
    }
    ntt(int size):size(size){
        l=floorintlog2(size);
        n=1<<l;
        r.resize(n,0);
        W.fill(vector<T>(n));
        for (int i=0;i<n;i++)
            r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
        for (int type:{0,1})
            for (int i=0;i<l;i++)
                W[type][i]=power(P[type],(mod-1)/(1<<i<<1));
    }
    template<int type,class U>
    valarray<T> _NTT(const U& B)const{
        valarray<T> A(n);
        copy(std::begin(B),std::end(B),begin(A));
        for (int i=0;i<n;i++) 
            if(i<r[i]) swap(A[i],A[r[i]]);
        for (int mid=1,midj=0;mid<n;mid<<=1,midj++){
            T Wn=W[type][midj];
            for (int R=mid<<1,j=0;j<n;j+=R){
                T w=1;
                for (int k=0;k<mid;k++,w*=Wn){
                    const T x=A[j+k],y=w*A[j+mid+k];
                    A[j+k]=x+y;
                    A[j+mid+k]=x-y;
                }
            }
        }
        if (type) A*=power(T(n),mod-2);
        return A;
    }
    template<class U>
    valarray<T> NTT(const U& A)const{return _NTT<0>(A);}
    valarray<T> DNT(const valarray<T>& A)const{return _NTT<1>(A);}
};
mint P[1000000+10];
mint C(int n,int k){
  if (n<0||k>n) return 0;
  return P[n]/P[n-k]/P[k];
}
int main(){
  cin>>n;
  ntt<mint> t(2*n+2);
  vec<mint> a(n+1),b(n+1);
  P[0]=1;
  for (int i=1;i<=1000000;i++) P[i]=P[i-1]*i;
  for (int i=0;i<=n;i++){
    int k=n-i;
    a[i]=C(n-2*k,k)*(n-3*k<0?0:power(mint(26),n-3*k))*P[k];
    //cerr<<C(n-2*k,k)*power(mint(26),n-3*k)*P[k]<<endl;
    b[i]=mint(1)/P[i];
    if (i%2==1) b[i]*=-1;
  }
  auto c=t.DNT(t.NTT(a)*t.NTT(b));
//  print("{{} }\n{{} }\n",a,b);
//  for (int i=0;i<=n;i++) cout<<c[i]<<" ";cout<<endl;
  for (int i=n;i>=0;i--){
    cout << c[i]/P[n-i] << " ";
  }
}

I:let fat tension

z3475

标签

数学;矩阵

题意

有n个人，每一个人有能力向量和技能向量。现在组织一场互相学习，每个人都能获得新的技能向量。

求所有

思路

考虑矩阵乘法的定义

即是的形式，考虑使用矩阵乘法化简计算。

最终答案就是

如果矩阵乘法两参数大小为则时间复杂度为。矩阵越小越快。发现和都太大，考虑首先计算。最终时间复杂度为。

参考代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
#include <bits/stdc++.h>
using namespace std;
struct FAST_IO{
    FAST_IO(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    }
}__fast_io;
#if __cplusplus < 201402L
template<class T, class U=T>
T exchange(T& obj, U&& new_value){
    T old_value=move(obj);
    obj=forward<U>(new_value);
    return old_value;
}
#endif
#define cons(a,...) a=typename decay<decltype(a)>::type(__VA_ARGS__)
using INT=int;
#define DEF_NUM(num) \
using i##num=int##num##_t;using u##num=uint##num##_t;
DEF_NUM(8)DEF_NUM(16)DEF_NUM(32)DEF_NUM(64)
using i128=__int128;using u128=unsigned __int128;
using usize=uintptr_t;using isize=intptr_t;
using f32=float;using f64=double;using f128=long double;
#define x first
#define y second
//#define int long long
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
auto &_=std::ignore;
using ll=long long;
template<class T>
using vec=vector<T>;
template<bool B,class T=void>
using enableif_t=typename enable_if<B,T>::type;

#define DEF_COULD(name,exp) \
template<class U> \
struct name{\
    template<class T>\
    constexpr static auto is(int i)->decltype(exp,true){return true;}\
    template<class T>\
    constexpr static bool is(...){return false;}\
    static const bool value=is<U>(1);\
};
#define DEF_CAN(name,exp) DEF_COULD(can##name,exp)
#define ENABLE(T,name) enableif_t<can##name<T>::value>(1)
#define ENABLEN(T,name) enableif_t<!can##name<T>::value>(1)
#define FOR_TUPLE enableif_t<i!=tuple_size<T>::value>(1)
#define END_TUPLE enableif_t<i==tuple_size<T>::value>(1)
#define FOR_TUPLET(T) enableif_t<i!=tuple_size<T>::value>(1)
#define END_TUPLET(T) enableif_t<i==tuple_size<T>::value>(1)

#define DEF_INF(name,exp)\
constexpr struct{\
    template<class T>\
    constexpr operator T()const {return numeric_limits<T>::exp();}\
} name;

DEF_CAN(Out,(cout<<*(T*)(0))) DEF_CAN(For,begin(*(T*)(0)))
DEF_INF(INF,max) DEF_INF(MINF,min)
DEF_CAN(Array,declval<T>()[0])

template<size_t i,class T>
auto operator>>(istream& is,T &r)->decltype(END_TUPLE,is){
    return is;
}
template<size_t i=0,class T>
auto operator>>(istream& is,T &r)->decltype(FOR_TUPLE,is){
    is>>get<i>(r);
    return operator>> <i+1>(is,r);
}

template<size_t i,class ...Args>
auto operator>>(istream& is,const tuple<Args&...> &r)->decltype(END_TUPLET(tuple<Args&...>),is){
    return is;
}
template<size_t i=0,class ...Args>
auto operator>>(istream& is,const tuple<Args&...> &r)->decltype(FOR_TUPLET(tuple<Args&...>),is){
    is>>get<i>(r);
    return operator>> <i+1>(is,r);
}

template<class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLE(T,Out),c+1);
template<size_t i,class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLEN(T,For),END_TUPLE,c+1);
template<size_t i=0,class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLEN(T,For),FOR_TUPLE,c+1);
template<class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLEN(T,Out),ENABLE(T,For),c+1);


template<class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLE(T,Out),c+1){
    os << cv;
    while (*c!='}') c++;
    return c+1;
}
template<size_t i,class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLEN(T,For),END_TUPLE,c+1){
    return c;
}
template<size_t i,class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLEN(T,For),FOR_TUPLE,c+1){
    while (*c!='{') os << *c++;
    c=__format(os,c,get<i>(cv));
    return __format<i+1>(os,c,cv);
}
template<class T>
auto __format(ostream &os,const char *c,const T& cv)->decltype(ENABLEN(T,Out),ENABLE(T,For),c+1){
    const char *ct=c+1;
    if (cv.size()==0){
        int b=1;
        while (1){
            if (*ct=='}') b--;
            if (*ct=='{') b++;
            if (!b) break;
            ct++;
        }
    }else{
        for (auto &i:cv){
            const char *cc=c+1;
            while (*cc!='{') os << *cc++;
            cc=__format(os,cc,i);
            while (*cc!='}') os << *cc++;
            ct=cc;
        }
    }
    return ct+1;
}
void _format(ostream &os,const char *c){
    while (*c!='{'&&*c!='\0') os<< *c++;
}
template<class T,class ...Args>
void _format(ostream &os,const char *c,const T &a,const Args& ...rest){
    while (*c!='{'&&*c!='\0') os<< *c++;
    if (*c=='{') c=__format(os,c,a);
    _format(os,c,rest...);
}
template<class ...Args>
string format(const char *c,const Args& ...rest){
    ostringstream os;
    _format(os,c,rest...);
    return os.str();
}
template<class ...Args>
ostream& print(const char *c,const Args& ...rest){return _format(cout,c,rest...),cout;}
template<class ...Args>
ostream& println(const char *c,const Args& ...rest){return print(c,rest...)<<endl;}

#ifndef ONLINE_JUDGE
#define debug(...) cerr<<format(__VA_ARGS__)
#define debugln(...) cerr<<format(__VA_ARGS__)<<endl
#else
#define debug(...) cerr
#define debugln(...) cerr
#endif

template<class T>
uintptr_t flat(T* b){
    return reinterpret_cast<uintptr_t>(b);
}
template<class T>
auto index(const T a[],uintptr_t p)->decltype(ENABLEN(T,Array),tuple<int>()){
    return (p-flat(&a[0]))/sizeof(T);
}
template<class T>
auto index(const T a[],uintptr_t p)->decltype(ENABLE(T,Array),
    tuple_cat(tuple<int>(),index(a[0],p))){
    int i=(p-flat(a))/sizeof(a[0]);
    p-=i*sizeof(a[0]);
    return tuple_cat(tuple<int>(i),index(a[0],p));
}

template<class T,class ...Args>
struct Rtar{
    T& a;tuple<Args...> n;
    Rtar(T& a,tuple<Args...> n):a(a),n(n){}
};
template<class T,class ...Args>
Rtar<T,Args&...> rtar(T &a,Args&... rest){
    return Rtar<T,Args&...>(a,tie(rest...));
}
template<size_t i,class U,class ...Args,class T=tuple<Args&...>>
auto operator>>(istream& is,Rtar<U,Args&...> r)->decltype(END_TUPLE,is){
    return is>>r.a;
}
template<size_t i=0,class U,class ...Args,class T=tuple<Args&...>>
auto operator>>(istream& is,Rtar<U,Args&...> r)->decltype(FOR_TUPLE,is){
    r.a=typename decay<U>::type(get<i>(r.n));
    for (auto &w:r.a)
        operator>> <i+1>(is,Rtar<decltype(w),Args&...>(w,r.n));
    return is;
}
template<class T1,class T2>
bool cmin(T1 &a,const T2 b){return a>b?a=b,1:0;}
template<class T1,class T2>
bool cmax(T1 &a,const T2 b){return a<b?a=b,1:0;}
template<class T1,class T2,class ...T3>
bool cmin(T1 &a,const T2 b,const T3 ...rest){return cmin(a,b)|cmin(a,rest...);}
template<class T1,class T2,class ...T3>
bool cmax(T1 &a,const T2 b,const T3 ...rest){return cmax(a,b)|cmax(a,rest...);}

bool MULTIDATA=true;


#define for_n(i,n,exp) for (int i=0;i<n;i++) exp;
template<class T>
struct dmat:public vector<T>{
    int n,m;
    dmat(int n,int m):n(n),m(m),vector<T>(n*m,0){}
    dmat(int n,int m,initializer_list<T> a):n(n),m(m),vector<T>(a){}
    T* operator[](int i){return &vector<T>::operator[](i*m);}
    const T* operator[](int i)const{return &vector<T>::operator[](i*m);}
    dmat operator*(const dmat<T> &b)const{
        auto& a=(*this);
        dmat<T> x(a.n,b.m);
        for (int i=0;i<a.n;i++)
            for (int j=0;j<b.m;j++)
                for (int k=0;k<a.m;k++)
                    x[i][j]+=a[i][k]*b[k][j];
        return x;
    }
    dmat operator*=(const dmat<T> &b){return (*this)=(*this)*b;}
    static dmat<T> unit(int n,int m){
        dmat<T> x(n,m);
        for (int i=0;i<n;i++) x[i][i]=1;
        return x;
    }
};
double q2(double x){return x*x;}
int main(){
  int n,k,d;
  cin>>n>>k>>d;
  dmat<double> X(n,k),Y(n,d),XT(k,n);
  for (int i=0;i<n;i++){
    double x=0;
    for (int j=0;j<k;j++){
      cin>>X[i][j];
      x+=q2(X[i][j]);
    }
    x=sqrt(x);
    for (int j=0;j<k;j++){
      XT[j][i]=X[i][j]/=x;
    }
  }

  for (int i=0;i<n;i++)
    for (int j=0;j<d;j++)
      cin>>Y[i][j];
  auto a=X*(XT*Y);
  cout<<fixed<<setprecision(8);
  for (int i=0;i<n;i++){
    for (int j=0;j<d;j++)
      cout<<a[i][j]<<" ";
    cout<<endl;
  }
}

H:Take the Elevator

LyFive

标签

贪心;模拟

题意

现在有k个人准备坐电梯，但电梯相同时刻只能容纳人并且只能从第一层到达某层，再从某层回到第一层。上升/下降速度为1层/单位时长，现求把k个人都送到目的位置花费多少单位时长。

思路

考虑电梯的行动轨迹，不难发现电梯接送的时候应该尽可能先把未被接送的最高层人接送完成，这样整体花费的时间最少。 首先把需要接送的人分为上升和下降人群，在每一轮上升下降过程优先接送可能到达的最高层，每轮次的时间消耗为。不断模拟轮次删除即可算出答案。 考虑模拟过程中，维护电梯人数状态，为了方便考虑我们可以把上升人群由直接转换成下降情况同类进行考虑。 设正在电梯的人的集合为，电梯人群目标下降的最高楼层为。 首先，对不同人群按照第一关键字排序，每轮比较上升人群和下降人群最大的更新。然后每一轮分开维护上升和下降的电梯状态，每次有人需要上电梯时检查电梯是否满员，即集合大小或，若后者满足则表示下降过程有人出了电梯并删除加入继续维护电梯状态。最终，上升和下降人群全部接送完毕即可。

参考代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define x first
#define y second

int t, n, m, x, y, k;

multiset<pair<int, int>> up;
multiset<pair<int, int>> dn;

void init()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
}

void f(multiset<pair<int, int>> &dn)
{
    if (dn.empty())
        return;
    vector<pair<int, int>> v;
    multiset<int> vi;
    for (auto x = dn.rbegin(); x != dn.rend(); x++)
    {
        if (vi.size() < m)
        {
            v.push_back(*x);
            vi.insert(x->y);
        }
        else if (x->x <= *vi.rbegin())
        {
            auto it = vi.end();
            it--;
            vi.erase(it);
            vi.insert(x->y);
            v.push_back(*x);
        }
    }
    for (auto x : v)
    {
        dn.erase(dn.lower_bound(x));
    }
}
void solve()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> x >> y;
        if (x < y)
            up.insert({y, x});
        else
            dn.insert({x, y});
    }
    LL ans = 0;
    while (up.size() || dn.size())
    {
        LL ux = 0;
        LL dx = 0;
        if (up.size())
            ux = up.rbegin()->x;
        if (dn.size())
            dx = dn.rbegin()->x;
        LL mx = max(ux, dx);
        f(dn);
        f(up);
        ans += 2 * mx - 2;
    }
    cout << ans << "\n";
}

int main()
{
    init();
    solve();
}

LyFive

标签

dp;dp空间优化

题意

某个游戏有n个世界，每个世界都是一张有向图。玩家起始在首个世界的1号节点，每次可以选择不动或移动一步，随后穿梭到下一个世界的当前节点。当穿梭所有世界结束后，到达节点则游戏胜利。现在作者想从n个世界中选择最小的连续的世界作为这个游戏的某个关卡，要求至少存在一种获胜方案，求连续的世界集合最小的大小。

思路

由于世界是连续穿梭，且每个世界只能走0/1步。不难发现后面出现的世界是对前面的扩展，即枚举前置世界的情况无后效性。为此考虑要求集合最小，则每次加入一个新的世界找到所需最近的世界。定义状态为只使用前个世界以其为起点能够到达节点编号最大的世界。不难发现，对于第个世界若存在的路径则,若存在的路径，则。同时状态第一维可以用滚动数组优化。最终输出即可。

参考代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL N = 1e4 + 2;
const LL M = 2000 + 100;

int n, m, l, x, y;
int dp[2][M];

void init()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
}

void solve()
{
    cin >> n >> m;
    int ans = N;

    for (int i = 1; i <= n; i++)
    {
        cin >> l;
        for (int j = 0; j <= m; j++)
            dp[i % 2][j] = dp[(i - 1) % 2][j];
        for (int j = 0; j < l; j++)
        {
            cin >> x >> y;
            if (x == 1)
            {
                dp[i % 2][y] = i;
            }
            dp[i % 2][y] = max(dp[(i - 1) % 2][x], dp[i % 2][y]);
        }
        if (dp[i % 2][m])
            ans = min(ans, i - dp[i % 2][m] + 1);
    }

    if (ans == N)
        ans = -1;
    cout << ans << "\n";
}

int main()
{
    init();
    solve();
}
build本页面最近更新：2022/7/29 01:37:28，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：Ir1d
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论