A.
我的做法是nmlogn的。。。。直接做m次堆贪心就可以。按理说是能过的。。。
正解直接是在原dp上搞一搞。。。可以做到n^2+nlog?
2333
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define maxn 2050 using namespace std; long long n,m,a[maxn]; long long now=0; struct status { long long id,val; status (long long id,long long val):id(id),val(val) {} status () {} friend bool operator < (status x,status y) { return x.val>y.val; } }; priority_queue <status> q; int main() { scanf("%lld%lld",&n,&m); for (long long i=1;i<=n;i++) scanf("%lld",&a[i]); for (long long i=1;i<=m;i++) { scanf("%lld",&now);long long ret=0; while (!q.empty()) q.pop(); for (long long j=1;j<=n;j++) { if (now+a[j]>=0) { now+=a[j]; if (a[j]<0) q.push(status(j,a[j])); } else { ret++; if (!q.empty()) { if (now-q.top().val+a[j]>=now) {now=now-q.top().val+a[j];q.pop();q.push(status(j,a[j]));} } } } printf("%lld ",ret); } return 0; }
B.
第一问的话，可以用phi(a*b)=phi(a)*phi(b)*gcd(a,b)/phi(gcd(a,b))，那么可以筛出所有需要的东西。
至于第二问。。参照上帝与集合的正确用法。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 10000050 #define mod 1000000007 using namespace std; int n,m,k=0,p,prime[maxn],tot=0,d[maxn],phi[maxn],inv[maxn]; bool vis[maxn]; int gcd(int a,int b) { if (!b) return a; return gcd(b,a%b); } void get_table() { phi[1]=inv[1]=d[1]=1; for (register int i=2;i<=maxn-50;i++) { inv[i]=(-(long long)mod/i*inv[mod%i]%mod+mod)%mod; if (!vis[i]) { prime[++tot]=i; phi[i]=i-1; if (n%i==0) d[i]=i;else d[i]=1; } for (register int j=1;j<=tot && i*prime[j]<=maxn;j++) { vis[i*prime[j]]=true; if ((n/d[i])%prime[j]==0) d[i*prime[j]]=d[i]*prime[j]; else d[i*prime[j]]=d[i]; if (i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1); else { phi[i*prime[j]]=phi[i]*prime[j]; break; } } } } long long f_pow(long long x,long long y,long long p) { long long ans=1,base=(long long)x; while (y) { if (y&1) ans=(ans*base)%p; base=(base*base)%p; y>>=1; } return ans; } void work1() { for (int i=1;i<=m;i++) { long long ret=(((long long)phi[i]*phi[n])%mod*d[i])%mod*inv[phi[d[i]]]%mod,ret2; k=((int)ret+k)%mod; } } int work2(int p) { if (p==1) return 0; return f_pow(k,work2(phi[p])+phi[p],p); } int main() { scanf("%d%d%d",&n,&m,&p); get_table(); work1(); printf("%d ",work2(p)); return 0; }
C.
还是数学题。。。。
gcd(f[a],f[b])=f[gcd(a,b)]。
lcm(a,b,c)=a*b*c/gcd(a,b)/gcd(a,c)/gcd(b,c)*gcd(a,b,c)。
那么可以g[i]表示F[i]的幂次。首先g[i]+g[2*i]+...=Σ(i=1..n)(-1)^(n+1)*C(n,i)=[n!=0]。
所以倒着for，调和级数搞一搞就好了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 50050 #define maxm 1000050 #define mod 1000000007 using namespace std; long long n,a[maxn],cnt[maxm],num[maxm],g[maxm],mx=0,f[maxm]; long long ans=1; long long f_pow(long long x,long long y) { long long ans=1,base=x; while (y) { if (y&1) ans=(ans*base)%mod; base=(base*base)%mod; y>>=1; } return ans; } int main() { scanf("%lld",&n); for (long long i=1;i<=n;i++) { scanf("%lld",&a[i]); cnt[a[i]]++;mx=max(mx,a[i]); } for (long long i=1;i<=mx;i++) for (long long j=1;j*i<=mx;j++) num[i]+=cnt[i*j]; for (long long i=mx;i>=1;i--) { if (!num[i]) continue; g[i]=1; for (long long j=2*i;j<=mx;j+=i) g[i]=(g[i]-g[j]+mod-1)%(mod-1); } f[1]=f[2]=1; for (long long i=3;i<=mx;i++) f[i]=(f[i-1]+f[i-2])%mod; for (long long i=1;i<=mx;i++) ans=(ans*f_pow(f[i],g[i]))%mod; printf("%lld ",ans); return 0; }