2013-C21-team5
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
|
->=+++=<-
T+T
| |
|+|
| |
|+|
| |
|+|
| |
|+|
| |
|+|
V
}}}
{{{
C题
这题不需要用莫比乌斯反演...
令三角形三边长为a、b、c且a<=b<=c
设f(x)为周长为x的三角形的数目，则f(x)可以分为：(1)a<=b==c的情况 与 (2)a<=b<c的情况
第一种情况的数目可以直接算出来：floor(x/2.0)-ceil(x/3.0)
第二种情况a<=b<c，那么我们让c减1，则形式为a<=b<=c的三角形总数，即f(x-1)，所以f(x)可以由f(x-1)与第一种情况构成；但是注意：
f(x-1)中有些合法的情况在给c做了加1操作后会变得不合法，即a+b==c+1的情况，需要把这类不合法的情况减掉。
如何计算不合法的情况？因为a+b==c+1且a+b+c+1==x，所以a+b==c+1==x/2，即此时x必然为偶数；所以a+b==x/2，不合法数目为 x/2/2.
f(x)计算好了，接下来看划分。
因为所有三角形都是相似的，所以他们必然起源于同一个原型——即gcd(a,b,c)==1三边互质的三角形。
令周长为x的原型三角形的个数为g(x)。
假设这个原型三角形周长为d，且d|x，那么可以把x分成n/d份，而基于这个原型的所有组合可以用隔板法算出来(n/d-1个空），g(d)的贡献为
g(d)*pow(2, n/d-1)。
g(x)可以由筛法求出，g(x) = f(x) - sigma(g(d)) 其中d|x。
初始所有g(x) == f(x)，用类似筛法的方式求即可，总复杂度O(N*lnN)
这个复杂度不同于素数筛法的复杂度，因为宿舍的个数相比N小很多。
代码：
typedef long long llg;
const int N = 5000001;
const int mod = 1000000007;
int pmd[N], g[N];
void solve() {
pmd[0] = 1;
for(int i = 1; i < N; i++) {
pmd[i] = pmd[i-1] << 1;
if(pmd[i] >= mod) pmd[i] -= mod;
}
g[3] = 1;
for(int i = 4; i < N; i++) {
int l, r;
l = (i-1)/2; r = i/3;
if(i%3) ++r;
g[i] = g[i-1] + (l-r+1);
if(g[i] >= mod) g[i] -= mod;
if(!(i & 1)) g[i] -= (i>>2);
if(g[i] < 0) g[i] += mod;
}
for(int i = 3; i < N; i++) {
for(int j = i+i; j < N; j += i) {
g[j] -= g[i];
if(g[j] < 0) g[j] += mod;
}
}
int n, T = 0;
llg ans;
while(scanf("%d", &n) != EOF) {
ans = 0;
for(int d = 1; d <= n; d++) if(n%d == 0) {
ans = ans + ((llg)pmd[d-1]*g[n/d]);
ans %= mod;
}
cout << "Case " << (++T) << ": " << ans <<"\n";
}
}
}}}
{{{
E题
Solution:
借用了kmp的思想.
在运行过程中不断维护一个匹配串pat,将其与str进行匹配.
对于str[i],如果pat怎么也匹配不了的话,则将pat更新为目前为止从pat在str中出现的最晚位置l到i这一段字符串[l,i].
再不断更新整个pat在str中的最晚出现位置.
整个过程中使用了kmp的方法,以保证匹配复杂度为O(n).
具体做法:
ss为原串,pat是用ss[l]~ss[l+k-1]表示的,l为pat目前位置pat出现的最晚位置,k为pat的长度.
a数组存的是pat的自匹配关系.在更新过程中,不断维护数组a.
然后还要注意很多细节,详见代码.
Code:
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
const int INF=10000007;
const int MaxL=100010;
char ss[MaxL];
int a[MaxL],q[MaxL],l[MaxL],len;
int gao(){
int len=strlen(ss);
memset(a,-1,sizeof(a[0])*(len+5));
int l=0,lr=0; //lr表示匹配时pat内字符的位置(kmp的匹配过程)
int i,j,k=1;
for (i=1; i<len; i++){
while (lr>0 && ss[i]!=ss[l+lr]) lr=a[lr-1]+1; //kmp匹配过程
if (ss[i]!=ss[l+lr]){
k=i-l+1; a[k-1]=-1; continue;
//当无法匹配时,将pat更新为l到i.注意,a[k-1]也要更新!(在这里WA了好久)
}
for (j=0; i+j<len; j++)
if (ss[i+j]==ss[l+lr+j]){
if (lr+j+1==k){
l=i-lr; lr=a[lr+j]+1; //更新pat最晚出现位置
i+=j; break;
}
a[i+j-l]=lr+j; //维护数组a, (i+j-l)是相对位置.
}
else{
lr=a[lr+j-1]+1;
i+=j-1; break;
}
}
return len-l;
}
int main(){
int cas=0;
while (scanf("%s",ss)!=EOF){
printf("Case %d: %d\n",++cas,gao());
}
return 0;
}
}}}{{{
|
->=+++=<-
T+T
| |
|+|
| |
|+|
| |
|+|
| |
|+|
| |
|+|
V
}}}
C题
这题不需要用莫比乌斯反演...
令三角形三边长为a、b、c且a<=b<=c
设f(x)为周长为x的三角形的数目，则f(x)可以分为：(1)a<=b==c的情况 与 (2)a<=b<c的情况
第一种情况的数目可以直接算出来：floor(x/2.0)-ceil(x/3.0)
第二种情况a<=b<c，那么我们让c减1，则形式为a<=b<=c的三角形总数，即f(x-1)，所以f(x)可以由f(x-1)与第一种情况构成；但是注意：
f(x-1)中有些合法的情况在给c做了加1操作后会变得不合法，即a+b==c+1的情况，需要把这类不合法的情况减掉。
如何计算不合法的情况？因为a+b==c+1且a+b+c+1==x，所以a+b==c+1==x/2，即此时x必然为偶数；所以a+b==x/2，不合法数目为 x/2/2.
f(x)计算好了，接下来看划分。
因为所有三角形都是相似的，所以他们必然起源于同一个原型——即gcd(a,b,c)==1三边互质的三角形。
令周长为x的原型三角形的个数为g(x)。
假设这个原型三角形周长为d，且d|x，那么可以把x分成n/d份，而基于这个原型的所有组合可以用隔板法算出来(n/d-1个空），g(d)的贡献为
g(d)*pow(2, n/d-1)。
g(x)可以由筛法求出，g(x) = f(x) - sigma(g(d)) 其中d|x。
初始所有g(x) == f(x)，用类似筛法的方式求即可，总复杂度O(N*lnN)
这个复杂度不同于素数筛法的复杂度，因为宿舍的个数相比N小很多。
代码：
typedef long long llg;
const int N = 5000001;
const int mod = 1000000007;
int pmd[N], g[N];
void solve() {
pmd[0] = 1;
for(int i = 1; i < N; i++) {
pmd[i] = pmd[i-1] << 1;
if(pmd[i] >= mod) pmd[i] -= mod;
}
g[3] = 1;
for(int i = 4; i < N; i++) {
int l, r;
l = (i-1)/2; r = i/3;
if(i%3) ++r;
g[i] = g[i-1] + (l-r+1);
if(g[i] >= mod) g[i] -= mod;
if(!(i & 1)) g[i] -= (i>>2);
if(g[i] < 0) g[i] += mod;
}
for(int i = 3; i < N; i++) {
for(int j = i+i; j < N; j += i) {
g[j] -= g[i];
if(g[j] < 0) g[j] += mod;
}
}
int n, T = 0;
llg ans;
while(scanf("%d", &n) != EOF) {
ans = 0;
for(int d = 1; d <= n; d++) if(n%d == 0) {
ans = ans + ((llg)pmd[d-1]*g[n/d]);
ans %= mod;
}
cout << "Case " << (++T) << ": " << ans <<"\n";
}
}
E题
Solution:
借用了kmp的思想.
在运行过程中不断维护一个匹配串pat,将其与str进行匹配.
对于str[i],如果pat怎么也匹配不了的话,则将pat更新为目前为止从pat在str中出现的最晚位置l到i这一段字符串[l,i].
再不断更新整个pat在str中的最晚出现位置.
整个过程中使用了kmp的方法,以保证匹配复杂度为O(n).
具体做法:
ss为原串,pat是用ss[l]~ss[l+k-1]表示的,l为pat目前位置pat出现的最晚位置,k为pat的长度.
a数组存的是pat的自匹配关系.在更新过程中,不断维护数组a.
然后还要注意很多细节,详见代码.
Code:
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
const int INF=10000007;
const int MaxL=100010;
char ss[MaxL];
int a[MaxL],q[MaxL],l[MaxL],len;
int gao(){
int len=strlen(ss);
memset(a,-1,sizeof(a[0])*(len+5));
int l=0,lr=0; //lr表示匹配时pat内字符的位置(kmp的匹配过程)
int i,j,k=1;
for (i=1; i<len; i++){
while (lr>0 && ss[i]!=ss[l+lr]) lr=a[lr-1]+1; //kmp匹配过程
if (ss[i]!=ss[l+lr]){
k=i-l+1; a[k-1]=-1; continue;
//当无法匹配时,将pat更新为l到i.注意,a[k-1]也要更新!(在这里WA了好久)
}
for (j=0; i+j<len; j++)
if (ss[i+j]==ss[l+lr+j]){
if (lr+j+1==k){
l=i-lr; lr=a[lr+j]+1; //更新pat最晚出现位置
i+=j; break;
}
a[i+j-l]=lr+j; //维护数组a, (i+j-l)是相对位置.
}
else{
lr=a[lr+j-1]+1;
i+=j-1; break;
}
}
return len-l;
}
int main(){
int cas=0;
while (scanf("%s",ss)!=EOF){
printf("Case %d: %d\n",++cas,gao());
}
return 0;
}