#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.0f,5.0f,0.5f,25.0f}; float loglut[1000001]; struct naivebayes{ signed cnt[langs][buckets][4]; signed total[langs][4]; float logden[langs][4]; bool init=0; void train(signed *E, int L){ if(!init){ for(int i = 0; i <= 1000000; i++){ loglut[i]=logf(i+smooth); } for(int i = 0; i < langs; i++){ for(int j = 0; j < 4; j++){ logden[i][j]=logf(smooth*buckets); } } init=1; } 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]++; } } for(int j = 0; j < max_ngrams; j++){ logden[L][j]=logf(total[L][j]+smooth*buckets); } } signed predict(signed *E){ float best=-1e18f; 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=logf((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]*(loglut[cnt[L][h][j]]-logden[L][j]); } } if(prob>=best){ best=prob; blang=L; } } return blang; } }NB; void excerpt(signed *E){ int qu=language(NB.predict(E)); NB.train(E,qu); }