专项测试(数学1)

今天模拟赛考得没有感觉,感觉数学专题没用到数学......

T1 young

做这个题,本来以为摇摆兵可以早一点切掉,然后让他帮帮我来着

结果他就比我早了一分钟,并且我们两个同时写出了答案相同的错误代码呃呃

好难的亚子

image

该说的题解都说了,我这里给出p的求法

哎呀算了算了直接看代码吧

code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int read(){
    int s=0,t=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();}
    while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
    return s*t;
}
const int mod=258280327;
const int N=51;
const int M=9;
int ksm(int x,int y){
    int ret=1;
    while(y){
        if(y&1)ret=ret*x%mod;
        x=x*x%mod;y>>=1;
    }return ret;
}
int n,m,ans;
int f[N][M],g[N][N][M],p[N][N][M][1<<M];
int jc[N],inv[N],pw2[(N+1)*M];
int C(int x,int y){return jc[x]*inv[y]%mod*inv[x-y]%mod;}
int P(int s,int t,int m,int k){
    if(!m)return 1;
    if(!s||!t)return pw2[(s+t)*m];
    if(!k)return pw2[(s+t)*m];
    if(p[s][t][m][k]!=-1)return p[s][t][m][k];
    if((k>>m-1)&1)return p[s][t][m][k]=P(s,t,m-1,k^(1<<(m-1)))*2%mod;
    int ret=0;
    fo(i,0,s)fo(j,0,t){
        int res=C(s,i)*C(t,j)%mod;
        res=res*P(i,j,m-1,k)%mod*P(s-i,t-j,m-1,k)%mod;
        if((i&&j)||(s-i&&t-j))ret=(ret+res)%mod;
    }
    ret=(ret+2*P(s,t,m-1,0))%mod;
    return p[s][t][m][k]=ret;
}
int G(int s,int t,int m){
    if(!s||!t||!m)return 0;
    if(g[s][t][m]!=-1)return g[s][t][m];
    int ret=0;
    fo(k,1,(1<<m)-1)ret=(ret+P(s,t,m,k))%mod;
    return g[s][t][m]=ret;
}
int F(int n,int m){
    if(!m||n<=1)return 0;
    if(f[n][m]!=-1)return f[n][m];
    int ret=0;//cout<<"SB"<<endl;
    fo(i,0,n){
        int res=0;
        if(i)res=(res+pw2[(n-i)*(m-1)]*F(i,m-1))%mod;
        if(n-i)res=(res+pw2[i*(m-1)]*F(n-i,m-1))%mod;
        if(i&&(n-i))res=(res+pw2[(n+1)*(m-1)]+G(i,n-i,m-1))%mod;
        ret=(ret+res*C(n,i))%mod;
    }
    return f[n][m]=ret;
}
signed main(){
    n=read();m=read();
    memset(f,-1,sizeof(f));
    memset(g,-1,sizeof(g));
    memset(p,-1,sizeof(p));
    pw2[0]=1;fo(i,1,(n+1)*m)pw2[i]=pw2[i-1]*2%mod;
    jc[0]=1;fo(i,1,n)jc[i]=jc[i-1]*i%mod;
    inv[0]=1;inv[n]=ksm(jc[n],mod-2);
    fu(i,n-1,1)inv[i]=inv[i+1]*(i+1)%mod;
    ans=F(n,m)*ksm(pw2[n*m],mod-2)%mod;
    // cout<<F(n,m)<<" "<<pw2[n*m]<<endl;
    // cout<<G(2,2,2)<<endl;
    // cout<<P(3,3,3,1)<<endl;
    //1 1 2 1 : 
    // ans=24ll*ksm(16,mod-2)%mod;
    printf("%lld",ans);
}

T2 Simple

\(f(n)\)\(n\)位钦定数的个数

答案为\(\sum\limits_{i=1}^{n}i^2f(i)\)

image

这个东西其实是个莫比乌斯反演

我们直接化简它,得到

\[\sum\limits_{d=1}^{n}d*\mu(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d} \right\rfloor}i*10^i
\]

我们发现后面这个咋也不能杜教筛,但是前面那个却可以,于是调换个顺序

\[\sum\limits_{i=1}^{n}i*10^i\sum\limits_{d=1}^{\left\lfloor\frac{n}{i} \right\rfloor}d*\mu(d)
\]

后面这个直接卷上一个\(id\)就能杜教筛了

前面那个有通项公式,直接\(OEIS\)

其实乘一个\(10\)然后两个一消就完事了,被七百信一眼切了,我和摇摆兵玩了一个小时没玩明白

code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int read(){
    int s=0,t=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();}
    while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
    return s*t;
}
const int mod=258280327;
const int N=1e7+5;
int ksm(int x,int y){
    int ret=1;
    while(y){
        if(y&1)ret=ret*x%mod;
        x=x*x%mod;y>>=1;
    }return ret;
}
int n,ans;
signed p[N],cnt,R=1e7;
bool vis[N];
int ss[N],iv,i2;
void init(){
    ss[1]=1;
    fo(i,2,R){
        if(!vis[i])p[++cnt]=i,ss[i]=-1;
        for(int j=1;j<=cnt&&i*p[j]<=R;j++){
            vis[i*p[j]]=true;
            if(i%p[j]==0){ss[i*p[j]]=0;break;}
            else ss[i*p[j]]=-ss[i];
        }
    }
    fo(i,1,R)ss[i]=(1ll*ss[i-1]+1ll*i*ss[i]%mod+mod)%mod;
}
int f(int x){return ((9*x-1)%mod*ksm(10,x)%mod+1+mod)%mod*10%mod*iv%mod;}
unordered_map<int,int> mp;
int t(int x){x%=mod;return x*(x+1)%mod*i2%mod;}
int S(int x){
    if(x<=R)return ss[x];
    if(mp.find(x)!=mp.end())return mp[x];
    int ret=1;
    for(int l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        ret=(ret-(t(r)-t(l-1)+mod)*S(x/l)%mod+mod)%mod;
    }return mp[x]=ret;
}
signed main(){
    n=read();init();iv=ksm(81,mod-2);
    i2=ksm(2,mod-2);
    for(int l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        ans=(ans+(f(r)-f(l-1)+mod)*S(n/l))%mod;
    }
    printf("%lld",ans);
    return 0;
}

T3 mate

组合数取模嘛

能直接做的直接做,能\(CRT\)的就\(CRT\),再不济就分解质因数,到点了就输出0

于是乎就切了

正解是线段树维护质因子,因为最后的式子只有一个会变化,所以我们直接用线段树单点修,全局查就行了

code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int read(){
    int s=0,t=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();}
    while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
    return s*t;
}
const int N=1e6+5;
int n,mod,xpos,ypos;
int p[N],cnt,R=1e6,buc[N],bmo[N];
bool vis[N];
int mo[N],cmo,an[N],ans;
void init(){
    fo(i,2,R){
        if(!vis[i])p[++cnt]=i;
        for(int j=1;j<=cnt&&i*p[j]<=R;j++){
            vis[i*p[j]]=true;
            if(i%p[j]==0)continue;
        }
    }
}
int jc[15][N],inv[15][N];
int w(int x,int y,int i){return x>=y?jc[i][x]*inv[i][y]%mo[i]*inv[i][x-y]%mo[i]:0;}
int C(int x,int y,int i){if(y==0)return 1;return C(x/mo[i],y/mo[i],i)*w(x%mo[i],y%mo[i],i)%mo[i];}
int ksm(int x,int y,int mod){
    int ret=1;
    while(y){
        if(y&1)ret=ret*x%mod;
        x=x*x%mod;y>>=1;
    }return ret;
}
void spj_init(){
    fo(i,1,cmo){
        int mn=min(n,mo[i]-1);
        jc[i][0]=1;fo(j,1,mn)jc[i][j]=jc[i][j-1]*j%mo[i];
        inv[i][0]=1;inv[i][mn]=ksm(jc[i][mn],mo[i]-2,mo[i]);
        fu(j,mn-1,1)inv[i][j]=inv[i][j+1]*(j+1)%mo[i];
    }
}
void spj1(){
    spj_init();ans=0;
    fo(i,xpos,n-ypos){
        if((i+xpos)&1)continue;
        ans=(ans+C(n,i,1)*C(i,(xpos+i)>>1,1)%mo[1]*C(n-i,(n-i+ypos)>>1,1))%mo[1];
    }
    printf("%lld",ans);
}
int exgcd(int a,int b,int &x,int &y){
    if(!b)return x=1,y=0,a;
    int g=exgcd(b,a%b,x,y),t=x;
    x=y;y=t-a/b*y;return g;
}
void spj2(){
    spj_init();ans=0;
    int sum=1;
    fo(j,1,cmo){
        fo(i,xpos,n-ypos){
            if((i+xpos)&1)continue;
            an[j]=(an[j]+C(n,i,j)*C(i,(xpos+i)>>1,j)%mo[j]*C(n-i,(n-i+ypos)>>1,j))%mo[j];
        }sum*=mo[j];
    }
    fo(i,1,cmo){
        int m=sum/mo[i],x,y;
        exgcd(mo[i],m,x,y);
        ans=(ans+y%sum*m%sum*an[i])%sum;
    }
    ans=(ans+sum)%sum;
    printf("%lld",ans);
}
void CC(int x,int y){
    fo(i,1,cnt){
        if(p[i]>x)break;
        int now=x;
        while(now)buc[i]+=now/p[i],now/=p[i];
    }
    fo(i,1,cnt){
        if(p[i]>y)break;
        int now=y;
        while(now)buc[i]-=now/p[i],now/=p[i];
    }
    fo(i,1,cnt){
        if(p[i]>x-y)break;
        int now=x-y;
        while(now)buc[i]-=now/p[i],now/=p[i];
    }
}
signed main(){
    n=read();mod=read();init();
    xpos=abs(read());ypos=abs(read());
    if(n<xpos+ypos||((n+xpos+ypos)&1)||mod==1){printf("0");return 0;}
    int fl=0,tmp=mod;
    for(int i=1;p[i]*p[i]<=mod;i++){
        if(mod%p[i]==0)mod/=p[i],fl=max(fl,2ll),mo[++cmo]=p[i];
        while(mod%p[i]==0)mod/=p[i],fl=max(fl,3ll);
    }
    if(mod>1)fl=max(fl,1ll),mo[++cmo]=mod;
    if(fl!=1&&n>90000){printf("0");return 0;}
    if(fl==1){spj1();return 0;}
    if(fl==2){spj2();return 0;}
    mod=tmp;
    fo(i,xpos,n-ypos){
        if((xpos+i)&1)continue;
        int res=1;
        CC(n,i);CC(i,(xpos+i)>>1);CC(n-i,(n-i+ypos)>>1);
        fo(i,1,cnt)res=res*ksm(p[i],buc[i],mod)%mod,buc[i]=0;
        ans=(ans+res)%mod;
    }
    printf("%lld",ans);
    return 0;
}

QQ:2953174821

推荐这些文章:

专项测试(数学3)

今天非常生气,本来要爆摇摆兵50分的结果只爆了20分......
T1 解方程
这就是一个\(exlucas\)的板子
然而当年这个板子是我硬拍过去的...

code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int read(){
int s=0,t=1;char ch=getchar();
...

专项测试(数学2)

这我今天补昨天的博客,真是可怜,昨晚\(21:40:05\)改完的题......

这一场还是很好的一场,因为我没切题...其实我还挺郁闷的
如何才能让我前两个题多测没换行痛失30分,没事一共就得了30分,加起来也就60
T1 猜拳游戏
一遇到这种最优策略的问题,我是这样的:
题意:两个人都绝顶聪明!
我:我没他俩聪明......
题意:两个人采取最优策略!
我:最优策略是啥??我不知道啊,也没人告诉我最优策略是啥啊?
题意:要赢!
我:咋我的策略是赢,然后概率不对嘞
对面摇摆兵:有的时候不输就行了
于是发现平局对答案没有影响,我们设赢的概率为\(p\),输的概率是\(r\),那么最后我们转...

专项测试 数学4

A. 传统题
让求的答案为 \(\sum\limits_{i=1}^niF(i)\)
\(F(i)\) 为答案为 \(i\) 的方案数
直接求不好求,可以简单转化一下变成 \(\sum\limits_{i=1}^n(m^n-F(ans<i))\)
那么考虑求 \(\sum\limits_{i=1}^nF(ans<i)\rightarrow\sum\limits_{i=0}^{n-1}F(ans\leq i)\)
枚举最后的答案分成了 \(j\) 段就是 \(\sum\limits_{i=0}^n\sum\limits_{j=1}^nm*(m-1)^{j-1}\)
每段的颜色都不和...

专项测试 数学1

A. young
要求期望下最小生成树的权值
由于异或,所以考虑二进制拆分,分别考虑每一位的贡献
在当前这一位,肯定是将这一位是 \(1\) 的放在一起,是 \(0\) 的放在一起,然后两块之间再连 \(1\) 条边让他们联通起来
那么设 \(f_{n,m}\) 表示在一共 \(n\) 个点权值范围为 \(0\) 到 \(2^m-1\) 的所有情况最小生成树和
那么根据上面说的可以把贡献拆成两部分
1.块内的连边
2.块之间的连边
第一部分可以递归解决,第二部分需要再搞一个 \(dp\) ,设 \(g_{s,t,m}\) 表示一边 \(s\) 个点另一边 \(t\) 个点,权值范围为 \(0...

数学/数论专题-专项训练:矩阵相关#1

目录1. 前言2. 题单P5343 【XR-1】分块P5789 [TJOI2017]可乐(数据加强版)P5337 [TJOI2019]甲苯先生的字符串3. 总结
1. 前言
本篇文章是作者学习矩阵的时候的一些相关训练。
注意作者是个 OIer,因此并不会涉及到线性代数知识(或者说是很少)。
前置知识:矩阵快速幂
2. 题单
题单:

P5343 【XR-1】分块
P5789 [TJOI2017]可乐(数据加强版)
P5337 [TJOI2019]甲苯先生的字符串

P5343 【XR-1】分块
显然这道题并不是分块
首先我们需要预处理出来有哪些块长是 xht37 可以分的,这里记作 \(a\...

数学/数论专题-专项训练:欧拉函数

@目录1. 前言2. 练习题P2568 GCDP2398 GCD SUM3. 总结
1. 前言
本篇博文是欧拉函数的专项训练。
其实一般数论的题目就是推式子难,式子推出来了代码都好打。
如果您没有学过欧拉函数,可以看一看我的这篇博文:数论专题-学习笔记:欧拉函数
这里放一下欧拉函数的 8 个性质:

基本性质 1:若 \(p\) 为质数,那么 \(\varphi(p)=p-1\)。特别的,\(\varphi(1)=1\)。
基本性质 2:设 \(n = p^k\) 且 \(p\) 为质数,那么:\[\varphi(n)=n-\dfrac{n}{k}=n-p^{k-1}=p^{k-1} \ti...

luogu P2260 [清华集训2012]模积和 |数论分块

题目描述

\(\sum_{i=1}^{n} \sum_{j=1}^{m} (n \bmod i) \times (m \bmod j), i \neq j\) mod 19940417 的值
输入格式
输入只有一行两个整数 \(n\),\(m\)。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define int long long
const int mod=19940417;
inline int ksm(int x,int y){
int...

【墨鳌】【LCP 22. 黑白方格画】

组合数学
\(O(N\cdot M)\)
class Solution {
public:
int f[10][10];

int C(int n, int m) {
if (n == m || m == 0) return 1;
return f[n][m] = C(n - 1, m - 1) + C(n - 1, m);
}

int paintingPlan(int n, int k) {
if (k == 0 || k == n * n) return 1;
int ans = 0;
...

51nod 1120 机器人走方格 V3 |卢卡斯定理+卡特兰数列

N * N的方格,从左上到右下画一条线。一个机器人从左上走到右下,只能向右或向下走。并要求只能在这条线的上面或下面走,不能穿越这条线,有多少种不同的走法?由于方法数量可能很大,只需要输出Mod 10007的结果。
输入
输入一个数N(2 <= N <= 10^9)。
输出
输出走法的数量 Mod 10007。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstdlib&g...

【luogu P4721】【模板】分治 FFT(NTT)(多项式求逆 / cdq分治)

【模板】分治 FFT
题目链接:luogu P4721
题目大意
给你多项式 \(G\) 满足 \(G_0=0\)。
然后要你求多项式 \(F\) 的前 \(n\) 项满足:\(F_{i}=\sum\limits_{j=1}^iF_{i-j}G_j\)。
思路
cdq分治
你会发现对于一个你要求的范围 \([l,r]\),你如果求出了 \([l,mid]\),你就可以拿他来求它这个部分对 \([mid+1,r]\) 的贡献,然后问题就变成了求 \([mid+1,r]\) 的。
所以就是一个 cdq 分治。
那你考虑这个横跨的部分怎么求。
那你 \(F\) 是 \([l,mid]\),那你 \...

文章标题:专项测试(数学1)
文章链接:https://www.dianjilingqu.com/3995.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>