赛时 rank 19,T1 0,T2 25 T3 10 T4 100
T3 挂了10pts?
数学专场，套路专场，烧脑专场。
幸亏我还有缓存的李超树博客，最后一个小时就溜了去打数据结构。
数学好难，拜谢数学。
T1 黑暗型高松灯
要用势能分析，鞅的停时定理。由于赛时这个放T1非常逆天，所以整场比赛的奖励也十分逆天。
不会做，跳了。
T2 速度型高松灯
按位考虑，矩阵快速幂。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
#define int long long
int n,mod;
struct matrix{
int s[3][3];
matrix operator*(matrix a){
matrix ans;
memset(ans.s,0,sizeof ans.s);
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)
ans.s[i][j]=((ans.s[i][j]+a.s[i][k]*s[k][j])%mod+mod)%mod;
return ans;
}
}ans,base,k;
inline matrix new_one(){
matrix a;
memset(a.s,0,sizeof a.s);
for(int i=0;i<3;i++)a.s[i][i]=1;
return a;
}
inline matrix ksm(matrix a,int b){
matrix ans = new_one();
for(;b;b >>= 1,a = a*a)
if(b&1)ans = ans*a;
return ans;
}
__int128_t ten[22];
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
cin>>n>>mod;
n++;
ten[0]=1;
for(int i=1;i<=20;i++)ten[i]=ten[i-1]*10;
memset(base.s,0,sizeof base.s);
k.s[0][0]=0,k.s[1][0]=0,k.s[2][0]=1;
base.s[0][2]=1,base.s[1][2]=1,base.s[2][1]=-1,base.s[2][2]=2;
for(int i=1;i<=(int)ceil(1+log(n)/log(10.0));i++){
base.s[0][0]=ten[i]%mod;
if(n<ten[i]){
k=k*ksm(base,n-ten[i-1]);
return cout<<k.s[0][0],0;
}k=k*ksm(base,ten[i]-ten[i-1]);
}
}
T3 力量型高松灯
莫反，有个恶心的\((i+j)^k\)
\[\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\mu^2(\gcd(i,j))\gcd(i,j)\\ =&\sum_{d=1}^n\mu^2(d)d\sum_{i=1}^n\sum_{j=1}^n(i+j)^k[\gcd(i,j)=d]\\ =&\sum_{d=1}^n\mu^2(d)d^{k+1}\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}(i+j)^k[\gcd(i,j)=1]\\ =&\sum_{d=1}^n\mu^2(d)d^{k+1}\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}(i+j)^k\sum_{e|i,e|j}\mu(e)\\ =&\sum_{e=1}^n\mu(e)e^k\sum_{d=1}^{\lfloor\frac ne\rfloor}\mu^2(d)d^{k+1}\sum_{i=1}^{\lfloor\frac n{de}\rfloor}\sum_{j=1}^{\lfloor\frac n{de}\rfloor}(i+j)^k\\ =&\sum_{T=1}^nS\left(\left\lfloor\frac nT\right\rfloor\right)T^k\sum_{d|T}\mu^2(d)\mu\left(\frac Td\right)d \end{aligned} \]其中 \(S(n)=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\)。
考虑如何求\(S(n)\)
设\(F(n) = \sum_{i=1}^ni^k,G(n)=\sum_{i=1}^nF(i)\)，那么\(S(n)=G(2n)-2G(n)\)
线筛加前缀和就可以了
考虑后面的\(\sum_{d|T}\mu^2(d)\mu\left(\frac Td\right)d\)怎么求
我们设T有一个质因数p，若\(T=p^{3\,or\,more }\times sth.\)，那么后面的就是0。
然后就没了
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
#define int long long
const int N = 1e7 + 10,mod = 998244353;
bitset<N> pd;
vector<int> prime;
int f[N],F[N],n,k;
inline int power(int a,int b,int mod){
int res = 1;
while(b){
if(b&1) res = 1ll * res * a % mod;
b >>= 1;
a = 1ll * a * a % mod;
}
return res;
}
inline void Sieve(int n) {
f[1] = F[1] = 1;
for(int i = 2; i <= n; ++i) {
if(!pd[i]) prime.push_back(i),f[i] = i - 1,F[i] = power(i,k,mod);
for(auto j : prime) {
if(i * j > n) break;
int p = i * j;
pd[p] = true;
F[p] = 1ll * F[i] * F[j] % mod;
if(i % j == 0) {
int q = i / j;
if(q % j) f[p] = 1ll * (mod - j) * f[q] % mod;
break;
}
f[p] = 1ll * f[i] * (j - 1) % mod;
}
}
for(int i = 2; i <= n; ++i) f[i] = (f[i - 1] + 1ll * f[i] * F[i] % mod) % mod,F[i] = (F[i] + F[i - 1]) % mod;
for(int i = 2; i <= n; ++i) F[i] = (F[i] + F[i - 1]) % mod;
}
inline int solve(int n){return (F[n<<1] - 2ll*F[n]%mod + mod)%mod;}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
cin>>n>>k;k %= (mod-1);
Sieve(n<<1);
ll ans = 0;
for(int l = 1,r;l <= n;l = r + 1){
r = n / (n / l);
ans = (ans + 1ll * (f[r]-f[l-1]+mod)%mod*solve(n/l)%mod)%mod;
}
cout<<ans;
}
T4 高松灯
贪心。
从低到高填9，计算答案即可。
特判第一位，如果后面的超限，那么就填第一位的数字-1，反之就填第一位的数字。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
ll n;cin>>n;
ll ans = 0;
bool flag = true;
while(n > 9){
int x = n % 10;
if(x != 9) flag = false;
ans += 9;
n /= 10;
}
ans += (flag?n:n-1);
cout<<ans;
}
总结
逆天模拟赛
标签：10,int,sum,long,集训,FILE,using,csp,mod From： https://www.cnblogs.com/hzoi-Cu/p/18328603