day 15
Frost_Delay
2019-08-15 20:43:04
我变强了！，今天模拟赛我第11！！！，得分200/300，感谢良心数据！；
以下是总结：
T1贪心，排序后第K大乘第K小即可，long long可过；
T2我不会做，得了三十分暴力分，听说有原题，题面是 1/x+1/y=1/(n!) ，求有多少种x，y符合题意；
T3其实是二分图匹配，但我不会，写了个贪心+搜索，还好数据没卡我，得了70分；
于是得分100+30+70=200！；
开心开心。
T1
库特的向量(code)
```cpp
#include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
long long a[1010],b[1010],n;
long long ans;
inline int read()
{
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
inline int cmp(int x,int y)
{
return x<y;
}
inline int cmp1(int x,int y)
{
return x>y;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)b[i]=read();
sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp1);
for(int i=1;i<=n;i++)
ans+=a[i]*b[i];
printf("%lld",ans);
return 0;
}
```
T2
恭介的法则(rule)
经过我~~苦思冥想~~一顿调试，找出了一个方法：
1.分解n!的质因数，由于要分解的是（n!）2
但只需要将分解出的质数指数乘2即可，由约数个数定理可得出答案；
2.但这和原题（bzoj2721）（洛谷1445）不太一样，它不取模！；
于是，我们还需要高精度乘法；而且要压位！不然存不下；
于是，一段好看丑陋的代码产生了
```cpp
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=3000000;
long long n,num[maxn],ans[3000000]={0,1},size=1;
void dec(int x)
{
while(x%2==0){
num[2]++;x/=2;
}
for(int i=3;i*i<=x;i+=2)
while(x%i==0)
num[i]++,x=x/i;
if(x!=1) num[x]++;
}
void mul(long long x)
{
for(int i=1;i<=size;i++)
ans[i]*=x;
for(int i=1;i<size;i++)
{
if(ans[i]>=10000)
{
int temp=ans[i]/10000;
ans[i]%=10000;
ans[i+1]+=temp;
}
}
while(ans[size]>=10000)
{
int temp=ans[size]/10000;
ans[size]%=10000;
ans[++size]+=temp;
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
dec(i);
for(int i=1;i<=n;i++)
if(num[i])
{
mul(num[i]*2+1);
}
printf("%lld",ans[size]);
for(int i=size-1;i>=1;i--)
{
printf("%lld",ans[i]/1000);
printf("%lld",ans[i]/100%10);
printf("%lld",ans[i]/10%10);
printf("%lld",ans[i]%10);
}
printf("\n");
return 0;
}
```
但是，它tle了！于是，我继续修改；
经过同宿舍dalao——lx指点；
我AC了！
想法：由于每个num中的值可能很小，所以我们只要累积到一定大小再乘入答案；
这样就可以跑的飞快！
AC代码
```cpp
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=3000000;
unsigned long long n,num[maxn],ans[3000000]={0,1},size=1;
void dec(int x)
{
while(x%2==0){
num[2]++;x/=2;
}
for(int i=3;i*i<=x;i+=2)
while(x%i==0)
num[i]++,x=x/i;
if(x!=1) num[x]++;
}
void mul(long long x)
{
for(int i=1;i<=size;i++)
ans[i]*=x;
for(int i=1;i<size;i++)
{
if(ans[i]>=10000)
{
int temp=ans[i]/10000;
ans[i]%=10000;
ans[i+1]+=temp;
}
}
while(ans[size]>=10000)
{
int temp=ans[size]/10000;
ans[size]%=10000;
ans[++size]+=temp;
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
dec(i);
unsigned long long p=1;
for(int i=1;i<=n;i++)
if(num[i])
{
p*=(num[i]*2+1);
if(p>50000)
{
mul(p);
p=1;
}
}
mul(p);
printf("%lld",ans[size]);
for(int i=size-1;i>=1;i--)
{
printf("%lld",ans[i]/1000);
printf("%lld",ans[i]/100%10);
printf("%lld",ans[i]/10%10);
printf("%lld",ans[i]%10);
}
printf("\n");
return 0;
}
```
T3
沙耶的玩偶(doll)
未完待续