首页 > 代码库 > Coins

Coins

2024-09-06 10:29:34   214人阅读

题意：

有1~n 面值的硬币，第i个硬币有ai个，求问这些硬币可以凑出多少个权值。

 

解法：

假定对于第i个硬币，选取了$x_i$个，则凑出的权值为$S = \sum_{i=1}^n{x_i * i}$

其中$x_i$可以表示为$x_i = k_i * \frac{LCM(1,2..,n)}{i} + b_i$，从而有

$$S = LCM(1,2...n)* \sum_{i=1}^n {k_i} + \sum_{i=1}^n{b_i * i}$$

这样有$0<=bi<LCM/i $，$S$可以表示为若干个公比为$LCM$，首项为$\sum_{i=1}^n{b_i * i}$，

项数为$\sum_{i=1}^n {k_i}$的等差数列的并。

这样$a2_i = min \{ a_i \  mod \  \frac{LCM}{i} + \frac{LCM}{i}, a_i \} $，二进制拆分+bitset压位计算出

$O(n^2 * LCM *log(a2_i) / 64)$，进而计算出首项，合并等差数列即可。

 

技术分享 
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <bitset>
 5 #include <ctime>
 6 
 7 #define N 17
 8 #define LL long long
 9 #define M 360361
10 
11 using namespace std;
12 
13 int n,L,a[N];
14 bool flag[M];
15 bitset<M*N> f;
16 
17 LL gcd(LL a,LL b)
18 {
19     if(!b) return a;
20     return gcd(b,a%b);
21 }
22 
23 int main()
24 {
25 //    freopen("test.txt","r",stdin);
26     while(~scanf("%d",&n))
27     {
28         L=1;
29         int sum=0;
30         LL ans=0,K=0;
31         for(int i=2;i<=n;i++) L = L*i/gcd(L,i);
32         for(int i=1;i<=n;i++)
33         {
34             scanf("%d",&a[i]);
35             int tmp = min(a[i], a[i]%(L/i) + (L/i));
36             K += (a[i]-tmp) / (L/i);
37             a[i]=tmp;
38             sum+=i*a[i];
39         }
40         f.reset();
41         f[0]=1;
42         for(int i=1;i<=n;i++)
43         {
44             int cnt=a[i];
45             for(int j=1;cnt;j<<=1)
46             {
47                 int tmp=min(j,cnt);
48                 if(tmp*(LL)i > sum) break;
49                 f |= (f << (tmp*i));
50                 cnt-=tmp;
51             }
52         }
53         for(int i=0;i<=sum;i++)
54         {
55             if(!f[i]) continue;
56             ans++;
57             bool flag=0;
58             for(int j=i-L;j>=0;j-=L) if(f[j]) flag=1;
59             if(!flag) ans += K;
60         }
61         cout << ans << endl;
62     }
63     return 0;
64 }
View Code

 

Coins


联系
我们