5/15测试

写在前面

我太菜了

T1 方程的解（equation.cpp）

题目大意

对于不定方程\(a_1+a_2+…a_{k-1}+a_k=g(x)\)，其中\(k≥2\)且\(k∈N^*\)，\(x\) 是正整数，\(g(x)=x^x mod 1000, x,k\)是给定的数。我们要求的是这个不定方程的正整数解组数。
对于\(40\%\)的数据，\(ans≤10^{16}；\)
对于\(100\%\)的数据，\(k≤100，x≤2^{31}-1，k≤g（x）\)

Sol

第一步求\(g(x)\)，很简单的快速幂。
然后题目就转化为了\(g(x)\)个苹果放入\(k\)个不同的盘中，求方案数。标准的插板法，答案就是\(C_{g(x)-1}^{k-1}\)。
由于我太菜了不确定自己写的扩欧对不对，加上数据小，直接用递推式\(C_i^j=C_{i-1}^{j-1}+C_{i-1}^{j}\)，\(40\)分到手。
剩下的六十分套一个高精加就可以了，扩欧求要用高精乘。然而我菜，估算得\(ans_{max}≈10^{157}\)，所以淼一个手写\(INT\_576\)即可。
代码超\(\%80\)都是复制粘贴，放上精华部分

f[upo][dowm][0]=f[upo-1][dowm-1][0]+f[upo][dowm-1][0];//懒得写高精，淼一个高低位爬了 
f[upo][dowm][1]=f[upo-1][dowm-1][1]+f[upo][dowm-1][1]+f[upo][dowm][0]/exc;
f[upo][dowm][2]=f[upo-1][dowm-1][2]+f[upo][dowm-1][2]+f[upo][dowm][1]/exc;
f[upo][dowm][3]=f[upo-1][dowm-1][3]+f[upo][dowm-1][3]+f[upo][dowm][2]/exc;
f[upo][dowm][4]=f[upo-1][dowm-1][4]+f[upo][dowm-1][4]+f[upo][dowm][3]/exc;
f[upo][dowm][5]=f[upo-1][dowm-1][5]+f[upo][dowm-1][5]+f[upo][dowm][4]/exc;
f[upo][dowm][6]=f[upo-1][dowm-1][6]+f[upo][dowm-1][6]+f[upo][dowm][5]/exc;
f[upo][dowm][7]=f[upo-1][dowm-1][7]+f[upo][dowm-1][7]+f[upo][dowm][6]/exc;
f[upo][dowm][8]=f[upo-1][dowm-1][8]+f[upo][dowm-1][8]+f[upo][dowm][7]/exc;
f[upo][dowm][7]%=exc;
f[upo][dowm][6]%=exc;
f[upo][dowm][5]%=exc;
f[upo][dowm][4]%=exc;
f[upo][dowm][3]%=exc;
f[upo][dowm][2]%=exc;
f[upo][dowm][1]%=exc;
f[upo][dowm][0]%=exc;

T2 礼物(gift.cpp)

题目大意

商店里一共有种礼物。夏川每得到一种礼物，就会获得相应喜悦值\(W_i\)（每种礼物的喜悦值不能重复获得）。
每次，店员会按照一定的概率\(P_i\)（或者不拿出礼物），将第\(i\)种礼物拿出来。
季堂每次都会将店员拿出来的礼物买下来。没有拿出来视为什么都没有买到，也算一次购买。
求夏川能获得的最大喜悦值以及使夏川获得最大喜悦值的期望购买次数。
对于\(100\%\)的数据，\(N≤20\;,0<W_i ≤ 10^9\;,0 < P_i ≤ 1\)且\(\sum_{P_i}≤1\)

Sol

显然最大喜悦值就是所有礼物喜悦值之和。
那么问题就转化为了把所有物品都抽到一遍的期望值。
由于\(n\)很小，考虑状压。
显然就是这样

inline double f(int now)
{
    if(now==0)return 0.0;
    if(dp[now])return dp[now];
    double ans=1,pn=0;
    for(int i=0;i<20;i++)
    {
	if(mi[i]&now)
	{
	    ans+=p[i+1]*f(mi[i]^now);
	    pn+=p[i+1];
	}
    }
    return dp[now]=ans/pn;
}

我太菜了解释不来状压方程。

5/15测试

原文：https://www.cnblogs.com/orzlsw/p/14772066.html