#include #include #include using namespace std; using ll=long long; vector s; vector > dp; void swap(int& a, int& b) { int c; c=a; a=b; b=c; } int lcp(int i, int j) { if(i=dp[i].size()) dp[i].resize(j+1, -1); else if(dp[i][j]>=0) return dp[i][j]; char *p, *q; int k; p=s[i]; q=s[j]; for(k=0;p[k] && p[k]==q[k];k++) ; return dp[i][j]=k; } int main(void) { vector buf; char *p; int i, j, k, n, m, d; ll x, result; while(scanf("%d", &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)%((ll)n*(n-1)); result+=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); /* for(auto x: dp) { for(auto y: x) printf("%2d ", y); printf("\n"); } */ } return 0; }