题解
遍历所有的子集肯定不行,所以我么考虑某些数作为 \(mex\) 的值时的贡献,也就是求 \(i\) 作为 \(mex\) 的值时,有多少子集的 \(mex\) 是 \(i\)
实施
-
对于 \(i \leq n\) ,假设子集选了 \(k_1\) 个小于 \(i\) 的数,\(k_2\) 个大于 \(i\) 的数,则有 \(1+(i-1)-k_1=k_1+k_2\),即 \(i\) 是第 \(k_1+k_2+1\) 个没有被选中的数
-
对于 \(i>n\) ,假设子集选了 \(k\) 个小于 \(i\) 的数,同理有 \(1+(i-1)-k=k+1\)
预处理所有的组合数
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
ll c[5005][5005]={0};
void init()
{
for(int i=0;i<=5000;i++)
{
c[i][0]=1;
c[i][i]=1;
for(int j=1;j<i;j++)
{
c[i][j]=c[i-1][j-1]+c[i-1][j];
c[i][j]%=mod;
}
}
}
void solve()
{
ll n;
cin >> n;
ll ans = 0;
for (ll i = 1; i <= n; i++)
{
for(int k2=0;k2<=n-i;k2++)
{
int k1=i-1-k2;
if(k1%2||k1<0) continue;
k1/=2;
ans+=c[i-1][k1]*c[n-i][k2]%mod*i%mod;
ans%=mod;
}
}
for(ll i=n+1;i<=2*n+1;i++)
{
if(i%2==0) continue;
ll j=(i-1)/2;
ans+=c[n][j]%mod*i%mod;
ans%=mod;
}
cout << ans << '\n';
}
int main()
{
init();
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}
标签:5005,Meow,ll,long,子集,Ultra,mex
From: https://www.cnblogs.com/pure4knowledge/p/18300391