#include #include #include #include #include #include #include using namespace std; using ll=long long; using pcpi=pair; using vmii=vector >; vector s; vmii dp; void swap(int& a, int& b) { int c; c=a; a=b; b=c; } int lcp(const char* p, const char* q) { int i; for(i=0;p[i];i++) { if(p[i]!=q[i]) break; } return i; } void min_u(int& m, int v) { if(m>v) m=v; } int get_lcp(int i, int j) { swap(i, j); if(dp[i].find(j)!=dp[i].end()) return dp[i][j]; return dp[i][j]=lcp(s[i], s[j]); } int main(void) { vector buf; int i, j, k, m; ll x, result, n, d; char *p; while(scanf("%lld", &n)==1) { dp.clear(); dp.resize(n); s.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; }