题意：一个圆上有n个等分点，现在从一个点出发，指定k，不停地隔k个点连边（样例请看link），问有多少种不同的方法，使得所有的点都被连起来。两种情况是一样的，当且仅当他们旋转若干角度以后是一样的。
tags：首先要运用一下数论知识，很容易就可以得出只有和n互质的k才是合法的。然后发现，k画出的图可以通过旋转得到n-k的图，而(n,k)=1 <-> (n,n-k)=1，所以答案为(phi(n) + 1)/2。Phi为欧拉函数。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 200005; ll getphi(ll n) { ll ans=n; for(ll i=2; i*i<=n; ++i) if(n%i==0) { ans= ans/i*(i-1); while(n%i==0) n/=i; } if(n>1) ans= ans/n*(n-1); return ans; } int main() { ll n; for(; scanf("%lld", &n)>0; ) { printf("%lld ", getphi(n)/2); } return 0; }
题意：给定n个字符串，统计字符串(s1, s2)的对数，使得s1的字典序比s2的字典序要大，s1反一反（abc->cba，记为s1’）比s2’的字典序要小。
tags：按字符串的字典序排序，从小到大枚举，假设现在考虑到了字符串s1，那么我们已经处理过了所有字典序<s1的字符串s2，我们关心的是这些字符串中满足s1’<s2’的s2的数目，可以完美地用trie树解决。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 1000005; int n, f[N], a[N][26], cnt; string s[N]; void insert_rev_trie(string str) { int len=str.length(), now=0; for(int i=len-1; i>=0; --i) { if(a[now][str[i]-'a']==0) a[now][str[i]-'a']=++cnt; now=a[now][str[i]-'a']; ++f[now]; } } int calc_rev_trie(string str) { int len=str.length(), now=0, sum=0; for(int i=len-1; i>=0; --i) { for(int j=str[i]-'a'+1; j<26; ++j) sum += f[a[now][j]]; now=a[now][str[i]-'a']; } for(int j=0; j<26; ++j) sum += f[a[now][j]]; return sum; } int main() { cnt=0; mes(f, 0); mes(a, 0); scanf("%d", &n); rep(i,1,n) cin>>s[i]; sort(s+1, s+1+n); ll ans=0; rep(i,1,n) insert_rev_trie(s[i]), ans += calc_rev_trie(s[i]); printf("%lld ", ans); return 0; } /* 2 lopta kugla 4 lova novac aron sunce 14 branimir vladimir tom kruz bred pit zemlja nije ravna ploca ko je zapalio zito */