问题标题: 关于NOIP2024第2题

Question

0

包思远

新手启示者

我已经AC了，分享一下代码：

#include<bits/stdc++.h>
using namespace std;
int T,n,m,v,ans;
const int Mod=1e9+7;
map<int,int> b,vis;
vector<int> a;
vector<int> k;
vector<int> num;
int fast(int x,int y){
	if(y==0)return 1;
	if(y==1)return x%Mod;
	int t=fast(x,y/2);
	if(y%2==0){
		t=((long long)t*t)%Mod;
		return t;
	}
	else{
		t=((long long)t*t)%Mod;
		t=(long long)t*x%Mod;
		return t%Mod;
	}
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>T;
	while(T--){
		bool flag=false;
		cin>>n>>m>>v;
		b.clear();
		a.clear();
		vis.clear();
		k.clear();
		num.clear();
		ans=1;
		for(int i=1,c,d;i<=m;i++){
			cin>>c>>d;
			if(flag)continue;
			if(b[c]!=0&&b[c]!=d){
				flag=true;
				continue;
			}
			if(b[c]==0){
				b[c]=d;
				a.push_back(c);
			}
		}
		if(flag){
			cout<<0<<endl;
			continue;
		}
		sort(a.begin(),a.end());
		k.push_back(-1);
		num.push_back(-1);
		for(int i=1;i<a.size();i++){
			if(vis[a[i]-a[i-1]-1]==0){
				k.push_back(a[i]-a[i-1]-1);
				num.push_back(1);
				vis[a[i]-a[i-1]-1]=k.size()-1;
			}
			else num[vis[a[i]-a[i-1]-1]]++;
		}
		for(int i=1;i<k.size();i++){
			int sum=(fast(v,k[i]+2)+1-v+Mod)%Mod;
			sum=((long long)sum*fast(v,k[i]))%Mod;
			sum=fast(sum,num[i]);
			ans=((long long)ans*sum)%Mod;
		}
		ans=((long long)ans*fast(v,(a[0]-1)*2+(n-a[a.size()-1])*2))%Mod;
		cout<<ans<<endl;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

附题目：

样例(assign.zip)下载地址：https://www.luogu.com.cn/fe/api/problem/downloadAttachment/kmklspbn?contestId=217331

包思远在2024-12-06 21:50:40追加了内容

注：assign.zip为Linux下的UTF-8编码的数据，在Windows系统下无法直接使用，建议将文件里的内容复制到酷町编程的IDE中，再把IDE里显示的内容复制粘贴到文件里，最后保存即可。

酷町豆代码分享 C++ 5条评论 2 周，6 日前

Answer 1

包思远

新手启示者

欢迎讨论

Answer 2

王旭邈

资深光能

NOIP这么难吗？小脑给我干萎缩了

Answer 3

包思远

新手启示者

D

Answer 4

陈俊霖

新手天翼

此题严格弱于T1 。我们学校有位T1 2.5h T2 45min 的大神。

Answer 5

包思远

新手启示者

@陈俊霖

因而我算出最新的菊花公式：（n>=3时成立）

当n=2时，k只能为1，方案数为1（特判一下即可）

上面的菊花公式，n=3,k=1; n=3,k=2; n=4,k=1; n=4,k=2; n=4,k=3; 我都算过了，和实际结果（枚举去重后所得）相比较结果一样。

n>=5时我认为它也是正确的，但我并未手动验证。

Answer 6

陈俊霖

新手天翼

#include<cstdio>
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
int c,n,m,k,U[100050],V[100050];
typedef long long ll;
ll fact[300050],mod=1000000007,Re2=500000004;
vector<int>t[100050];
void solve19(){
scanf("%d%d",&n,&k);
for(int i=1;i<n;i++){
scanf("%d%d",&U[i],&V[i]);
}
for(int i=1,s;i<=k;i++)scanf("%d",&s);
n--;
ll d=ll(n-k)*(n-k-1)%mod*fact[n-2]%mod;
printf("%lld\n",(fact[n]-d+mod)%mod*Re2%mod);
}
ll dfs6(int x,int fr){
ll s=fact[t[x].size()-1];
for(int i=0;i<t[x].size();i++){
if(t[x][i]==fr)continue;
s=s*dfs6(t[x][i],x)%mod;
}
return s;
}
void solve6(){
scanf("%d%d",&n,&k);
for(int i=1;i<n;i++){
scanf("%d%d",&U[i],&V[i]);
t[U[i]].push_back(V[i]);
t[V[i]].push_back(U[i]);
}
int s;
scanf("%d",&s);
ll L=dfs6(U[s],V[s]);
ll R=dfs6(V[s],U[s]);
printf("%d\n",int(L*R%mod));

for(int i=1;i<=n;i++){
t[i].clear();
}
}
void solve(){
if(c==18){
printf("1\n");
return;
}
if(c>=19&&c<=21){
solve19();
return;
}
if(c<=6){
solve6();
return;
}
solve6();
}
int main(){
freopen("traverse.in","r",stdin);
freopen("traverse.out","w",stdout);
int T;
scanf("%d%d",&c,&T);
fact[0]=1;
for(int i=1;i<=200000;i++){
fact[i]=fact[i-1]*i%mod;
}
while(T--){
solve();
}
fclose(stdin);
fclose(stdout);
return 0;
}

这是我考场代码。40pts。

应该是(n！-（n-k-1）(n-k)((n-2)!))/2

思路是容斥，考虑两端都未选中的有向链个数。

Answer 7

包思远

新手启示者

@陈俊霖

这个公式是对的

Answer 8

包思远

新手启示者

@陈俊霖

#include<bits/stdc++.h>
using namespace std;
const int Mod=1e9+7;
int c,T,n,k;
vector<int> g[100005];
vector<int> f;
int fact[100005];
int read(){
    int x=0,sign=1;
    char c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')sign=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*sign;
}
#define r() read()
int cal(){
    int x=((long long)k*fact[n-2])%Mod;
    int y=((((long long)k*(k-1)/2)%Mod)*fact[n-3])%Mod;
    return (x-y+Mod)%Mod;
}
int main(){
    freopen("traverse.in","r",stdin);
    freopen("traverse.out","w",stdout);
    fact[0]=1;
    for(int i=1;i<=100000;i++){
        fact[i]=((long long)fact[i-1]*i)%Mod;
    }
    c=r(),T=r();
    while(T--){
        n=r(),k=r();
        for(int i=1,u,v;i<n;i++){
            u=r(),v=r();
            g[u].push_back(v);
            g[v].push_back(u);
        }
        for(int i=1,e;i<=k;i++){
            e=r();
            f.push_back(e);
        }
        if(c==18)cout<<1<<endl;
        else if(c>=19&&c<=21){
            if(n==2)cout<<1<<endl;
            else{
                if(k==1)cout<<fact[n-2]<<endl;
                else cout<<cal()<<endl;
            }
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

我是这么写的，链和菊花都过了（k=1还没写）

Answer 9

包思远

新手启示者

@陈俊霖

这个结果。。。。。。

我认为，(a-b)%mod=(a%mod-b%mod+mod)%mod是正确的，但我在思考(a/b)%mod=a%mod/b不正确，但(a/b)%mod=a%mod*(mod/b)%mod应该也欠妥

Answer 10

包思远

新手启示者

D

Answer 11

包思远

新手启示者

@陈俊霖

已经40了

Answer 12

包思远

新手启示者

@陈俊霖

我的代码是：

#include<bits/stdc++.h>
using namespace std;
const int Mod=1e9+7;
int c,T,n,k,u[100005],v[100005];
vector<int> g[100005];
vector<int> f;
int fact[100005];
int read(){
    int x=0,sign=1;
    char c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')sign=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*sign;
}
#define r() read()
int cal(){
    int x=((long long)k*fact[n-2])%Mod;
    int y=((((long long)k*(k-1)/2)%Mod)*fact[n-3])%Mod;
    return (x-y+Mod)%Mod;
}
int dfs(int id,int fa){
    int sum=fact[g[id].size()-1];
    for(int i=0;i<g[id].size();i++){
        if(g[id][i]!=fa)sum=((long long)sum*dfs(g[id][i],id))%Mod;
    }
    return sum;
}
int main(){
    freopen("traverse.in","r",stdin);
    freopen("traverse.out","w",stdout);
    fact[0]=1;
    for(int i=1;i<=100000;i++){
        fact[i]=((long long)fact[i-1]*i)%Mod;
    }
    c=r(),T=r();
    while(T--){
        n=r(),k=r();
        for(int i=1;i<n;i++){
            u[i]=r(),v[i]=r();
            g[u[i]].push_back(v[i]);
            g[v[i]].push_back(u[i]);
        }
        for(int i=1,e;i<=k;i++){
            e=r();
            f.push_back(e);
        }
        if(c==18)cout<<1<<endl;
        else if(c>=19&&c<=21){
            if(n==2)cout<<1<<endl;
            else{
                if(k==1)cout<<fact[n-2]<<endl;
                else cout<<cal()<<endl;
            }
        }
        else if(c<=6){
            cout<<((long long)dfs(u[f[0]],v[f[0]])*dfs(v[f[0]],u[f[0]]))%Mod<<endl;
        }
        for(int i=1;i<=n;i++)g[i].clear();
        f.clear();
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

和你的代码思路应该是一样的（k=1时），但通过我的测试发现，

下面这个代码也能40分：

#include<bits/stdc++.h>
using namespace std;
const int Mod=1e9+7;
int c,T,n,k;
vector<int> g[100005];
vector<int> f;
int fact[100005];
int read(){
    int x=0,sign=1;
    char c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')sign=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*sign;
}
#define r() read()
int cal(){
    int x=((long long)k*fact[n-2])%Mod;
    int y=((((long long)k*(k-1)/2)%Mod)*fact[n-3])%Mod;
    return (x-y+Mod)%Mod;
}
int dfs(int id,int fa){
    int sum=fact[g[id].size()-1];
    for(int i=0;i<g[id].size();i++){
        if(g[id][i]!=fa)sum=((long long)sum*dfs(g[id][i],id))%Mod;
    }
    return sum;
}
int main(){
    freopen("traverse.in","r",stdin);
    freopen("traverse.out","w",stdout);
    fact[0]=1;
    for(int i=1;i<=100000;i++){
        fact[i]=((long long)fact[i-1]*i)%Mod;
    }
    c=r(),T=r();
    while(T--){
        n=r(),k=r();
        for(int i=1,u,v;i<n;i++){
            u=r(),v=r();
            g[u].push_back(v);
            g[v].push_back(u);
        }
        for(int i=1,e;i<=k;i++){
            e=r();
            f.push_back(e);
        }
        if(c==18)cout<<1<<endl;
        else if(c>=19&&c<=21){
            if(n==2)cout<<1<<endl;
            else{
                if(k==1)cout<<fact[n-2]<<endl;
                else cout<<cal()<<endl;
            }
        }
        else if(c<=6){
            cout<<dfs(f[0],0)<<endl;
        }
        for(int i=1;i<=n;i++)g[i].clear();
        f.clear();
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

很显然，我认为第一个代码的思路应该才是正解，但是第二个代码为什么40分我也解释不了，很奇怪

Answer 13

王鹏轩

高级守护

大佬们，你们可真厉害啊！

问题标题: 关于NOIP2024第2题

13 个回答: