#include #include #include #include #include using namespace std; using ll=long long; using pcpi=pair; vector s; vector lcp; vector idx; void swap(int& a, int& b) { int c; c=a; a=b; b=c; } int calc_lcp(const char *p, const char *q) { int k; for(k=0;p[k] && p[k]==q[k];k++) ; return k; } bool cmp(const pcpi& a, const pcpi& b) { return (strcmp(a.first, b.first)<0); } void min_u(int& m, int v) { if(m>v) m=v; } int get_lcp(int i, int j) { int idx1=idx[i]; int idx2=idx[j]; if(idx1>idx2) swap(idx1, idx2); int ret=lcp[idx1]; for(int i=idx1+1;i buf; char *p; int i, j, k, m; ll x, result, n, d; while(scanf("%lld", &n)==1) { s.resize(n); lcp.resize(n); idx.resize(n); buf.resize(800000+100000); p=&buf[0]; for(i=0;ij) swap(i, j); else j++; x=(x+d)%(n*(n-1)); result+=get_lcp(i-1, j-1); // printf("k=%d x=%d i=%d j=%d %lld\n", k, x, i, j, result); } printf("%lld\n", result); } return 0; }