HDU 4466 HDOJ Triangle 2012ACM亚洲赛成都赛区C题

时间:2022-04-05 16:46:51

http://acm.hdu.edu.cn/showproblem.php?pid=4466

题目意思:

  给定一个长度为n的铁丝,将其分成有顺序的若干份,每份折成三角形,要求所有的三角形相似。

  三角形顺序不同视为不同方案,三边相等视为同一方案。求方案个数。

 

首先定义f(x)表示周长为x的三角形个数。

我们用(a,b,c)表示一个三角形,其中a <= b <= c 

将f(x)的所有三角形分为两部分,b=c 和 b!=c 的

  b = c 的三角形个数

    a至少为1,c的最大值为floor((x-1)/2)

    a<=b<=c,所所以c的最小值为ceil(x/3)

    个数为floor((x-1)/2) - ceil(x/3) + 1。注意x比较小的时候,可能最大值比最小值小,此时差为-1,加1后为0,不影响结果。

    化简后就是程序中的(i-1)/2 - i/3 + (i%3?0:1)

  b!=c 的三角形个数

    由于b!=c,则b<c,则b<=c - 1

    且a + b > c > c - 1

    所以,(a,b,c-1)也一定是三角形。

    所以这部分的方案数等于 f(x-1) 减去 f(x-1)中满足a + b = c + 1的三角形

    含有a+b=c+1的三角形的x一定为奇数:

      此时c = (x-1)/2

      方案数floor((x - (x-1)/2)/2)

    化简后就是程序中的(x+1)/4

然后定义g(x)为周长为x的本质三角形个数(官方现场题解给出的概念,就是三边最大公约数为1的三角形)

  则g(x) = f(x) - sigma(g(k)) ,其中k为小于x的所有x的约数,这个是可以nlogn全部预处理出来

    Ps:刚发现这题其实组数不很多,完全没必要预处理,预处理版本1.7s,直接计算反而更快93ms,见代码版本二。

 

然后对于题目给定的n,枚举n的所有约数,对于n的约数i,将有n/i个三角形。隔板法可得,对应的分解方案数目为 2^(n/i - 1)

 

 

比赛的时候已经想到O(n)求n分解三角形个数地方法。结果没看到所有三角形要相似这个条件,果断变神题。

看到这个条件,哎呀,后悔啊,现场假如没漏看条件说不定就出的,金牌就有希望了啊TAT。

代码如下

  (新增版本二,无筛选直接计算)

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 typedef long long ll;
 5 const int N=5000000,m=1000000007;
 6 int n,f[N+10],p2[N+10],C;
 7 int l,k[6010],g[6010];
 8 int main()
 9 {
10     f[3]=1;p2[1]=1;p2[2]=2;p2[3]=4;
11     for(int i=4;i<=N;i++){
12         p2[i]=p2[i-1]<<1;
13         if(p2[i]>=m) p2[i]-=m;
14         f[i]=f[i-1] + (i-1)/2 - i/3 + (i%3?0:1);
15         if(!(i&1))f[i]-=i/4;
16         if(f[i]>=m) f[i]-=m;
17         if(f[i]<0) f[i]+=m;
18     }
19     while(~scanf("%d",&n)){
20         ll ans=0;
21         l=0;
22         for(int i=1;i*i<=n;i++)if(n%i==0){
23             k[l++]=i;
24             if(i*i!=n)k[l++]=n/i;
25         }
26         sort(k,k+l);
27         for(int i=0;i<l;i++) g[i]=f[k[i]];
28         for(int i=0;i<l;i++){
29             for(int j=i+1;j<l;j++)if(k[j]%k[i]==0){
30                 g[j]-=g[i];
31                 if(g[j]<0)g[j]+=m;
32             }
33             ans=(ans + (ll)g[i]*p2[n/k[i]])%m;
34         }
35         printf("Case %d: %I64d\n",++C,(ans+m)%m);
36     }
37     return 0;
38 }

 

  (版本一)

 1 #include<cstdio>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=5000000,m=1000000007;
 5 int n,f[N+10],p2[N+10],C;
 6 int main()
 7 {
 8     f[3]=1;p2[1]=1;p2[2]=2;
 9     for(int i=4;i<=N;i++){
10         f[i]=f[i-1] + (i-1)/2 - i/3 + (i%3?0:1);
11         if(!(i&1))f[i]-=i/4;
12         if(f[i]>=m) f[i]-=m;
13         if(f[i]<0) f[i]+=m;
14     }
15     for(int i=3;i<=N;i++){
16         p2[i]=p2[i-1]<<1;
17         if(p2[i]>=m) p2[i]-=m;
18         for(int j=i+i;j<=N;j+=i){
19             f[j]-=f[i];
20             if(f[j]<0) f[j]+=m;
21         }
22     }
23     while(~scanf("%d",&n)){
24         ll ans=0;
25         for(int i=1;i*i<=n;i++)if(n%i==0){
26             ans = (ans + (ll)f[i]*p2[n/i])%m;
27             if(i*i!=n) ans = (ans + (ll)f[n/i]*p2[i])%m;
28         }
29         printf("Case %d: %I64d\n",++C,(ans+m)%m);
30     }
31     return 0;
32 }