由于错误的比赛策略、过度的水群和我早上不知道有这个比赛的残酷事实,我最多就拿200分了,惨败……比赛结束15分钟之后才写完C。无论如何,我似乎还是可以放一下代码,水一篇博客的?
所有代码未经证实。
第一题
#include <iostream>
using namespace std;
typedef long long ll;
int gcd(int a,int b){
return b != 0?gcd(b,a%b):a;
}
int T,p1,p2,k;
int main(){
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
ios::sync_with_stdio(false);
cin>>T;
while(T--){
cin>>p1>>p2>>k;
int d = gcd(p1,p2);
p1/=d;
p2/=d;
if(p1>p2)swap(p1,p2);
int lim = (p2+p1-2)/p1;
if(lim>=k){
cout<<"No\n";
}else{
cout<<"Yes\n";
}
}
return 0;
}
第二题
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
char buf[1000000],*p1,*p2;
inline bool isdigit(const char &ch){
return ch>=48&&ch<=57;
}
inline char nextchar(){
return p1==p2&&(p2=buf+fread(p1=buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline void getint(int &des){
char ch=des=0;
while(!isdigit(ch)&&ch!=EOF)ch=nextchar();
while(isdigit(ch))des=des*10+ch-48,ch=nextchar();
}
using namespace std;
typedef long long ll;
const int mod = 1000000007;
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int sq(int x){return 1ll*x*x%mod;}
int pow(int a,int b){return b == 0 ? 1 : ( b&1 ? mul(a,sq(pow(a,b/2))) : sq(pow(a,b/2)));}
int n,A[1000010],V[1000010];
vector<int> po[1000010];
int d1[1000010],d2[1000010];
inline void update(const int &left,const int &right,const int &w){
register int i;
for(i=left;i<=1000005;i+=i&-i){
d1[i]=add(d1[i],w);
d2[i]=add(d2[i],mul(left,w));
}
for(i=right;i<=1000005;i+=i&-i){
d1[i]=sub(d1[i],w);
d2[i]=sub(d2[i],mul(right,w));
}
}
inline int query(const int &left,const int &right){ //×ó±ÕÓÒ¿ª
register int i;register int ans=0;
for(i=left-1;i>=1;i-=i&-i){
ans=sub(ans,(1ll*d1[i]*left-d2[i]+mod)%mod);
}
for(i=right-1;i>=1;i-=i&-i){
ans=(1ll*d1[i]*right-d2[i]+ans+mod)%mod;
}
return ans;
}
int main() {
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
getint(n);
for(int i=0;i<n;i++){
getint(A[i]);V[i] = A[i];
}
sort(V,V+n);
int m = unique(V,V+n)-V;
for(int i=0;i<n;i++){
A[i] = lower_bound(V,V+m,A[i])-V;
po[A[i]].push_back(i);
}
for(int i=0;i<n;i++)reverse(po[i].begin(),po[i].end());
int ans = 0,cu = 0;
int cv = 0;
for(int i=0;i<n;i++){
if(i == po[A[i]].back()){
cv+=1;
update(i+1,n-1+2,1);
}
cu = add(cu,sq(cv));
}
for(int i=0;i<n;i++){
ans = add(ans,cu);
po[A[i]].pop_back();
int r = po[A[i]].size()?po[A[i]].back():n;
cu = sub(cu,mul(2,query(i+1,r-1+2)));
cu = add(cu,r-i);
update(i+1,r-1+2,mod-1);
}
cout<<ans<<endl;
return 0;
}
第三题
设dp[i][j]为第i号点的子树中选取j对配对节点的选择方案数。
取,答案序列为,那么我们有:
于是使用二项式反演就可以求出答案了。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int mod = 998244353;
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int sq(int x){return 1ll*x*x%mod;}
int mpow(int a,int b){return b == 0 ? 1 : ( b&1 ? mul(a,sq(mpow(a,b/2))) : sq(mpow(a,b/2)));}
const int N = 1000000;
int fac[N+10],invfac[N+10];
int C(int n,int m){
if(n<0 || m<0 || m>n)return 0;
return mul(fac[n],mul(invfac[m],invfac[n-m]));
}
int n,u,v;
vector<int> G[5050];
char ch[5050];
int dp[5050][5050],sz[5050],sc[5050][2];
void dfs(int num,int cf = -1){
dp[num][0] = 1;
for(auto ct:G[num]){
if(ct == cf)continue;
dfs(ct,num);
vector<int> ndp(sz[num]+sz[ct]+2,0);
for(int i=0;i<=sz[num];i++){
for(int j=0;j<=sz[ct];j++){
ndp[i+j] = add(ndp[i+j],mul(dp[num][i],dp[ct][j]));
}
}
for(int i=0;i<ndp.size();i++)dp[num][i] = ndp[i];
sz[num]+=sz[ct];
sc[num][0]+=sc[ct][0];
sc[num][1]+=sc[ct][1];
}
vector<int> ndp(sz[num]+2,0);
for(int i=0;i<=sz[num];i++){
if(!dp[num][i])continue;
ndp[i] = add(ndp[i],dp[num][i]);
int ca = sc[num][(ch[num]-'0')^1]-i;
if(ca<0)break;
ndp[i+1] = add(ndp[i+1],mul(dp[num][i],ca));
}
for(int i=0;i<ndp.size();i++)dp[num][i] = ndp[i];
sz[num] +=1;
sc[num][ch[num]-'0']+=1;
}
int main() {
//freopen("match.in","r",stdin);
//freopen("match.out","w",stdout);
fac[0] = 1;
for(int i=1;i<=N;i++)fac[i] = mul(fac[i-1],i);
invfac[N] = mpow(fac[N],mod-2);
for(int i=N-1;i>=0;i--) invfac[i] = mul(invfac[i+1],i+1);
cin>>n;
cin>>(ch+1);
for(int i=1;i<n;i++){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1);
for(int i=0;i<=n/2;i++){
dp[1][i] = mul(dp[1][i],fac[n/2-i]);
}
for(int i=0;i<=n/2;i++){
int cans = 0;
for(int j=i;j<=n/2;j++){
if((j-i)%2 == 1){
cans = sub(cans,mul(C(j,i),dp[1][j]));
}else{
cans = add(cans,mul(C(j,i),dp[1][j]));
}
}
cout<<cans<<" \n"[i == n/2];
}
return 0;
}
Total Page Visits: 4084
发表回复