1001 sum

计算下前缀和，看有没有模m相同的即可。 #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int pp[5100]; int T; int flag; int n,k; int sum; int main() { scanf("%d",&T); while (T--) { flag=0; memset(pp,0,sizeof(pp)); pp[0]=1; scanf("%d %d",&n,&k); sum=0; for (int i=1;i<=n;i++) { int x; scanf("%d",&x); sum=(sum+x)%k; if (pp[sum]) flag=1; pp[sum]=1; } if (flag) printf("YES "); else printf("NO "); } return 0; }

1002 domino

贪心去掉k−1个最大值即可 #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; int a[110000]; int T; int flag; int n,k; LL ans; int main() { scanf("%d",&T); while (T--) { scanf("%d %d",&n,&k); for (int i=1;iscanf("%d",&a[i]); sort(a+1,a+n); ans=0; for (int i=1;i<=max(n-k,0);i++) ans+=(LL)(a[i]+1LL); cout<return 0; }

1003 abs

因为y的每个质因子的次数都为2，所以y为完全平方数，然后暴力枚举下d(y=d∗d)，判断d是否每个质因子都只出现了一次。 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; LL x; int T; LL ans1,ans2; int check(LL x) { for (LL i=2;i*i<=x;i++) { if (x%i==0) { x/=i; if (x%i==0) return 0; } } return 1; } int main() { cin>>T; while (T--) { cin>>x; LL d=(LL)sqrt((double)x+0.5); for (LL i=1;;i++) { if (check(d+i)&&d+i>=2) { ans1=abs(x-(d+i)*(d+i)); break; } } ans2=1e18; for (LL i=0;;i++) { if ((d-i)<2) break; if (check(d-i)) { ans2=abs(x-(d-i)*(d-i)); break; } } cout<return 0; }

1004 Tower Defence

dp，f[i][j][k]，i表示1号点所在的联通块的大小，j表示1号点与联通块内其他点的最大距离，k表示与1号点最短距离恰好为j的点的个数，f[i][j][k]表示这样的方案数。考虑其对答案的贡献，对于不在1号点所在联通块内的 其他点，可以随便连，方案数为2n(n−1)2，将其乘起来即可。下面考虑f[i][j][k]的转移。枚举距离为j+1的点的个数l，首先用组合数从剩余n-i个点中选出l个点，这些点一定与第j层的点连至少一条边，所以层与层之间的连接方案为2k−1，其次，这些点之间也可以互相连边，方案数为2l(l−1)2。那么其对f[i+l][j+1][l]的贡献应该为
f[i][j][k]∗Cln−i∗(2k−1)∗(2l(l−1)2) #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const LL mod=1e9+7; int n,k; LL f[61][61][61]; LL ans; LL pow_mod(LL a,LL b,LL p) { LL tmp=1; a%=p; for(LL i=b;i;i>>=1,a=a*a%p) if(i&1)tmp=tmp*a%p; return tmp; } int T; LL C[70][70]; int main() { C[0][0]=1; for(int i=1;i<=61;i++){ C[i][0]=1; for (int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; } scanf("%d",&T); while (T--) { scanf("%d %d",&n,&k); memset(f,0,sizeof(f)); f[1][0][1]=1; ans=0; for (int i=0;ifor (int j=1;j<=n;j++) for (int l=1;l<=j;l++) { if (f[j][i][l]==0) continue; ans=(ans+f[j][i][l]*pow_mod(2,(LL)(n-j)*(n-j-1)/2LL,mod))%mod; for (int ll=1;ll<=n-j;ll++) { LL d=(((f[j][i][l]*pow_mod(pow_mod(2,l,mod)-1+mod,ll,mod))%mod)*pow_mod(2,(LL)(ll)*(ll-1)/2LL,mod))%mod; d=(d*C[n-j][ll])%mod; f[j+ll][i+1][ll]=(f[j+ll][i+1][ll]+d)%mod; } } } cout<return 0; }

1005 gcd

首先证明一个小结论：
当x≠1时，不妨设a>b:
∵(xa−1)≡−1(modx)
∴gcd(xa−1,xa−b)=1
∴gcd(xa−1,xb−1)=gcd(xa−1,xa−xa−b)=gcd(xa−b−1,xa−1)
由此可以得出:
gcd(x<