結果
問題 | No.1204 お菓子配り-FINAL |
ユーザー |
![]() |
提出日時 | 2020-08-27 18:46:26 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,557 ms / 8,000 ms |
コード長 | 9,726 bytes |
コンパイル時間 | 29,134 ms |
コンパイル使用メモリ | 448,396 KB |
最終ジャッジ日時 | 2025-01-13 15:28:48 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 130 |
ソースコード
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC push_options #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #include<bits/stdc++.h> #include <xmmintrin.h> #include <immintrin.h> using namespace::std; __attribute__((constructor))void init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);} #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/priority_queue.hpp> #include<ext/pb_ds/tag_and_trait.hpp> // #include <boost/multiprecision/cpp_dec_float.hpp> // #include <boost/multiprecision/cpp_int.hpp> // namespace mp = boost::multiprecision; // typedef mp::number<mp::cpp_dec_float<0>> cdouble; // typedef mp::cpp_int cint; template<typename T>using pbds=__gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; template<typename T>using pbds_map=__gnu_pbds::tree<T,T,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; template<typename T,typename E>using hash_map=__gnu_pbds::gp_hash_table<T,E>; template<typename T>using pqueue =__gnu_pbds::priority_queue<T, greater<T>,__gnu_pbds::rc_binomial_heap_tag>; typedef long long lint; #define INF (1LL<<60) #define IINF (1<<30) #define LINF (9223372036854775807LL) #define EPS (1e-10) #define endl ('\n') #define MOD 1000000007LL //#define MOD 998244353LL //#define MOD 18446744069414584321ULL typedef vector<lint> vec; typedef vector<vector<lint>> mat; typedef vector<vector<vector<lint>>> mat3; typedef vector<string> svec; typedef vector<vector<string>> smat; template<typename T>inline void numout(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i<INF/2?i:"INF";f=1;}cout<<endl;} template<typename T>inline void numout2(T t){for(auto i:t)numout(i);} template<typename T>inline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i;f=1;}cout<<endl;} template<typename T>inline void output2(T t){for(auto i:t)output(i);} template<typename T>inline void _output(T t){bool f=0;for(lint i=0;i<t.size();i++){cout<<f?"":" "<<t[i];f=1;}cout<<endl;} template<typename T>inline void _output2(T t){for(lint i=0;i<t.size();i++)output(t[i]);} #define rep(i,...) for(auto i:range(__VA_ARGS__)) #define rrep(i,...) for(auto i:reversed(range(__VA_ARGS__))) #define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i) #define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i) #define irep(i) for(lint i=0;;++i) inline vector<int64_t> range(int64_t n){vector<int64_t>v(n);iota(v.begin(),v.end(),0LL);return v;} inline vector<int64_t> range(int64_t a,int64_t b){vector<int64_t>v(b-a);iota(v.begin(),v.end(),a);return v;} inline vector<int64_t> range(int64_t a,int64_t b,int64_t c){vector<int64_t>v((b-a+c-1)/c);for(int i=0;i<(int)v.size();++i)v[i]=i?v[i-1]+c:a;return v;} inline auto reversed(auto v){reverse(v.begin(),v.end());return v;} #define all(n) begin(n),end(n) #define dist(a,b,c,d) sqrt(pow(a-c,2)+pow(b-d,2)) //inline lint gcd(lint A,lint B){return B?gcd(B,A%B):A;} //inline lint lcm(lint A,lint B){return A/gcd(A,B)*B;} // inline cint cgcd(cint A,cint B){return B?cgcd(B,A%B):A;} // inline cint clcm(cint A,cint B){return A/cgcd(A,B)*B;} bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;} bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;} const vector<lint> dx={1,0,-1,0,1,1,-1,-1}; const vector<lint> dy={0,1,0,-1,1,-1,1,-1}; #define SUM(v) accumulate(all(v),0LL) auto call=[](auto f,auto... args){return f(f,args...);}; template<typename T,typename ...Args>auto make_vector(T x,int arg,Args ...args){if constexpr(sizeof...(args)==0)return vector<T>(arg,x);else return vector(arg,make_vector<T>(x,args...));} class mint { using u64 = std::uint_fast64_t; public: u64 a; constexpr mint(const long long x = 0)noexcept:a(x>=0?x%get_mod():get_mod()-(-x)%get_mod()){} constexpr u64 &value()noexcept{return a;} constexpr const u64 &value() const noexcept {return a;} constexpr mint operator+(const mint rhs)const noexcept{return mint(*this) += rhs;} constexpr mint operator-(const mint rhs)const noexcept{return mint(*this)-=rhs;} constexpr mint operator*(const mint rhs) const noexcept {return mint(*this) *= rhs;} constexpr mint operator/(const mint rhs) const noexcept {return mint(*this) /= rhs;} constexpr mint &operator+=(const mint rhs) noexcept { a += rhs.a; if (a >= get_mod())a -= get_mod(); return *this; } constexpr mint &operator-=(const mint rhs) noexcept { if (a<rhs.a)a += get_mod(); a -= rhs.a; return *this; } constexpr mint &operator*=(const mint rhs) noexcept { a = a * rhs.a % get_mod(); return *this; } constexpr mint operator++(int n) noexcept { a += 1; if (a >= get_mod())a -= get_mod(); return *this; } constexpr mint operator--(int n) noexcept { if (a<1)a += get_mod(); a -= 1; return *this; } constexpr mint &operator/=(mint rhs) noexcept { u64 exp=get_mod()-2; while (exp) { if (exp % 2) { *this *= rhs; } rhs *= rhs; exp /= 2; } return *this; } constexpr bool operator==(mint x) noexcept { return a==x.a; } constexpr bool operator!=(mint x) noexcept { return a!=x.a; } constexpr bool operator<(mint x) noexcept { return a<x.a; } constexpr bool operator>(mint x) noexcept { return a>x.a; } constexpr bool operator<=(mint x) noexcept { return a<=x.a; } constexpr bool operator>=(mint x) noexcept { return a>=x.a; } constexpr static int root(){ mint root = 2; while(root.pow((get_mod()-1)>>1).a==1)root++; return root.a; } constexpr mint pow(long long n){ long long x=a; mint ret = 1; while(n>0) { if(n&1)(ret*=x); (x*=x)%=get_mod(); n>>=1; } return ret; } constexpr mint inv(){ return pow(get_mod()-2); } static vector<mint> fac,ifac; static bool init; constexpr static int mx=10000001; void build(){ init=0; fac.resize(mx); ifac.resize(mx); fac[0]=1,ifac[0]=1; for(int i=1;i<mx;i++)fac[i]=fac[i-1]*i; ifac[mx-1]=fac[mx-1].inv(); for(int i=mx-2;i>=0;i--)ifac[i]=ifac[i+1]*(i+1); } mint comb(lint b){ if(init)build(); if(a==0&&b==0)return 1; if((lint)a<b||a<0)return 0; return fac[a]*ifac[a-b]*ifac[b]; } mint fact(){ if(init)build(); return fac[a]; } mint fact_inv(){ if(init)build(); return ifac[a]; } friend ostream& operator<<(ostream& lhs, const mint& rhs) noexcept { lhs << rhs.a; return lhs; } friend istream& operator>>(istream& lhs,mint& rhs) noexcept { lhs >> rhs.a; return lhs; } constexpr static u64 get_mod(){return MOD;} }; vector<mint> mint::fac; vector<mint> mint::ifac; bool mint::init=1; constexpr int N=20; mint f(bitset<N>v,const string& s,lint n){ mint ans=0; { for(int i=0;i<n-(int)s.size()+1;++i){ bool b=1; rep(j,s.size()){ if((s[j]=='-')^(v[i+j]))b=0; } if(b)ans+=mint(n).pow(n-v.count()); } } if(int(v.count())==n)return ans; for(int i=0;i<n;++i){ bitset<N>b=v; lint tmp=i; while(b[tmp++%n]); b[(tmp+n-1)%n]=1; ans+=f(b,s,n); } return ans; } int main(){ lint n,m; cin>>n>>m; string s; cin>>s; //cout<<f(bitset<N>(),s,n)<<endl; auto f=[](lint n,lint k)->mint{ n++; if(k==0)return 1; return mint(n-k)*mint(n).pow(k-1); }; if(count(all(s),'o')==0){ mint ans=0; rep(i,n-m+1){ mint tmp=0; tmp+=mint(n).pow(i+m); if(n-m-i>=1){ tmp-=mint(m)*f(n-1,i+m); } if(n-m-i>=2){ for(int j=0;j<=m-2;++j){ tmp+=mint(m-1-j)*f(n-(j+2),i+m-j)*f(j,j)*mint(i+m).comb(j); } } ans+=tmp*(n-m+1)*mint(n).pow(n-m-i); } cout<<ans<<endl; }else{ vec v; lint now=0; rep(i,m){ if(s[i]=='o'){ if(now)v.push_back(now); now=0; }else{ now++; } } lint l=(s[0]=='o'?0:v[0]),r=now; if(s[0]!='o')v.erase(v.begin()); mint tmp=1; lint cnt=0; for(auto e:v){ tmp*=f(e,e); tmp/=mint(e).fact(); cnt+=e; } tmp*=mint(cnt).fact(); mint ans=0; vector<mint>table(max(l+r-1,1LL),0); rep(i,l)rep(j,r){ table[i+j]+=f(i,i)*f(j,j)*mint(i+j).comb(i); } rep(i,n-m+1){ mint tmp2=0; tmp2+=f(n-m+l+r,i+l+r); if(n-m-i>=1){ for(int j=0;j<=l-1;++j){ tmp2-=f((n-m+l+r)-(1+j),(i+l+r)-j)*f(j,j)*mint(i+l+r).comb(j); } for(int j=0;j<=r-1;++j){ tmp2-=f((n-m+l+r)-(1+j),(i+l+r)-j)*f(j,j)*mint(i+l+r).comb(j); } } if(n-m-i>=2){ for(int j=0;j<=l+r-2;++j){ tmp2+=f((n-m+l+r)-(2+j),(i+l+r)-j)*table[j]*mint(i+l+r).comb(j); } } ans+=tmp*tmp2*mint(i+l+r+cnt).comb(cnt)*(n-m+1)*mint(n).pow(n-i-cnt-l-r); } cout<<ans<<endl; } }