#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<<20,max_ngrams=4; const float smooth=0.5,prior=1.0; struct naivebayes{ unsigned short cnt[langs][buckets][2]; signed total[langs][2]; void train(signed *E, int L){ for(int i = 0; i+max_ngrams <= 100; i++){ int h=0; for(int j = 0; j < max_ngrams-1; j++){ h=(h*263+E[i+j])%buckets; } cnt[L][h][0]++; h=(h*263+E[i+max_ngrams-1])%buckets; cnt[L][h][1]++; total[L][0]++; total[L][1]++; } } 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 <= 100; i++){ int h=0; for(int j = 0; j < max_ngrams-1; j++){ h=(h*263+E[i+j])&(buckets-1); } prob+=log((cnt[L][h][0]+smooth)/(total[L][0]+smooth*buckets)); h=(h*263+E[i+max_ngrams-1])%buckets; prob+=log((cnt[L][h][1]+smooth)/(total[L][1]+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); }