一个常数和复杂度都很大的题解 令 为 在 个球中选 组的方案数，则显然有转移 然后考虑对其优化：令 为 的生成函数，则 只与 和 有关，且关系为 .然后考虑对上式进行矩阵加速递推，复杂度 ，再加一个巨大的常数，但此题 的范围很小，可以通过。 代码： #include<bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define Fast_IO ios::sync_with_stdio(false); #define fir first #...

数论函数 定义域为整数，值域为复数的函数 积性函数：若 ，则 除数函数 除数函数为积性函数。 欧拉函数 表示不超过 且与 互质的正整数的个数 其中 是 的标准分解。由此易见 函数是积性函数。同时满足 线性求 函数： #define int long long int phi[3000005]; int n=3000000; bool mark[3000005]; int prime[1000005]; int tot; void getphi() { phi[1]=1; for(int i=2;i<=n;i++) { ...

为什么第3题O(n)算法只有40分？ #include<bits/stdc++.h> using namespace std; #define mod 10007 #define ll long long int main() { ll n,m; cin>>n>>m; ll a=m%mod; ll b=a*(m-1)%mod; ll c=b*(m-2)%mod; for(int i=4;i<=n;++i) { a=(b*(m-1)+c*(m-2))%mod; b=c...