#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include "grader.h" #include "lang.h" #define int long long using namespace std; const int langs=56,buckets=1<<18,max_ngrams=4; const float smooth=0.08,prior=1.0; struct naivebayes{ signed cnt3[langs][buckets],cnt4[langs][buckets],cnt5[langs][buckets]; signed total[langs][2]; void train(signed *E, int L){ for(int i = 0; i+max_ngrams <= 102; i++){ int h=0; for(int j = 0; j < max_ngrams-2; j++){ h=(h*283+E[i+j])&(buckets-1); } cnt3[L][h]++; h=(h*283+E[i+max_ngrams-2])&(buckets-1); cnt4[L][h]++; h=(h*283+E[i+max_ngrams-1])&(buckets-1); cnt5[L][h]++; } } signed predict(signed *E){ float best=-1e300; int blang=0,sum=0; for(int i = 0; i < langs; i++)sum+=total[i][0]+total[i][1]; for(int L = 0; L < langs; L++){ float prob=log((total[L][0]+total[L][1]+prior)/(sum+prior*langs)); for(int i = 0; i+max_ngrams <= 102; i++){ int h=0; for(int j = 0; j < max_ngrams-2; j++){ h=(h*283+E[i+j])&(buckets-1); } prob+=5*log((cnt3[L][h]+smooth)/(total[L][0]+smooth*buckets)); h=(h*283+E[i+max_ngrams-2])&(buckets-1); prob+=log((cnt4[L][h]+smooth)/(total[L][0]+smooth*buckets)); h=(h*283+E[i+max_ngrams-1])&(buckets-1); prob+=10*log((cnt5[L][h]+smooth)/(total[L][0]+smooth*buckets)); } if(prob>=best){ best=prob; blang=L; } } return blang; } }NB; void excerpt(signed *E){ int qu=language(NB.predict(E)); NB.train(E,qu); }