#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.0625,prior=0.75; const float table[4]={3,4,0.5,15.0}; struct naivebayes{ signed cnt[langs][buckets][4]; signed total[langs][4]; void train(signed *E, int L){ for(int i = 0; i < 100; i++){ int h=0; for(int j = 0; j < max_ngrams; j++){ if(i+j>=100)break; h=(h*283+E[i+j])&(buckets-1); cnt[L][h][j]++; total[L][j]++; } } } 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]+total[i][2]+total[i][3]; for(int L = 0; L < langs; L++){ float prob=log((total[L][0]+total[L][1]+total[L][2]+total[L][3]+prior)/(sum+prior*langs)); for(int i = 0; i < 100; i++){ int h=0; for(int j = 0; j < max_ngrams; j++){ if(i+j>=100)break; h=(h*283+E[i+j])&(buckets-1); prob+=table[j]*log((cnt[L][h][j]+smooth)/(total[L][j]+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); }