3月12日考试总结

T1

得分情况 :

预计分数 : 0pts
实际得分 : 0pts
大样例没过的\(O(n^4)\)DP , 并没有分

正解 :

考虑合法情况 , 就是\(gcd(a_1...a_n)=1\)的\(a\)序列
并不好直接搞 , 用容斥做
整理出容斥式 :

然后整除分块做

等一下!
这个\(n\)有\(1e9\)!
\(\mu\)的前缀和不能直接线筛
好8 , 掏出自己的杜教筛板子

再等一下!

你看这个模数 是不是不大对劲?
发现\(453682211 = 47*47*59*59*59\) S.H.I.T
于是你还得掏出ExLucas

完事 , 上代码 :

#include<bits/stdc++.h>
#define MAXN(a) ((max##a)+10)
using namespace std;

typedef long long ll;
const int mod=453682211;

struct HashMap{...};

namespace Math{
	inline ll slow_mul(ll a,ll b,ll mod){...}
	ll exgcd(ll a,ll b,ll &x,ll &y){...}
	ll excrt(int n,ll *A,ll *B){...}
	inline ll quick_pow(ll a,ll b,ll mod){...}
	inline ll inv(ll a,ll b){...}
	namespace ExLucas{
		ll pref[2][220000];
		inline void Pre_Work(){...}
		ll fac(ll n,ll pi,ll pk){...}
		ll C(ll n,ll m,ll pi,ll pk){...}
		ll C(ll n,ll m){...}
	}
	namespace Sum{
		HashMap Map;
		const int maxS=5000000;
		int cnt,prim[MAXN(S)];
		ll mu[MAXN(S)];
		bool bok[MAXN(S)];
		inline void Eula(){...}
		ll get_mu(ll x){...}
	}
	inline void Pre_Work(){
		Sum::Eula();
		ExLucas::Pre_Work();
	}
}

using Math::ExLucas::C;
using Math::Sum::get_mu;

ll n,m,a,b;

inline ll calc(ll n,ll m){
	ll ans=0,N=n-1;
	for(ll l=1,r;l<=N;l=r+1)
		r=N/(N/l),ans=(ans+( C((N/l)+1,m) * (get_mu(r)-get_mu(l-1)) % mod ))%mod;
	ans=(ans+( C(N/n+1,m) * (get_mu(n)-get_mu(n-1)) % mod ))%mod;
	return (ans%mod+mod)%mod;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("brain.in","r",stdin);
	freopen("brain.out","w",stdout);
#endif
	Math::Pre_Work();
	scanf("%lld %lld %lld %lld",&n,&m,&a,&b);
	printf("%lld\n",calc(n,m));
	return 0;
}

把板子的部分丢上去会死人的

T2

得分情况 :

预计分数 : 15pts
实际得分 : 15pts
暴力搜就完事了

正解 :

在路上了quq

T3

得分情况 :

预计分数 : 20pts
实际得分 : 20pts
暴力模拟就完事了

正解 :

不会多项式 , 死在路上了quq