省选前作业题汇总2

一些CC题

(完全口胡预警

Milestones

直接随机直线即可，两个点正好在那条直线上的概率是$frac{1}{49}$

Knight Moving

a,b线性无关：解方程之后转成网格图上路径计数

a,b线性相关：点数不超过2*500，直接建图路径计数

(别看就两句，i207M码了8个K，我先跑了

Product of Digitals

质因数分解后本质就是$2,3,5,7$的若干次方相乘

BSGS的思想，预处理$2,3$的次幂并排序，枚举$5,7$的次幂二分找有没有对应的$2,3$

Sine Partition Function

这什么玩意

神tm矩乘，咕咕咕

Reduce string

BZOJ 2121 $O(n^3*m*len)$大力DP

---

一些THUPC题

Tommy神的树

orz immortalCO，咕咕咕

赛艇

*AUWC，这是好的*

两个0/1矩阵的交为全零矩阵->对应位置没有交->展开成序列->通过序列对应位置相乘(0/1的乘法相当于与运算)判断->反转序列使得对差的位置做贡献->成功把状态压缩在一个格子里->多项式乘法

就是下标调的很烦啊=。=

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1550,M=9e6+90,mod=998244353;
int a[M],b[M],rev[M],pw[30][2]; char rd[M];
int n,m,k,mx,my,nx,ny,xx,yy,nm,ans,G,Gi;
int Qpow(int x,int k)
{
    if(k==1) return x;
    int tmp=Qpow(x,k/2);
    return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod;
}
int ID(int a,int b)
{
    return a*m+b;
}
int IDX()
{
    return (xx-mx)*m+yy-my;
}
void Pre()
{
    register int i; 
    nm=1; while(nm<=2*n*m) nm<<=1;
    for(i=1;i<nm;i++)
        rev[i]=(rev[i>>1]>>1)+(i&1)*(nm>>1);
    G=3,Gi=Qpow(G,mod-2),nx-=mx,ny-=my;
    for(int i=1;i<=28;i++)
    {
        pw[i][0]=Qpow(G,(mod-1)/(1<<i));
        pw[i][1]=Qpow(Gi,(mod-1)/(1<<i));
    }
}
void Trans(int *arr,int len,int typ)
{
    register int i,j,k;
    for(i=0;i<len;i++)
        if(rev[i]>i) swap(arr[rev[i]],arr[i]);
    for(i=2;i<=len;i<<=1)
    {
        int lth=i>>1,ort=pw[(int)log2(i)][typ==-1];
        for(j=0;j<len;j+=i)
        {
            int ori=1,tmp;
            for(k=j;k<j+lth;k++,ori=1ll*ori*ort%mod)
            {
                tmp=1ll*ori*arr[k+lth]%mod;
                arr[k+lth]=(arr[k]-tmp+mod)%mod;
                arr[k]=(arr[k]+tmp)%mod;
            }
        }
    }
    if(typ==-1)
    {
        int Ni=Qpow(len,mod-2);
        for(i=0;i<=len;i++)
            arr[i]=1ll*arr[i]*Ni%mod;
    }
}
int main()
{
    register int i;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%s",rd);
        for(int j=0;j<m;j++)
            a[ID(i,j)]=rd[j]=='1';
    }
    scanf("%s",rd);
    for(int i=0;i<k;i++)
    {
        if(rd[i]=='w') xx--; if(rd[i]=='a') yy--;
        if(rd[i]=='s') xx++; if(rd[i]=='d') yy++;
        mx=min(mx,xx),nx=max(nx,xx);
        my=min(my,yy),ny=max(ny,yy);
    }
    xx=yy=0,b[IDX()]=1;
    for(int i=0;i<k;i++)
    {
        if(rd[i]=='w') xx--; if(rd[i]=='a') yy--;
        if(rd[i]=='s') xx++; if(rd[i]=='d') yy++;
        b[IDX()]=1;
    }//printf("%d %d %d %d ",nx,mx,ny,my);
    reverse(b,b+n*m),Pre(); 
//    for(int i=0;i<n*m;i++)
//        printf("%d %d
",a[i],b[i]);
    Trans(a,nm,1),Trans(b,nm,1);
    for(i=0;i<nm;i++) a[i]=1ll*a[i]*b[i]%mod;
    Trans(a,nm,-1); //printf("%d %d ",n-nx,m-ny);
    for(int i=0;i<n-nx;i++)
        for(int j=0;j<m-ny;j++)
            if(!a[i*m+j+n*m-1]) ans++;
    printf("%d",ans);
    return 0;
}

蛋糕

特判掉测度为1的情况，之后状压每一维是否在边界，枚举子集统计

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ull unsigned long long
using namespace std;
const int N=20;
const ull mod=2148473648;
int T,S,B,cnt[N],wid[N];
ull ans[N];
void Add(ull &x,ull y)
{
    x+=y;
    if(x>=mod) x-=mod;
}
ull Count(int s)
{
    ull ret=1;
    for(int i=0;i<4;i++)
        if(wid[i]!=1)
        {
            if(s&(1<<i)) ret=ret*2%mod;
            else ret=ret*(wid[i]-2)%mod;
        }
    return ret;
}
int main()
{
    for(int i=0;i<=(1<<4);i++)
        cnt[i]=cnt[i>>1]+(i&1);
    scanf("%d",&T);
    while(T--)
    {
        memset(ans,S=B=0,sizeof ans);
        for(int i=0;i<4;i++)
        {
            scanf("%d",&wid[i]);
            (wid[i]==1)?B+=2:S|=1<<i;
        }
        for(int s=S;;s=(s-1)&S)
        {
            Add(ans[B+cnt[s]],Count(s));
            if(!s) break;
        }
        for(int i=0;i<=8;i++)
            printf("%llu ",ans[i]); puts("");
    }
    return 0;
}

RSA

$∵gcd(e1,e2)==1$

$∴m->m^1->m^{e_1*x+e_2*y}->m^{{e_1}^x}*m^{{e_2}^y}->c_1^x*c_2^y$，类似exGCD那样求解，即递归求$gcd(e1,e2)$，过程中不断更新$c1,c2->c2,c1*Inv(c2^{e1/e2})$

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll T,c1,c2,e1,e2,mod;
void Add(ll &x,ll y)
{
    x+=y;
    if(x>=mod) x-=mod;
}
void exGCD(ll a,ll b,ll &x,ll &y)
{
    if(!b) x=1,y=0;
    else exGCD(b,a%b,y,x),y-=a/b*x;
}
ll Inv(ll x)
{
    ll xx,yy;
    exGCD(x,mod,xx,yy);
    return (xx%mod+mod)%mod;
}
ll llm(ll a,ll b)
{
    ll ret=0;
    while(b)
    {
        if(b&1) Add(ret,a);
        Add(a,a),b>>=1;
    }
    return ret;
}
ll Qpow(ll x,ll k)
{
    ll ret=1;
    while(k)
    {
        if(k&1) ret=llm(ret,x);
        x=llm(x,x),k>>=1;
    }
    return ret;
}
void Solve(ll a,ll b)
{
    if(b) 
    {
        ll n1=c2,n2=llm(c1,Inv(Qpow(c2,a/b)));
        c1=n1,c2=n2,Solve(b,a%b);
    }
}
int main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld%lld%lld%lld",&c1,&c2,&e1,&e2,&mod);
        Solve(e1,e2),printf("%lld
",c1);
    }
    return 0;
}