#include #include #include #include #include using namespace std; using ll=long long; using pcpi=pair; vector s; vector lcp; vector idx; vector > dp; void swap(int& a, int& b) { int c; c=a; a=b; b=c; } int calc_lcp(const pcpi& a, const pcpi& b) { int k; const char *p, *q; p=a.first; q=b.first; int idx1, idx2; if(a.second>b.second) { idx1=a.second; idx2=b.second; } else { idx1=b.second; idx2=a.second; } if(dp[idx1].size()>idx2 && dp[idx1][idx2]>=0) return dp[idx1][idx2]; for(k=0;p[k] && p[k]==q[k];k++) ; return k; } bool cmp(const pcpi& a, const pcpi& b) { int k; const char *p, *q; p=a.first; q=b.first; for(k=0;p[k] && p[k]==q[k];k++) ; int idx1, idx2; if(a.second>b.second) { idx1=a.second; idx2=b.second; } else { idx1=b.second; idx2=a.second; } if(dp[idx1].size()<=idx2) dp[idx1].resize(idx2+1, -1); dp[idx1][idx2]=k; return p[k]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) { dp.clear(); dp.resize(n); 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; }