2019.3.2
三元环计数
有2种方法：假设有$m$条边
法1:将每一个点分为2类，第一类点的度数$ <= \sqrt{m}$，第二类度数$ >= \sqrt{m}$
对于第一类点，暴力枚举这个点的2条向外连的边，然后看这两条边指向的点有没有连边
对于第二类点，个数不超过$ >= \sqrt{m}$，所以这几个点立方级连边即可
这种方法要用到哈希表，常数很大
法2:将每一条边定向，从度数小的点连向度数大的点。如果度数相同则从编号小的连向编号大的
然后枚举每个点$i$，枚举$i$的出点$j$，打上值为$i$的标记对于每个枚举的$j$，暴力枚举出点$k$
，若$k$有$i$的标记，则证明”$i$有一条出边指向$k$"，统计答案
这样子是$O(m\sqrt{m})$的，为什么？
分度数$<=\sqrt{m}$ 和$ >= \sqrt{m}$ 讨论
我们发现耗在每一条边时间可以写成:$out[v[1]]+out[v[2]]+....+out[v[m]]$，其中$v[i]$表示第$i$条边的“出点”，$out[i]$表示第i个点的出度
对于$out[v[]]<=\sqrt{m}$的边，我们发现每一个$out[v[]]$卡到最大是$\sqrt{m}$，$m$个数的时间复杂度不会超过$O(m\sqrt{m})$
对于$out[v[]]>\sqrt{m}$的边，似乎不是很好分析
我们发现度数$>\sqrt{m}$的点至多只有$\sqrt{m}$个，而这些点只可能向度数更大的点连边，所以出度不超过$\sqrt{m}$
而且度数$<=\sqrt{m}$的点本来出度就不超过$\sqrt{m}$
所以每一个点的出度不超过$\sqrt{m}$
这样就对了
代码：
while(m--){ int x,y; scanf("%d%d",&x,&y); e1[++ct]=x; e2[ct]=y; ot[x]++; in[y]++; } for(int i=1;i<=ct;i++){ int p=(in[e1[i]] 例题：jzoj5803. 【2018.8.12省选模拟】girls
其实这题不是完全意义上的三元环计数
前面还要求出含0条，1条，2条边的答案
然后再对现在的含3条边的答案进行容斥，才是最终结果
6.26
杨表求lis期望值
等会填坑
7.1
excrt
这个算法我去年就学过，但是因为自己弱，一直没时间实现
考虑把2个方程组$x%a=b$ $x%c=d$合成一个
设e,f满足$a*e+b=x$且$c*f+d=x$
联立两个方程，得到$a*e-c*f=d-b$
然后使用exgcd解出e,f，将e,f都乘以$(d-b)/gcd(a,c)$
然后使用一些方法将e,f都变为自然数
然后将e,f代入原方程，变为$x mod (lcm(a,b))=(a*e+b)$即可
注意将e,f变成自然数的过程中要特判0
太菜了，模板题都没有ac
7.2
kummer定理
$C^n_{n+m}$含$p$的幂次个数为$n+m$在$p$进制下的进位次数
证明：可以从阶乘中含p的次数和组合数的定义推导出$C^n_{n+m}$含p的幂次数为
（太菜不怎么会latex，图片copy自网络）
注意到上面式子中，$m+n$，$m$，$n$除以$p^i$后，等价于将这些数在p进制下的表示都去掉$i$位
并且发现对于每一个i，$[\frac{m+n}{p^i}]-[\frac{n}{p^i}]-[\frac{m}{p^i}]$的值只可能等于0或1
然后将$n$，$m$去掉$i$位后累加
当去掉i位后，$[\frac{m+n}{p^i}]-[\frac{n}{p^i}]-[\frac{m}{p^i}]$的值为1，那就代表后面的数对现在进位，导致相差为1
所以，每一次进位就对应$[\frac{m+n}{p^i}]-[\frac{n}{p^i}]-[\frac{m}{p^i}]$的值为1，恰好一一对应，得证
例题：
jzoj6170. 【GDSOI 2019 day2】高中生数学题 （难题）
套上一个kummer定理进行dp
毒瘤，我原来想错了3次，暴力dp还不行，得用数学方法推公式优化，极其恶心
细细体会
#includeusing namespace std;typedef long long ll;ll n,p,kk,f[100][100][2][2],ans,a[110];int ct;int main(){ freopen("math.in","r",stdin); freopen("math.out","w",stdout); scanf("%lld%lld%lld",&n,&p,&kk); if(p==1){ printf("%lld",n); return 0; } f[0][0][0][1]=1; while(n){ a[++ct]=n%p; n/=p; } reverse(a+1,a+ct+1); for(int i=0;i
jzoj5330. 【NOIP2017提高A组模拟8.22】密码 （难题）
比上一道题更加毒瘤
基本思路是，首先高精度除法将n转换为p进制数
枚举状态中，要尝试枚举竖式加法式子下端的数
然后可以计算出竖式最上端的数的范围，同数字取值范围取交集，然后统计答案。。。。
然而不能枚举竖式式子下面的数，因为枚举时间会爆炸。。。。。
然后发现每当下面数+1，一个限定区间会右移一格，于是等差数列求和。。。还要分段计算，根据程序中nv的取值$0,-1,p-1,p$分4种情况讨论。。。。
然后还要滚动数组优化
有毒。。。。。。。。。
细细体会
#includeusing namespace std;typedef long long ll;#define mo 1000000007llll p,kk,f[2][4010][2][2],ans,a[4010],d[4010],t[100010];char c[100010];int ct;ll mod(){ ll ans=0; for(int i=d[0];i>=1;i--) ans=(ans*10+d[i])%p; return ans;}ll s(ll x){ return (x*(x+1ll)/2ll)%mo;}ll ss(ll x,ll y){ return (s(y)-s(x-1ll)+mo)%mo;}ll div(){ ll ans=0,ok=0,ct=0; for(int i=d[0];i>=1;i--){ ans=(ans*10+d[i]); if(!ok&&ans>=p){ t[++ct]=ans/p; ans%=p; ok=1; } else if(!ok&&ans