A
题目描述
(n) 个数 (a_i) 分成 (k) 非空集合，若该集合有 (x) 个数能量和为 (y)，产生的代价是 (x imes y)
试问每一种方案产生的代价之和，答案对 (998244353) 取模。
(1leq mleq nleq 10^6)
解法
一开始我是把贡献放在单点上，但是要算一整列的斯特林数（我算不来）
更好的方法是把组合意义用到底，我们考虑把 (x) 这个系数拆成每对 (u,v) 之间的贡献：
算单个斯特林数是很容易的，我们把盒子看成不同，容斥空盒的数量，剩下任意放置：
因为 (x^n) 是完全积性函数，所以可以用欧拉筛 (O(n)) 计算。
总结
本题的贡献是和集合大小有关联的，你可以把它转化成两个单点同时出现在一个集合的贡献。所以算贡献的主体也是要时刻注意的，选定好的主体也许可以让你从源头解决问题。
#include <cstdio>
const int M = 1000005;
const int MOD = 998244353;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,k,sum,ans,fac[M],inv[M];
void init(int n)
{
fac[0]=inv[0]=inv[1]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
for(int i=2;i<=n;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=2;i<=n;i++) inv[i]=inv[i-1]*inv[i]%MOD;
}
int C(int n,int m)
{
if(n<m || m<0) return 0;
return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int qkpow(int a,int b)
{
int r=1;
while(b>0)
{
if(b&1) r=r*a%MOD;
a=a*a%MOD;
b>>=1;
}
return r;
}
int S(int n,int m)
{
int res=0;
for(int i=0;i<m;i++)
{
int f=(i%2)?MOD-1:1;
res=(res+f*C(m,i)%MOD*qkpow(m-i,n))%MOD;
}
return res*inv[m]%MOD;
}
signed main()
{
freopen("ichigo.in","r",stdin);
freopen("ichigo.out","w",stdout);
n=read();k=read();init(n);
ans=S(n,k)+(n-1)*S(n-1,k);ans%=MOD;
for(int i=1;i<=n;i++) sum=(sum+read())%MOD;
printf("%lld
",ans*sum%MOD);
}
D
题目描述
(n) 个点，每个点可以分配一个非负实数权值 (t)，权值和为 (x)，有 (m) 条边 ((u,v))，每一条边贡献是 (t_u imes t_v)，试分配权值使得贡献最大，答案保留 (6) 位小数。
(nleq 40)
解法
考虑调整法，对于任意一种分配方案和两个不相连的点 (u,v)，设与其相连的点权值和分别是 (s_u,s_v)，那么如果 (s_uleq s_v)，可以把 (t_u) 全部加到 (t_v) 上去，答案不变差，如果 (s_u>s_v) 亦然。
这说明了最优方案中两个不相连的点 (u,v) 中有一个 (t) 为 (0)，所以最优方案一定是原图的一个团，应该将点权平均分配，所以如果团的大小是 (k)，那么最大贡献是 (x^2cdotfrac{k(k-1)}{2k^2})
显然最大团是最优的，数据范围启示我们可以折半搜索。设 (f[s]) 表示集合 (s) 的导出子图中最大团，我们枚举后 (n/2) 点的团 (t)，找到所有点的连边的交集 (s')，取 (|t|+f[s]) 就是全图的团。
总结
实数问题可以用调整法来推结论，还是要注意贡献的主体。
为什么本题会有这样的结论？感性理解就是要让点权集中，边的贡献就大，那么团是最优选择。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 45;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k,x,ans,a[M],f[1<<20];
int pd(int s)
{
for(int i=0;i<n;i++)
if((s>>i&1) && (s&a[i])!=s)
return 0;
return __builtin_popcountll(s);
}
signed main()
{
freopen("nanami.in","r",stdin);
freopen("nanami.out","w",stdout);
n=read();m=read();x=read();
for(int i=0;i<n;i++) a[i]|=1ll<<i;
for(int i=1;i<=m;i++)
{
int u=read()-1,v=read()-1;
a[u]|=1ll<<v;a[v]|=1ll<<u;
}
k=n/2;
for(int s=0;s<(1ll<<k);s++)
{
f[s]=pd(s);
for(int i=0;i<k;i++) if(s>>i&1)
f[s]=max(f[s],f[s^(1ll<<i)]);
}
for(int t=0;t<(1ll<<n-k);t++)
{
int s=(1ll<<k)-1;
for(int j=0;j<n-k;j++) if(t>>j&1)
s&=a[j+k];
ans=max(ans,f[s]+pd(t<<k));
}
double r=x*x*(ans-1)/(2.0*ans);
printf("%.6f
",r);
}