专项测试 数学1
T1 young
考虑dp
设f[n][m]表示n个点，权值在\([0,2^m-1]\)的最小生成树的权值之和
转移就将这 n 个点根据第m-1位的取值划分成s，t集合
然后s，t集合内部分别是一棵生成树，所以考虑 s 和 t 集合之间的最小连边，设为g[s][t][m]
\[f_{n,m}=\sum^{n}_ {k=0}{n\choose k}\Big( f_{k,m-1}* 2^{(n-k)* (m-1)}+f_{n-k,m-1}* 2^{k*(m-1)} +g_{k,n-k,m-1} +(k*(n-k)!=0)* 2^{(n+1)* (m-1)} \Big) \]考虑计算g[s][t][m]
直接求不出来，所以转化一下，设p(s,t,m,k)表示集合s，t权值在\([0,2^m-1]\) 且s->t 这条边权值>=k 的情况数
\[g_{s,t,m}=\sum_{i=1}^{2^m-1}p_{s,t,m,i} \]计算p时，将s，t继续划分，根据在m-1位的取值分成s0,s1,t0,t1四个集合，除特殊情况s0,t1空或s1,t0空外，连边只会在s0->t0,s1->t1
然后递归下去，根据乘法原理再套个组合数将两个集合的答案合起来
当然，细节较多，不一一分说
T2 Simple
若最小循环节长度小于n，循环移位一下，这个数在所有循环中肯定不是最小的，不满足限制
若最小循环节长度为n，在所有的循环方案中最小的那一个数是合法的
所以设f[n]表示长度为 n 的所有串的贡献之和
\[f_n=\frac{\sum_{d|n}{10^{\frac{n}{d}}\mu(d)}}{n} \]\[ans=\sum_{i=1}^{n}i^2* f_i \]\[ans=\sum_{i=1}^{n}i\mu(i)\sum_{j=1}^{\lfloor \frac{n}{i} \rfloor}j* 10^{j} \]左边那个杜教筛，右边那个等差乘等比可以O(1)算
T3 mate
强制在第一象限，然后向右的步数比左多 x 步，上比下多 y 步
枚举向右走 i 步，然后四个方向都有了
然后就是可重集排列，但是模数不保证是质数，也不保证小于 n
可以考虑数据结构维护这个可重集排列，线段树下标存每个质数的次数，i->i+1时只会有O(log n)O(我不知道但是很少)的素数产生变化，单点修改就行了
因为内存紧张，所以在叶子节点还需快速幂，复杂度O(n log^2 n)但是常数较小O(看似是两个log但是很快)
代码
T1
#include
#include
#include
using namespace std;
#define int long long
#define il inline
const int N=52;
const int mod=258280327;
int n,m;
int mi[N*N];
int f[N][N];
int c[N][N];
int g[N][N][9];
int fg[N][N][9][1<<8];
il void md(int &x){if(x>=mod)x-=mod;return;}
int fm(int x,int y){int ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
int get_fg(int s,int t,int m,int k)
{
if(s>t) swap(s,t);
if(fg[s][t][m][k]!=-1) return fg[s][t][m][k];
if(!s||!t) return fg[s][t][m][k]=mi[m*(s+t)];
if(!m) return fg[s][t][m][k]=0;
int sum=0;
int sum1=0,sum2=0;
for(int i=0;i<=s;++i)
for(int j=0;j<=t;++j)
{
if(!i&&j==t) continue;
if(i==s&&!j) continue;
if(fg[i][j][m-1][k]==-1) sum1=get_fg(i,j,m-1,k)*c[s][i]%mod; else sum1=fg[i][j][m-1][k]*c[s][i]%mod;
if(fg[s-i][t-j][m-1][k]==-1) sum2=get_fg(s-i,t-j,m-1,k)*c[t][j]%mod; else sum2=fg[s-i][t-j][m-1][k]*c[t][j]%mod;
(sum+=sum1*sum2)%=mod;
}
if(k>(1<>n>>m;
c[0][0]=1;
mi[0]=1;
for(int i=1;i T2
#include
using namespace std;
#define il inline
#define int long long
const int N=1e6+11;
const int mod=258280327;
bool fp[N];
int n;
int p[N],num,mu[N];
int smu[N];
unordered_map mp;
il void md(int &x){if(x>=mod)x-=mod;return;}
il int fm(int x,int y){x%=mod;int ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
int get_g(int x){x%=mod;return x*(x+1)/2%mod;}
int S(int n){return ((9*n%mod-1)*fm(10,n+1)+10)%mod*fm(81,mod-2)%mod;}
inline int read()
{
int s=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
void pre()
{
fp[0]=fp[1]=1;
smu[1]=mu[1]=1;
for(int tmp,i=2;i T3
#include
using namespace std;
#define il inline
#define int long long
const int N=1e6+11;
struct vct_{int x,num;};
struct tree{int l,r,num,sum;}tre[4*(N/10)];
bool fp[N];
int n,mod,x,y;
int mi[N];
int p[N],num,rle[N];
vector vct[N];
il void md(int &x){if(x>=mod)x-=mod;return;}
int fm(int x,int y){int ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
il int read()
{
int s=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
void pre()
{
fp[0]=fp[1]=1;
for(int tmp,i=2;i<=1e6;++i)
{
if(!fp[i]) p[++num]=i,rle[i]=num,vct[i].push_back({i,1});
for(int j=1;j<=num&&p[j]*i<=1e6;++j)
{
tmp=i*p[j];
fp[tmp]=1;
vct[tmp]=vct[i];
if(i%p[j]==0){vct[tmp][vct[tmp].size()-1].num+=1;break;}
else vct[tmp].push_back({p[j],1});
}
}
return;
}
void build(int i,int l,int r)
{
tre[i]={l,r,0,1};
if(l==r) return;
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
return;
}
void insert(int i,int x,int val)
{
if(tre[i].l==tre[i].r)
{
tre[i].num+=val;
tre[i].sum=fm(p[x],tre[i].num);
return;
}
int mid=(tre[i].l+tre[i].r)>>1;
if(x<=mid) insert(i<<1,x,val);
else insert(i<<1|1,x,val);
tre[i].sum=tre[i<<1].sum*tre[i<<1|1].sum%mod;
return;
}
signed main()
{
pre();
n=read(),mod=read(),x=read(),y=read();
if((n-x-y)&1){cout<<0<n){cout<<0<