清北学堂day1考试

probA

小 N 最近在沉迷数学问题。
对于一个数字串 S，如果可以将它划分成两个数字 A、B，满足：

1、 S ̅=(AB) ̅ 。（就是分割的时候，前面的串为A，后面的为B）

2、 A、B 均不包含前导 0。
3、 B 是 A 的倍数，且B / A是完全立方数。
那么小 N 就认为该划分是一个“好划分”。 如对于数字串“11297”，（11， 297）就是一个“好划分”。
如果一个数字串 S 至少有两个“好划分”，那么小 N 就认为 S 是一个“魔法串”。 如数字串“1335702375”就是一个“魔法串”，其“好划分”有（1， 335702375）和（133，5702375）。
现在给定正整数 N，小 N 需要你帮她求出一个长度恰好为 N 的“魔法串”S，如果无解请输出“QwQ”（不带引号）。
【输入】
一行一个正整数 N。
【输出】
一行一个长度恰好为 N 的“魔法串”S， 如果无解请输出“QwQ”（不带引号） 。
【输入输出样例】
19
【输出样例】
1124784124392112128
【数据范围】
对于 30%的数据： 1 ≤ N ≤ 10。
对于 50%的数据： 1 ≤ N ≤ 35。
对于 100%的数据： 1 ≤ N ≤ 100。

T1不知道为什么就gg了，最后拿了90，比赛一开场看到这个题QwQ感觉就是个规律题

首先写了一个暴力找规律

枚举A，然后枚举B是A的多少倍，不难证明这个东西的复杂度是在O （1000000） $（1000000）$以内的，然后对于每一个A和倍数，我们都将这个数记录在一个 map $map$里，如果一个数出现过两次，就说明它可以有至少两次分割

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#include<map> 

using namespace std;

inline int read()
{
  int x=0,f=1;char ch=getchar();
  while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

ll a,b;
map<long long,int> mp;
ll n;

ll count(ll x)
{
    ll cnt=0;
    while (x)
    {
      cnt++;
      x/=10;
    }
    return cnt;
}

ll qsm(ll i,ll j)
{
    ll ans=1;
    while (j)
    {
        if (j&1) ans*=i;
        i*=i;
        j>>=1;
    }
    return ans;
}

char s[110],ss[110];

int main()
{
  scanf("%lld",&n);
  ll top = qsm(10,n)-1;
  //cout<<top<<endl;
  for (int i=1;i<=top;i++)
  {
     ll j=1;
     ll cc=count(i);
     //cout<<"gg"<<endl;
     while ((cc+count(i*j*j*j))<n) j++;
     if (cc+count(i*j*j*j)>n) continue;
     while (cc+count(i*j*j*j)==n)
     {
       ll xx=i*j*j*j;
       ll ymh=i*qsm(10,count(xx))+xx;
       mp[ymh]++;  
       if (mp[ymh]==2){

        cout<<ymh<<endl;
        //return 0;
       } 
       j++;
     }
  }
  cout<<"QwQ";
  return 0;
}

经过一些小数的计算，就找到了规律。

就是根据%3的余数来分类，这就不详细说了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

inline int read()
{
  int x=0,f=1;char ch=getchar();
  while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}
int s[220];
int n;
int main()
{
  freopen("magic.in","r",stdin);
  freopen("magic.out","w",stdout);
  scanf("%d",&n);
  if (n<=4) cout<<"QwQ";
  else
  {
     if (n%3==2)
     {
         s[1]=7;
         s[2]=3;
         s[3]=5;
         s[4]=8;
         s[5]=4;
         int tmp = 5;
         while (tmp<n)
         {
            s[++tmp]=0; 
         }
      }
      if (n%3==0)
      {
        s[1]=3;
        s[2]=2;
        s[3]=4;
        int tmp =3;
        while (tmp<n)
        {
            s[++tmp]=0;
          }
       }
       if (n%3==1)
       {
          //1621296
           s[1]=1;
           s[2]=6;
           s[3]=2;
           s[4]=1;
           s[5]=2;
           s[6]=9;
           s[7]=6;
           int tmp =7;
           while (tmp<n)
           {
            s[++tmp]=0;
           }
       }
  }
  for (int i=1;i<=n;i++)
  {
    cout<<s[i];
  }
  return 0;
}

prob2
【问题描述】

有1~n一共n个数，n为偶数。小Q要把这n个数随机地两两配对。令每一对的权值为它们两个数的和。小Q想要知道这n对里最大的权值的期望是多少。请输出答案对10^9+7取模的值。

【输入】
一行一个正整数 N。
【输出】
一行一个整数，表示答案对10^9+7取模的值。
【输入样例】
4
【输出样例】
6
【数据范围】
对于 20%的数据： 1 ≤ N ≤ 10。
对于 40%的数据： 1 ≤ N ≤ 2000。
对于 100%的数据： 1 ≤ N ≤ 500000。

QwQ
考试的时候，只会暴力

就是暴力枚举所有的配对方案

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long

using namespace std;

inline int read()
{
  int x=0,f=1;char ch=getchar();
  while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

const ll mod = 1e9+7;


int vis[10010];
int n;
int a[1010];
ll ans;
ll ans1=1;

ll qsm(ll i,ll j)
{
    ll ans=1;
    while (j){
        if (j&1) ans=ans*i%mod;
        i=i*i%mod;
        j>>=1;
    }
    return ans;
}
void dfs(int x,int tmp)
{

    if (tmp==n/2)
    {
        ll max1 = 0;
        for (int i=1;i<=n/2;i++) max1=max(max1,(long long)a[i]);
        ans=(ans+max1)%mod; 
    }
    else
    {   
        if (vis[x])
        {
             dfs(x+1,tmp);
        }
        else
        for (int i=1;i<=n;i++)
        {
            if (!vis[i] && x!=i)
            {
                a[tmp+1]=x+i;
                vis[x]=1;
                vis[i]=1;
                dfs(x+1,tmp+1);
                vis[x]=0;
                vis[i]=0;
                a[tmp+1]=0; 
            }
        }
    }
}
int main()
{
  freopen("pair.in","r",stdin);
  freopen("pair.out","w",stdout);
  scanf("%d",&n);
  dfs(1,0);
  for (int i=1;i<=n-1;i+=2)
  {
    ans1=ans1*i%mod;
  }
  //cout<<ans1<<endl;
  cout<<ans*qsm(ans1,mod-2)%mod;
  return 0;
}

正解就是：

考虑枚举答案是否 ≥m $\ge m$

转化成答案是否 ≤m $\le m$

把 1−n $1-n$分成两部分，一部分是 >m2 $>\frac{m}{2}$的，一部分是 ≤m2 $\le \frac{m}{2}$的。

显然 >m2 $>\frac{m}{2}$的只能和 ≤m2 $\le \frac{m}{2}$的匹配。

我们从大到小枚举 >m2 $>\frac{m}{2}$的部分，每次都有 m−n $m-n$种选择，故方案数为

(m−n)n−m2 $$(m-n{)}^{n-\frac{m}{2}}$$

剩下的部分是一个完全图，令 f(x) $f(x)$为 x $x$个点的方案数, f(x) $f(x)$为 1×3×5×⋯×(x−1) $1\times 3\times 5\times \cdots \times (x-1)$

QwQ以上是老师的题解，但是我并不是非常理解

预处理阶乘后可以 O(nlogn) $O(nlogn)$进行计算。

但是我们通过这样计算得到的可能性情况，实际上是保证了任意两个数 ≤ $\le$m的情况，而不是 == $==$ 所以，我们维护一个front 表示 ≤ $\le$m-1的情况，二者相减，就能得到 == $==$m的情况了

QwQ感觉我的程序还是比std更好理解

这里有一些注意的地方，写一下，怕自己以后忘掉：

1>v只所以不直接用 n−m2 $n-\frac{m}{2}$是怕m在奇数的时候出现bug，所以用 (2∗n−m+1)2 $\frac{(2\ast n-m+1)}{2}$这样就不会出现边界的划分问题

2>inv的数组下表之所以是 n2−v $\frac{n}{2}-v$的原因是
我们考虑大于 m2 $\frac{m}{2}$的数是有 n−m2 $n-\frac{m}{2}$个，
然后每一个数匹配到一个数，那么使用过的数就是 2×n−m $2\times n-m$，
那么剩余的数就是 n−(2×n−m) $n-(2\times n-m)$，也就是 m−n $m-n$
因为有令 f(x) $f(x)$为 x $x$个点的方案数, f(x) $f(x)$为 1×3×5×⋯×(x−1) $1\times 3\times 5\times \cdots \times (x-1)$
所以，要乘到 m−n2 $\frac{m-n}{2}$，那么inv的下表也就是 m−n2 $\frac{m-n}{2}$
就等于 n2−v $\frac{n}{2}-v$ (之所以用v来计算，还是为了避免因为m的奇偶性带来的bug）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long

using namespace std;

inline int read()
{
  int x=0,f=1;char ch=getchar();
  while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

const ll mod = 1e9+7;

long long qsm(ll i,ll j)
{
   ll ans=1;
   while (j)
  {
     if (j&1) ans=ans*i%mod;
     i=i*i%mod;
     j>>=1;
  }
  return ans;
}

ll inv[1000010];
ll ans,front;
int n;
int main()
{
  scanf("%d",&n);
  inv[0]=1;
  for (int i=1;i<=n/2;i++)
  {
     inv[i]=inv[i-1]*(2*i-1)%mod;
  }
  front=0;
  for (int m=n+1;m<=2*n-1;m++)
  {
     ll v=(2*n-m+1)/2;
     ll tmp = qsm(m-n,v)%mod*inv[n/2-v]%mod;
     ans=(ans+(tmp-front+mod)%mod*(long long)m%mod)%mod;
     front=tmp;
  }
  ans=ans*qsm(inv[n/2],mod-2)%mod;
  cout<<ans;
  return 0;
}

probC
幸运数
（lucky.cpp/c/pas）lucky.in lucky.out
【问题描述】

对于任意两个非零整数x，y，若整数d能同时被x和y整除，则称d为x与y的公约数。定义x与y的最大公约数gcd(x, y)为x与y的最大的公约数。
如gcd(6, 9) = 3，gcd(12, 16) = 4，gcd(25, 32) = 1，等等。

这里，我们定义什么是幸运数：

对于一个正整数d，我们使用di表示d在十进制表示下，按从低位到高位顺序的第i位数字。
设F(d)表示d的奇数位的数字之和，即F(d) = d1 + d3 + d5 + ……；
设G(d)表示d的偶数位的数字之和，即G(d) = d2 + d4 + d6 + ……；
若F(d)与G(d)均大于0，且F(d)与G(d)的最大公约数不超过K，则称d为幸运数。其中K是一个已知的常数。

举个例子来说，若d = 641，则d1 = 1，d2 = 4，d3 = 6，F(641) = 1 + 6 = 7，G(641) = 4。此时F(d)与G(d)的最大公约数即gcd(7, 4)等于1。则当K不小于1时641是幸运数。

小M请你回答下面的问题：
对于给定的K，在不小于L并且不超过R的所有整数中，有多少个数是幸运数？
注意，输入文件包含多组测试数据。
【输入文件】
第一行包含一个整数T，表示有T组测试数据。
接下来T行，每行包含三个整数K、L、R，表示一次询问。
【输出文件】
输出T行，每行一个整数，依次表示每组测试数据的答案。

【输入样例】
5
1 1 10
2 28 34
100 987654321 987654321
1 1 50000
1 50001 100000
【输出样例】
0
5
1
30298
30309
【样例解释】
K = 1时，1到10之间不存在幸运数。
K = 2时，28到34之间的幸运数有28、29、31、32、34，共5个。
K = 100时，987654321是幸运数。
K = 1时，1到50000之间的幸运数有30298个，50001到100000之间的幸运数有30309个。
【数据规模和约定】
对于10%的数据：1 ≤ L ≤ R ≤ 103。
另有10%的数据：1 ≤ L ≤ R ≤ 107，1 ≤ K, T ≤ 10。
另有10%的数据：1 ≤ L ≤ R ≤ 109，K = 1，1 ≤ T ≤ 10。
对于60%的数据：1 ≤ L ≤ R ≤ 1012，1 ≤ K, T ≤ 102。
对于100%的数据：1 ≤ L ≤ R ≤ 1018， 1 ≤ K ≤ 102，1 ≤ T ≤ 1 000。

QAQ考场上想的是数位dp

我们考虑这个求 [L,R] $[L,R]$之间的答案，其实就是可以用 ans[1,r]−ans[1,l−1] $an{s}_{[1,r]}-an{s}_{[1,l-1]}$

那么我们令 f[i][j][k][p] $f[i][j][k][p]$表示前 i $i$位，奇数位的和是 j $j$,偶数位的和 k $k$，最高为是 p $p$
的方案数

首先，我们在预处理 f $f$数组的时候，需要包含着前导零

void init()
{
    for (int i=0;i<=9;i++)
    {
        for (int j=0;j<=9;j++)
          f[2][i][j][j]=1;
    }
    for (register int i=3;i<=18;++i)
    {
      for (register int x=0;x<=9;++x)
        for (register int j=0;j<=72;++j)
          for (register int p=0;p<=72;++p)
            for (register int q=0;q<=9;++q)
              {
                if (i&1)
                {
                     f[i][j+x][p][x]+=f[i-1][j][p][q];
                  }
                else
                {
                    f[i][j][p+x][x]+=f[i-1][j][p][q];
                }
              } 
    }
}

对于一个数x，我们设它的长度是 len $len$，那么，对于 [1,x] $[1,x]$中，我们首先可以把长度小于len的“幸运数”的个数加起来

for (register int u=2;u<=len-1;++u)
     for (register int i=1;i<=81;++i)
        for (register int j=1;j<=81;++j)
          for (register int p=1;p<=9;++p)
            if (gcd(i,j)<=k) tmp+=f[u][i][j][p];

然后，我们将位数与x相等，但是最高位比x小的个数加起来

for (register int i=1;i<=81;++i)
        for (register int j=1;j<=81;++j)
          for (register int p=1;p<=a[len]-1;++p)
            if (gcd(i,j)<=k) tmp+=f[len][i][j][p];

那么对于卡上界的呢，我们就要维护，比这一位高的偶数位的和，和奇数位的和，然后枚举当前位是多少(最低位要单独判断) 然后搞搞就行

if ((len & 1) && len>=2) ji+=a[len];
    else ou+=a[len];      
    for (register int i=len-1;i>=2;i--)
    {
        for (register int j=0;j<=a[i]-1;++j)
        {
              for (int u=0;u<=81-ji;u++)
                for (int v=0;v<=81-ou;v++)
                  if (gcd(u+ji,v+ou)<=k && u+ji!=0 && v+ou!=0) tmp+=f[i][u][v][j];
        }
        if (i&1) ji+=a[i];
        else ou+=a[i];
      }
     // cout<<ou<<" "<<ji<<endl;
        for (register int j=0;j<=a[1];++j)
        if (gcd(ou,ji+j)<=k && ou!=0 && ji+j!=0) tmp++;

下面附上完整代码·

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;

inline ll read()
{
  ll x=0,f=1;char ch=getchar();
  while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

ll f[20][100][100][10];
int t;
ll l,r,k;
ll a[110];

int gc(int a,int b)
{
    if (b==0) return a;
    else gc(b,a%b);
}

int gcd(int a,int b)
{ 
    if (a==0 || b==0) return 1;
    else return gc(a,b);
}

void init()
{
    for (int i=0;i<=9;i++)
    {
        for (int j=0;j<=9;j++)
          f[2][i][j][j]=1;
    }
    for (register int i=3;i<=18;++i)
    {
      for (register int x=0;x<=9;++x)
        for (register int j=0;j<=72;++j)
          for (register int p=0;p<=72;++p)
            for (register int q=0;q<=9;++q)
              {
                if (i&1)
                {
                     f[i][j+x][p][x]+=f[i-1][j][p][q];
                  }
                else
                {
                    f[i][j][p+x][x]+=f[i-1][j][p][q];
                }
              } 
    }
}

ll count(ll x)
{
    ll cnt=0;
    while (x)
    {
        cnt++;
        a[cnt]=x%10;
        x/=10;
    }
    return cnt;
}

ll solve(ll x)
{
    memset(a,0,sizeof(a));
    ll len = count(x);
    ll tmp=0;
    for (register int u=2;u<=len-1;++u)
     for (register int i=1;i<=81;++i)
        for (register int j=1;j<=81;++j)
          for (register int p=1;p<=9;++p)
            if (gcd(i,j)<=k) tmp+=f[u][i][j][p];
     //cout<<tmp<<" "<<x<<endl; 
    for (register int i=1;i<=81;++i)
        for (register int j=1;j<=81;++j)
          for (register int p=1;p<=a[len]-1;++p)
            if (gcd(i,j)<=k) tmp+=f[len][i][j][p];   
    ll ji=0,ou=0;
    if ((len & 1) && len>=2) ji+=a[len];
    else ou+=a[len];      
    for (register int i=len-1;i>=2;i--)
    {
        for (register int j=0;j<=a[i]-1;++j)
        {
              for (int u=0;u<=81-ji;u++)
                for (int v=0;v<=81-ou;v++)
                  if (gcd(u+ji,v+ou)<=k && u+ji!=0 && v+ou!=0) tmp+=f[i][u][v][j];
        }
        if (i&1) ji+=a[i];
        else ou+=a[i];
      }
     // cout<<ou<<" "<<ji<<endl;
        for (register int j=0;j<=a[1];++j)
        if (gcd(ou,ji+j)<=k && ou!=0 && ji+j!=0) tmp++;
      //cout<<tmp<<endl;
      return tmp;
}
int main()
{
  freopen("lucky.in","r",stdin);
  freopen("lucky.out","w",stdout);
  cin>>t;
  init();
  while (t--)
  {
      k=read();
      l=read();
      r=read();
      //cout<<solve(99)<<endl;
      //cout<<solve(int ans=0;
      printf("%lld\n",solve(r)-solve(l-1));
  }
  return 0;
}

QwQ然而这个程序只有60分 哎