oj.uz

Submission #502376

# Submission time Handle Problem Language Result Execution time Memory
502376 2022-01-05T20:43:05 Z inksamurai Trener (COCI20_trener) C++17
110 / 110
 754 ms 2452 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3qplfh5 ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;

void print(){
	cout<<"\n";
}
template<class te,class ...ti>
void print(const te&v, const ti&...nv) { 
	cout<<v;
	if(sizeof...(nv)){
		cout<<" ";
		print(nv...);
	}
}

using pii=pair<int,int>;
using vi=vector<int>;
using vll=vector<long long>;

//snuke's mod int
template <ll mod>
struct modint{
  ll x; // typedef long long ll;
  modint(ll x=0):x((x%mod+mod)%mod){}
  modint operator-()const{ return modint(-x);}
  modint& operator+=(const modint a){ if((x+=a.x)>=mod) x-=mod; return *this; }
  modint& operator-=(const modint a){ if((x+=mod-a.x)>=mod) x-=mod; return *this; }
  modint& operator*=(const modint a){ (x*=a.x)%=mod; return *this; }
  modint operator+(const modint a)const{ modint res(*this); return res+=a; }
  modint operator-(const modint a)const{ modint res(*this); return res-=a; }
  modint operator*(const modint a)const{ modint res(*this); return res*=a; }
  modint pow(ll n) const {
    modint res=1,x(*this);
    while(n){
        if(n&1)res*=x;
        x*=x;
        n>>=1;
    }
    return res;
  }
  modint inv() const { return pow(mod-2); }
};
using mint=modint<1000000007>;

// include mint here
using hshmint=modint<1000000007>;
using hshmint1=modint<998244353>;
using magicpair = pair<hshmint,hshmint1>;
struct rollhsh{	
	hshmint _p=9973; // base
	hshmint1 _p1=257; // base1
	vec(hshmint) pw,invpw;
	vec(hshmint1) pw1,invpw1;
	vec(magicpair) hsh;
	rollhsh(string s=""){
		init(s);
	}
	void init(string s){
		hsh.clear();
		pw.clear();
		invpw.clear();
		pw1.clear();
		invpw1.clear();
		hsh.resize(sz(s)+1);
		pw.resize(sz(s)+1);
		invpw.resize(sz(s)+1);
		pw1.resize(sz(s)+1);
		invpw1.resize(sz(s)+1);
		hsh[0]={1,1};
		pw[0]=1;
		pw1[0]=1;
		invpw[0]=1;
		invpw1[0]=1;		
		hshmint _invbase=_p.x;
		hshmint1 _invbase1=_p1.x;
		_invbase=_invbase.inv(); _invbase1=_invbase1.inv();
		rep(i,sz(s)){
			pw[i+1]=pw[i]*_p;
			pw1[i+1]=pw1[i]*_p1;
			invpw[i+1]=invpw[i]*_invbase;
			invpw1[i+1]=invpw1[i]*_invbase1;
			hshmint x=(int)(s[i]-'a'+1);
			hshmint1 x1=(int)(s[i]-'a'+1);
			hsh[i+1]={hsh[i].fi+pw[i]*x,hsh[i].se+pw1[i]*x1};
		}
	}
	pair<ll,ll> get(int l,int r){ 
		// from - to , inclusive
		hshmint _f=invpw[l]*(hsh[r+1].fi-hsh[l].fi);
		hshmint1 _s=invpw1[l]*(hsh[r+1].se-hsh[l].se);
		return {_f.x,_s.x};	
	}
};

using pll=pair<ll,ll>;

void slv(){
	int n,m;
	cin>>n>>m;
	vec(mint) dp(m),nedp;
	vec(pll) rbts,nerbts;
	rollhsh hsh;
	rep(i,n){
		nerbts={};
		nedp=vec(mint)(m,0);
		rep(j,m){
			string s;
			cin>>s;
			hsh.init(s);
			nerbts.pb(hsh.get(0,i));
			if(!i){
				nedp[j]=1;
			}else{
				rep(j1,m){
					if(rbts[j1]==hsh.get(0,i-1) or rbts[j1]==hsh.get(1,i)){
						nedp[j]+=dp[j1];
					}
				}
			}
		}
		swap(dp,nedp);
		swap(rbts,nerbts);
	}
	mint ans=0;
	rep(j,m)
		ans+=dp[j];
	print(ans.x,'\n');
}

int main(){
_3qplfh5;
	int t=1;
	// cin>>t;
	rep(cs,t)
		slv();
//	
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 444 KB Output is correct
2 Correct 8 ms 460 KB Output is correct
3 Correct 7 ms 460 KB Output is correct
4 Correct 10 ms 456 KB Output is correct
5 Correct 8 ms 484 KB Output is correct
6 Correct 8 ms 460 KB Output is correct
7 Correct 8 ms 460 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 9 ms 444 KB Output is correct
6 Correct 8 ms 460 KB Output is correct
7 Correct 7 ms 460 KB Output is correct
8 Correct 10 ms 456 KB Output is correct
9 Correct 8 ms 484 KB Output is correct
10 Correct 8 ms 460 KB Output is correct
11 Correct 8 ms 460 KB Output is correct
12 Correct 746 ms 2392 KB Output is correct
13 Correct 750 ms 2380 KB Output is correct
14 Correct 754 ms 2324 KB Output is correct
15 Correct 709 ms 2328 KB Output is correct
16 Correct 697 ms 2328 KB Output is correct
17 Correct 743 ms 2340 KB Output is correct
18 Correct 745 ms 2328 KB Output is correct
19 Correct 751 ms 2332 KB Output is correct
20 Correct 733 ms 2384 KB Output is correct
21 Correct 731 ms 2452 KB Output is correct
22 Correct 730 ms 2332 KB Output is correct