构造+贪心/数论
为什么只有两个标题呢……因为第二题我不会……
怎样提高智商
构造题……然而一开始半天我都yy不出来……
后来我想：这题应该不会特别麻烦，而且既然样例只给了1，可能再给大一点就让人发现规律了……（心理战的可怕0.0？）然后yy了一下，发现全部都写0的答案是最多的，是$4*3^{n-1}$，然后就过了……
唯一用到的是快速幂？
//UOJ Round #5 A
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
const int MOD=; void read(int &v){
v=; int sign=; char ch=getchar();
while(ch<'' || ch>'') {if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}
v*=sign;
}
typedef long long LL; LL pow_mod(int a,int b){
LL r=,base=a;
while(b){
if (b&) r=(r*base)%MOD;
base=base*base%MOD;
b>>=;
}
return r;
} int main(){
int n=;
read(n);
printf("%lld\n",pow_mod(,n-)*%MOD);
F(i,,n) printf("A 0 0 0 0\n");
return ;
}
怎样跑得更快
Orz vfk&trz！
这题真的是一道非常好的题！
然而由于我实在太傻逼，直到现在才看懂vfk的题解……vfk的题解写的真的非常好，清晰易懂0.0
感觉莫比乌斯反演真是好神奇>_<，不过做过这道题以后对莫比乌斯反演又有了些新的感悟？
小范围枚举倍数or约数进行反演感觉更简单直观……易于理解……（然而大多数题目的数据范围都比较大？QwQ）
//UOJ Round5 C
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=1e5+,P=;
/*******************template********************/ int n,c,d,q;
int b[N],f_r[N],f_z[N],hx[N],x[N],g[N];
inline void exgcd(LL a,LL b,LL &d,LL &x,LL &y){
if (!b){d=a;x=;y=;}
else {exgcd(b,a%b,d,y,x); y-=(a/b)*x;}
}
inline LL inv(int a){
LL d,x,y;
exgcd(a,P,d,x,y);
return d== ? (x+P)%P : -;
}
inline LL Pow(LL a,int b){
LL r=;
for(;b;b>>=,a=a*a%P) if (b&) r=r*a%P;
return r;
} void solve(){
F(i,,n) f_z[i]=(LL)b[i]*g[i]%P;
F(i,,n)
for(int j=i+i;j<=n;j+=i){
f_z[j]-=f_z[i];
if (f_z[j]<) f_z[j]+=P;
}
F(i,,n){
if (f_r[i]==- && f_z[i]!=){puts("-1");return;}
hx[i]=(LL)f_r[i]*f_z[i]%P;
}
D(i,n,)
for(int j=i+i;j<=n;j+=i){
hx[i]-=hx[j];
if (hx[i]<) hx[i]+=P;
}
F(i,,n) x[i]=(LL)hx[i]*g[i]%P;
F(i,,n) printf("%d%c",x[i],i==n?'\n':' ');
}
int main(){
#ifndef ONLINE_JUDGE
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
#endif
n=getint(); c=getint(); d=getint(); q=getint();
F(i,,n){
f_r[i]=Pow(i,abs(c-d));
if (c<d) f_r[i]=inv(f_r[i]);
}
F(i,,n) g[i]=Pow(Pow(i,d),P-);
F(i,,n)
for(int j=i+i;j<=n;j+=i){
f_r[j]-=f_r[i];
if (f_r[j]<) f_r[j]+=P;
}
F(i,,n) f_r[i]=inv(f_r[i]);
while(q--){
F(i,,n) b[i]=getint();
solve();
}
return ;
}