T1 巨胖的技能组合
题目：
考试最后做这道题的。
当时就听得 boshi 大喊一声：容斥！然后他就 Ak 了
然而我还是不会做
最后写了个 50 分的 dp 却得了 70 分。。。
正解：容斥+组合数
先假设所有的技能都能用无限次，根据插板法（考试时我还不会。。。）可以得到这样的情况方案数是：
$$C_{n+m-1}^{n-1}$$
然后我们来排除某些技能使用超限的情况
首先任选 1 个技能，故意让它超限（首先这个技能必须是有限制的技能），及使它的使用次数为 Li+1 次（因为这样剩余的总技能使用次数更大），再假设别的技能都能无限使用，看剩下的总技能使用次数和剩下的技能能组成多少种方案，这样拿原来假设每个技能都能无限使用时得到的值减去这个值就行了
但是我们会发现我们多减了，比如两个技能同时超限的情况就被多减了，于是我们和上面一样，任选一个技能，故意让它们超限，算出方案数，加到答案中。但我们又多加了三个技能同时超限的情况，所以减去。。。
以此类推，说白了就是容斥，选偶数个技能时加到答案，选奇数个时减去
这里要用到组合数，预处理一下阶乘和它们的逆元就行了
代码：
#include <bits/stdc++.h>
#define MOD (1000000007)
using namespace std;
typedef long long LL;
LL n,k,m,t[20],f[20][100005],ans,po[200005],ni[200005];
LL C(LL a,LL b){return po[a]*ni[b]%MOD*ni[a-b]%MOD;}
void dfs(LL cnt,LL fl,LL tot)
{
if(tot<0)return;
if(cnt==k+1)
{
ans=(ans+fl*C(tot+n-1,tot)%MOD+MOD)%MOD;
return;
}
dfs(cnt+1,fl,tot),dfs(cnt+1,-fl,tot-t[cnt]-1);
}
LL qpow(LL a,LL b)
{
LL sum=1;
while(b)
{
if(b&1)sum=sum*a%MOD;
b>>=1,a=a*a%MOD;
}
return sum;
}
int main()
{
freopen("dnf.in","r",stdin),freopen("dnf.out","w",stdout);
scanf("%lld%lld%lld",&n,&k,&m),memset(f,-1,sizeof(f)),po[1]=1,ni[1]=1;
for(int i=2;i<n+m;i++)po[i]=po[i-1]*i%MOD;
ni[n+m-1]=qpow(po[n+m-1],MOD-2);
for(int i=n+m-2;i>=2;i--)ni[i]=(i+1)*ni[i+1]%MOD;
for(int i=1;i<=k;i++)scanf("%lld",&t[i]);
dfs(1,1,m),printf("%lld\n",ans);
return 0;
}
T2 巨胖的辗转相除
题目：
我一看。。。辗转相除计算次数最多的不就是斐波那契数列相邻两项么？因为它们 gcd 一次其实就是向前移动一位
打标证明了一下
然后高精度压位（我压了 8 位）
首先打了个递推的加法，发现最大数据 5s。。。
然后我就打了个二分+logn 计算斐波那契数列，复杂度理论上是 log2 级别的（不带高进度复杂度），然而我写的高精度乘法常数巨大，最大数据 10s。。。
于是我开始疯狂优化加法，去除了没必要的 memset，然后用 unsigned char 自动溢出滚动数组（防止 swap），最后加法省去了一个 swap 就 0.9s 过最大数据
怕出事，写了个读入优化，0.6s 过了
代码：
#include <bits/stdc++.h>
#define MOD (100000000)
using namespace std;
typedef unsigned char UC;
struct BI
{
int arr[2000],cnt;
BI(){cnt=0;}
void check()
{
int d=0;
for(int i=0;i<cnt;i++)arr[i]+=d,d=arr[i]/MOD,arr[i]%=MOD;
while(d)arr[cnt]=d,d=arr[cnt]/MOD,arr[cnt]%=MOD,cnt++;
}
void operator = (int a){memset(arr,0,sizeof(arr)),arr[0]=a,cnt=1,check();}
void work(BI a,BI b)
{
cnt=a.cnt;
for(int i=0;i<cnt;i++)arr[i]=a.arr[i];
for(int i=0;i<b.cnt;i++)arr[i]+=b.arr[i];
check();
}
bool operator <= (BI a)
{
if(cnt==a.cnt)
{
for(int i=cnt-1;i>=0;i--)
{
if(arr[i]<a.arr[i])return 1;
if(arr[i]>a.arr[i])return 0;
}
return 1;
}
if(cnt<a.cnt)return 1;
return 0;
}
void print()
{
printf("%d",arr[cnt-1]);
for(int i=cnt-2;i>=0;i--)printf("%.8d",arr[i]);
putchar('\n');
}
}fib[300],n;
char str[20000];
int strl;
int main()
{
freopen("euclid.in","r",stdin),freopen("euclid.out","w",stdout);
char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))str[strl++]=c,c=getchar();
for(int i=strl-1;i>=0;i-=8)
{
int k=0;
for(int j=i,l=1;j>i-8&&str[j];j--,l*=10)k=k+l*(str[j]-'0');
n.arr[n.cnt++]=k;
}
fib[0]=1,fib[1]=1,fib[2]=2;UC cur=2,pre=1,post=0;
while(fib[cur]<=n){cur++,pre++,post++,fib[cur].work(fib[pre],fib[post]);}
fib[post].print(),fib[pre].print();
return 0;
}
T3 巨胖的最大约数
题目：
个人感觉做法很玄学。。。
评测发现程序访问了左闭右开的素数表的右端。。。然后 0 分 re，痛彻心扉地删掉了一个等于号以后过了
首先没必要从 1~n 筛素数，因为其实大素数根本不用考虑（比如一个很大的素数它的约数个数为 1，而且大素数相乘得到的数字虽然大，但是约数少啊），算了算发现搞出 1~100 的素数就行了（应该还不用到 100，它们乘起来已经很大了）
推了一下约数个数公式：设它分解质因数以后质因数的次数分别问 a1,a2,a3… 那它的约数个数就是 (a1+1)×(a2+1)×(a3+1)…
于是打了个很玄学的搜索，用上面那些素数组合到一起（乘法），记录约数个数和大小，最后求得答案
居然还真 AC 了。。。真玄学
（也许能证但不是很想（lande）证）
代码：
#include <bits/stdc++.h>
#define PS (25)
using namespace std;
typedef long long LL;
static const LL p[PS]=
{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
LL n,mx,ans;
void dfs(LL cur,LL cnt,LL tot)
{
if(cnt>=PS)
{
if(tot>mx||(tot==mx&&cur<ans))ans=cur,mx=tot;
return;
}
dfs(cur,cnt+1,tot);
for(LL i=p[cnt],j=2;cur*i<=n&&(cur*i)%i==0&&cur*i>0;i*=p[cnt],j++)
dfs(cur*i,cnt+1,tot*j);
}
int main()
{
freopen("divisor.in","r",stdin),freopen("divisor.out","w",stdout);
scanf("%lld",&n),dfs(1,0,1),printf("%lld\n",ans);
return 0;
}
0 条评论