牛表

40point

$P\le 500\{P\backslash le\; 500\}$，建边跑弗洛伊德算法，时间复杂度为$O(n^3)O(n^3)$。 意外的是评测机跑得非常快，导致暴力分超出预期。

100point

跑$P-1\{P-1\}$次迪杰斯特拉算法，但是边数是满的，直接跑的复杂度是$O(P^3)\{O(P^3)\}$。 考虑如何优化，通过打表可以观察到其实答案非常的小，我们可以假设答案不超过$lim\{lim\}$，那么用点$u\{u\}$去更新的时候只需要转移到$[max(1,u-lim),min(P-1,u+lim)][\{max(1,u-lim),min(P-1,u+lim)]\}$范围内的点，这样边数就被优化到了$O(Plim)O(Plim)$。

另外，由于$lim\{lim\}$很小，不需要采用堆优化的迪杰斯特拉算法，而仅仅需要开$lim+1\{lim+1\}$个队列即可，从而总的时间复杂度为$O(P^{2}lim)O(P^2lim)$。 最后设置$lim=30lim=30$就足够了（通过打表可以证明答案最大为$17\{17\}$。）。

一个复杂度较低的暴力证明法：

$1.1.$证明$ans(x,1)\le limans(x,1)\backslash le\; lim$

$2.2.$证明$ans(1,x)\le limans(1,x)\backslash le\; lim$

对于一个$P\{P\}$该证明的复杂度只需$O(Plim)O(Plim)$，总共$O(P^{2}lim)O(P^2lim)$。

这样可以证明答案$\le 2\ast lim\{\backslash le\; 2*lim\}$。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=5e3+5,mod=998244353;
char s[N];
int p,dis[N];
bool vis[N];
int mx;
const int lim=30;
queue<int>q[lim+1];
void sol(int s)
{
  for(int i=1;i<p;i++) vis[i]=false,dis[i]=p;
  dis[s]=0;
  q[0].push(s);
  for(int i=0;i<=lim;i++)
  {
    while(!q[i].empty())
    {
      int u=q[i].front();q[i].pop();
      if(vis[u]) continue;
      vis[u]=true;
      int l=max(1,u-lim),r=min(p-1,u+lim);
      for(int v=l;v<=r;v++)
      {
        int nx=1ll*u****        if(dis[nx]>dis[u]+abs(u-v))
        {
          dis[nx]=dis[u]+abs(u-v);
          if(dis[nx]<=lim) q[dis[nx]].push(nx);
        }
      }
    }
  }
}
bool use[N];
vector<int>prim;
int t;
int main() 
{
  for(int i=2;i<=2000;i++)
  if(!use[i])
    {
      prim.push_back(i);
      for(int j=i+i;j<=2000;j+=i) use[j]=true;
    }
  sc(p,t);
  int ans=0;
  ll g=1;
  for(int i=1;i<p;i++)
  {
    sol(i);
    for(int j=1;j<p;j++)
    {
      assert(dis[j]<p);
      ans=(ans+dis[j]*g%mod)%mod,g=g*t%mod;
    }
  }
  out(ans);
}

牛牛和数组操作

10point

枚举全排列，计算代价，对比代价，得出答案，时间复杂度$O(n!)\{O(n!)\}$。

20point

状态压缩，计算代价，对比代价，得出答案，时间复杂度$O(n{2}^n)\{O(n2^n)\}$。

70point（TLE）

设第一个操作的人编号为$x\{x\}$，在$x\{x\}$进行操作后，$[1,x-1]\{[1,x-1]\}$和$[x+1,n]\{[x+1,n]\}$的操作就独立了，这两段区间进行操作不会对另一段区间的价值产生影响，因此可以进行区间$dp\{dp\}$。 设$d{p}_{l,r}dp\_\{l,r\}$为对$[l,r]\{[l,r]\}$区间操作产生的最小代价，$g_{l,r}g\_\{l,r\}$为最小代价的操作序列数量，枚举$m\{m\}$，若$d{p}_{l,r}dp\_\{l,r\}$由$d{p}_{l,m},d{p}_{m+1,r}dp\_\{l,m\},dp\_\{m+1,r\}$转移过来，则$g_{l,r}+=g_{l,m}\ast g_{m+1,r}\ast C(r-l,m-l)g\_\{l,r\}+=g\_\{l,m\}*g\_\{m+1,r\}*C(r-l,m-l)$，时间复杂度$O(n^3)O(n^3)$。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=2005,mod=998244353;
int n,a[N],cost[N][N];
ll dp[N][N],g[N][N],c[N][N];
ll C(int n,int m)
{
    if(m==0||n==m) return 1;
    if(m==1) return n;
    if(c[n][m]) return c[n][m];
    return c[n][m]=(C(n-1,m-1)+C(n-1,m))%mod;
}
int cs(int l,int r)
{
    return cost[l][r];
}
bool vis[N][N];
void sol(int cas)
{
    sc(n);
    rep(i,1,n) sc(a[i]);
    for(int i=1;i<=n;i++)
    {
        cost[i][i]=a[i];
        for(int j=i+1;j<=n;j++)
            cost[i][j]=max(cost[i][j-1],a[j]);
    }
    for(int len=0;len<=n;len++)
        for(int l=1;l+len-1<=n;l++)
        {
            int r=l+len-1;
            if(l>=r)
            {
                dp[l][r]=0;
                g[l][r]=1;
            }
            else
            {
                dp[l][r]=1e18;g[l][r]=0;
                for(int i=l;i<=r;i++)
                    dp[l][r]=min(dp[l][r],dp[l][i-1]+cs(l,i-1)+dp[i+1][r]+cs(i+1,r));
                for(int i=l;i<=r;i++)
                    if(dp[l][r]==dp[l][i-1]+cs(l,i-1)+dp[i+1][r]+cs(i+1,r))   
                    g[l][r]=(g[l][r]+g[l][i-1]*g[i+1][r]%mod*C(r-l,i-l)%mod)%mod;
            }
        }
    printf("%lld\n",g[1][n]);
}
int main() 
{
//   freopen("1.in", "r",stdin);
//   freopen("1.out", "w", stdout);
  srand(time(0));
  int t=1,cas=0;
//   scanf("%d",&t);
  while(t--)
  {
    sol(++cas);
  }
}

100point（1000~2000ms)

实际上每次先操作区间最大值是最优的，因此没有必要对区间的所有数都进行枚举，而只枚举区间最大值，时间复杂度$O(n^3)O(n^3)$。。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=2005,mod=998244353;
int n,a[N],b[N],nex[N],pos[N][N],vis[N];
ll g[N][N],f[N],inv[N],invf[N];
bool use[N][N];
ll C(int n,int m)
{
    return f[n]*invf[m]%mod*invf[n-m]%mod;
}
ll P(int n,int m)
{
    return f[n]*invf[n-m]%mod;
}
void dfs(int l,int r)
{
    if(l>=r)
    {
        g[l][r]=1;
        return;
    }
    if(use[l][r]) return;
    use[l][r]=true;
    g[l][r]=0;
    for(int i=pos[l][r];i<=r;i=nex[i])
    {
        dfs(l,i-1);dfs(i+1,r);
        g[l][r]=(g[l][r]+g[l][i-1]*g[i+1][r]%mod*C(r-l,i-l)%mod)%mod;
    }
}
void sol(int cas)
{
    sc(n);
    rep(i,1,n) sc(a[i]);
    rep(i,1,N-1) vis[i]=n+1;
    for(int i=n;i>=1;i--)
    {
        nex[i]=vis[a[i]];
        vis[a[i]]=i;
    }
    for(int i=1;i<=n;i++)
    {
        pos[i][i]=i;
        for(int j=i+1;j<=n;j++)
            if(a[j]>a[pos[i][j-1]])
            pos[i][j]=j;
            else pos[i][j]=pos[i][j-1];
    }
    dfs(1,n);
    printf("%lld\n",g[1][n]);
}
int main() 
{
    f[0]=f[1]=invf[0]=invf[1]=inv[1]=1;
    rep(i,2,N-1)
    {
        f[i]=f[i-1]*i%mod;
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        invf[i]=invf[i-1]*inv[i]%mod;
    }
    // freopen("1.in", "r",stdin);
    // freopen("2.out", "w", stdout);
    srand(time(0));
    int t=1,cas=0;
    // scanf("%d",&t);
    while(t--)
    {
        sol(++cas);
    }
}

100point（100~300ms）

对于一段区间$[l,r][l,r]$，如果存在$a_i=a_{i+1}={}_{i=l}^r(a_i)(i\in [l,r))\{a\_i=a\_\{i+1\}=\backslash max\backslash limits\_\{i=l\}^r(a\_i)(i\backslash in[l,r))\}$。 此时$i,i+1\{i,i+1\}$谁先选择没有关系，因此有$g_{l,r}=g_{l,i}\ast g_{i+1,r}\ast C(r-l+1,i-l+1)\{g\_\{l,r\}=g\_\{l,i\}*g\_\{i+1,r\}*C(r-l+1,i-l+1)\}$。 因此当碰到两个最大值连续出现时，直接将整个区间划分为两段，最大值不连续则仍然枚举所有最大值。 时间复杂度$O(n^3)O(n^3)$。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=2005,mod=998244353;
int n,a[N],h[N][N],nex[N],pos[N][N],vis[N],g[N][N];
bool use[N][N];
int f[N],inv[N];
vector<pair<int,int>>dp[N];
void add(int &x,int y){x+=y;if(x>=mod)x-=mod;}
void sol(int cas)
{
    sc(n);
    ast(n,1,2000);
    rep(i,1,n) sc(a[i]),ast(a[i],1,n);
    rep(i,1,N-1) vis[i]=n+1;
    for(int i=n;i>=1;i--)
    {
        nex[i]=vis[a[i]];
        vis[a[i]]=i;
    }
    for(int i=1;i<=n;i++)
    {
        pos[i][i]=i;
        h[i][i]=0;
        for(int j=i+1;j<=n;j++)
        {
            if(a[j]>a[pos[i][j-1]])
                pos[i][j]=j,h[i][j]=0;
            else if(a[j]<a[pos[i][j-1]])
                pos[i][j]=pos[i][j-1],h[i][j]=h[i][j-1];
            else
            {
                pos[i][j]=pos[i][j-1];
                h[i][j]=h[i][j-1];
                if(!h[i][j]&&a[j]==a[j-1]) h[i][j]=j-1;
            }
        }
    }
    dp[n].push_back({1,n});
    for(int j=n;j>=2;j--)
    {
        for(pair<int,int>&x:dp[j])
        {
            int l=x.first,r=x.second;
            if(h[l][r])
            {
                int i=h[l][r];
                if(!use[l][i]) dp[i-l+1].push_back({l,i}),use[l][i]=true;
                if(!use[i+1][r]) dp[r-i].push_back({i+1,r}),use[i+1][r]=true;
            }
            else
            {
                for(int i=pos[l][r];i<=r;i=nex[i])
                {
                    if(!use[l][i-1]) dp[i-l].push_back({l,i-1}),use[l][i-1]=true;
                    if(!use[i+1][r]) dp[r-i].push_back({i+1,r}),use[i+1][r]=true;
                }
            }
        }
    }
    for(int j=0;j<=n;j++)
        for(pair<int,int>&x:dp[j])
        {
            int l=x.first,r=x.second;
            if(j<=1)
                g[l][r]=1;
            else
            {
                g[l][r]=0;
                if(h[l][r])
                {
                    int i=h[l][r];
                    g[l][r]=1ll*g[l][i]*g[i+1][r]%mod;
                }
                else
                {
                    for(int i=pos[l][r];i<=r;i=nex[i])
                        add(g[l][r],1ll*g[l][i-1]*g[i+1][r]%mod);
                    g[l][r]=1ll*g[l][r]*inv[r-l+1]%mod;
                }
            }
        }
    printf("%lld\n",1ll*g[1][n]*f[n]%mod);
}
int main() 
{
    f[0]=f[1]=inv[1]=1;
    for(int i=2;i<N;i++)
    {
        f[i]=1ll*f[i-1]*i%mod;
        inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    }
    // freopen("1.in", "r",stdin);
    // freopen("2.out", "w", stdout);
    srand(time(0));
    int t=1,cas=0;
    // scanf("%d",&t);
    while(t--)
    {
        sol(++cas);
    }
}

与巨

20point

$\mathrm{\mid }n\mathrm{\mid }\le 20\{|n|\backslash le\; 20\}$，而$2^{20}\{2^\{20\}\}$在$1e6\{1e6\}$左右，因此可以按照题意要求模拟。 时间复杂度$O(T{2}^{\mathrm{\mid }n\mathrm{\mid }}log(2^{\mathrm{\mid }n\mathrm{\mid }}))O(T2^\{|n|\}log(2^\{|n|\}))$或$O(T{2}^{\mathrm{\mid }n\mathrm{\mid }})O(T2^\{|n|\})$，取决于如何计算$G(x)\{G(x)\}$。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=1e7+5,mod=998244353;
char s[N];
ll c;
int n,p,dp[N];
int G(int x)
{
  int t=0;
  while(x) t++,x>>=1;
  return (1<<t)-1;
}
int main() 
{
  // freopen("1.in", "r",stdin);
  // freopen("2.out", "w", stdout);
  int cas;sc(cas);
  while(cas--)
  {
    scanf("%s%lld",s+1,&c);
    n=0;
    for(int i=1;s[i];i++) n=n*2+s[i]-'0';
    for(int i=1;i<=n;i++)
    {
      dp[i]=dp[i-1];
      if(((i*c)&G(i))==i) dp[i]=i;
    }
    ll ans=0;
    rep(i,1,n) ans=(ans+dp[i])%mod;
    out(ans);
  }
}

20point

$\mathrm{\mid }n\mathrm{\mid }\le 30,1\le c\le 50|n|\backslash le\; 30,1\backslash le\; c\backslash le\; 50$。 此时$n\{n\}$在$1e9\{1e9\}$左右，并且发现在$c\{c\}$为偶数的时候$d{p}_{c,i}\{dp\_\{c,i\}\}$永远是$0\{0\}$，因此这部分只有$25\{25\}$个有效的$c\{c\}$，可以对$d{p}_{c,1e6},d{p}_{c,2e6},\mathrm{.}\mathrm{.}\mathrm{.},d{p}_{c,x\ast 1e6}\{dp\_\{c,1e6\},dp\_\{c,2e6\},...,dp\_\{c,x*1e6\}\}$以及它们的前缀和进行打表，一个打$25\ast 1000\ast 2\{25*1000*2\}$个数。 然后计算出$n\{n\}$的十进制表示，在表中找到$d{p}_{c,\lfloor \frac{n}{1e6}\rfloor \ast 1e6}dp\_\{c,\backslash lfloor\backslash frac\{n\}\{1e6\}\backslash rfloor*1e6\}$的答案，再对剩余的进行计算。 时间复杂度$O(T1e6)O(T1e6)$。

100point

设$G(i)=2^{t+1}-1G(i)=2^\{t+1\}-1$（$G(x)G(x)$必然是这样的形式，其中$t\{t\}$为$i\{i\}$二进制的最高位），则相当于$x\mathrm{m}\mathrm{o}\mathrm{d}{2}^{t+1}x\backslash bmod\; 2^\{t+1\}$，则： 设$c-1=2^p\ast xc-1=2^p*x$，则$i\{i\}$需要含有因子$2^{t+1-p}2^\{t+1-p\}$。 设$m=\mathrm{\mid }n\mathrm{\mid }m=|n|$，我们可以枚举$tt$，如果，则$[2^t,2^{t+1}-1][2^t,2^\{t+1\}-1]$内的所有数最高位都为$t\{t\}$，设$g=t+1-p\{g=t+1-p\}$，$i\{i\}$含有因子$2^{g}2^g$即$i\{i\}$的低$g\{g\}$位全为$0\{0\}$，这样的数为$2^t,2^t+2^g,\mathrm{.}\mathrm{.}\mathrm{.},2^t+x\ast 2^g(2^t+(x+1)\ast 2^g=2^{t+1})\{2^t,2^t+2^g,...,2^t+x*2^g\}(2^t+(x+1)*2^g=2^\{t+1\})$，这是个$x+1\{x+1\}$项的等差数列，很容易求和，同时每个数对答案贡献$2^g\{2^g\}$次。 当$t=m-1\{t=m-1\}$时，由于$2^{t+1}>n\{2^\{t+1\}>n\}$，但我们需要满足$2^t+x\ast 2^g\le n\to x=\lfloor \frac{n}{2^g}\rfloor -2^{t-g}\{2^t+x*2^g\backslash le\; n\backslash to\; x=\backslash lfloor\backslash frac\{n\}\{2^g\}\backslash rfloor\}-2^\{t-g\}$，对这个$x+1x+1$项的等差数列计算贡献后，由于最后一项被计数了$2^g\{2^g\}$次（计数范围为$[2^t+x\ast 2^g,2^t+(x+1)\ast 2^g-1]\{[2^t+x*2^g,2^t+(x+1)*2^g\}-1]$），此时多计数了$2^t+(x+1)\ast 2^g-1-n\{2^t+(x+1)*2^g-1-n\}$次，把这个贡献减去即可。 时间复杂度为$O(n)\{O(n)\}$。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=1e7+5,mod=998244353;
char s[N];
ll c,f[N];
int n,p;
ll cal(ll s,ll d,ll n)
{
  return (s*n%mod+d*n%mod*(n+mod-1)%mod*(mod-mod/2)%mod)%mod;
}
int main() 
{
  f[0]=1;
  rep(i,1,N-1) f[i]=(f[i-1]<<1)%mod;
  // freopen("1.in", "r",stdin);
  // freopen("1.out", "w", stdout);
  int cas;sc(cas);
  while(cas--)
  {
    scanf("%s%lld",s+1,&c);
    n=strlen(s+1);
    c--;
    if(c==0)
    {
      ll ans=0;
      rep(i,1,n) ans=((ans<<1)+s[i]-'0')%mod;
      ans=ans*(ans+1)%mod*(mod-mod/2)%mod;
      out(ans);
      continue;
    }
    if(c&1){out(0);continue;}
    p=0;
    while(c%2==0) p++,c/=2;
    ll ans=0;
    for(int t=0;t<n;t++)
    {
      int g=max(0,t+1-p);
      if(t<n-1) ans=(ans+f[g]*cal(f[t],f[g],(f[t+1-g]+mod-f[t-g]))%mod);
      else
      {
        ll tot=0;
        rep(i,1,n-g) tot=((tot<<1)+s[i]-'0')%mod;
        tot=(tot+1+mod-f[t-g])%mod;
        ans=(ans+f[g]*cal(f[t],f[g],tot))%mod;
        ll las=(f[t]+(tot+mod-1)*f[g]%mod)%mod;
        ll l=0;
        rep(i,1,n) l=((l<<1)+s[i]-'0')%mod;
        ll r=(las+f[g]+mod-1)%mod;
        ans=(ans+mod-(r+mod-l)%mod*las%mod)%mod;
      }
    }
    out(ans);
  }
}

矩阵学说

20point

$n\le 50\{n\backslash le\; 50\}$，正方形矩阵的数量级别在$O(n^3)\{O(n^3)\}$左右。 可以枚举矩阵的左上角，每次正方形边长扩展$1\{1\}$，判断数据是否合法，时间复杂度$O(n^4)\{O(n^4)\}$。

40point

$n\le 500,a_i\le 100\{n\backslash le\; 500\},a\_i\backslash le\; 100$，在$20\{20\}$分的基础上，对数字进行状态压缩，把$a_i\{a\_i\}$压缩成$2^{a_i}\{2^\{a\_i\}\}$，每次边长扩展$1\{1\}$就只需要或上一个数，可以开两个long long用__builtin_popcountll()，或者用bitset。时间复杂度$O(n^3)O(n^3)$。

100point

在边长扩展的过程中，不同数量的数只会增加不会减少，具有单调性。于是可以二分找到不同数量的最大边长$x\{x\}$和不同数量$\le k\{\backslash le\; k\}$的最大边长$y\{y\}$，$y-x\{y-x\}$即为固定一个左上角符合条件的正方形的数量。 这样需要处理$O(n^{2}logn)\{O(n^2logn)\}$个查询，每个查询查询一个正方形内不同颜色的数量，由于是正方形，故可以采用二维$st\{st\}$表来做。 时间复杂度$O(n^{2}logn)O(n^2logn)$。

#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld\n", x); }
void out(int x, int y) { printf("%d %d\n", x, y); }
void out(ll x, ll y) { printf("%lld %lld\n", x, y); }
void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=1505,mod=1e9+7;
int n,m,k,lg[N];
bitset<100>dp[11][N][N];
void st()
{
    for(int k=1;1<<k<=max(n,m);k++)
        for(int i=1;i+(1<<k)-1<=n;i++)
        for(int j=1;j+(1<<k)-1<=m;j++)
        dp[k][i][j]=dp[k-1][i][j]|dp[k-1][i+(1<<k-1)][j+(1<<k-1)]|dp[k-1][i+(1<<k-1)][j]|dp[k-1][i][j+(1<<k-1)];
}
int query(int x1,int y1,int x2,int y2)
{
    int k=lg[x2-x1+1];
    return (dp[k][x1][y1]|dp[k][x2-(1<<k)+1][y2-(1<<k)+1]|dp[k][x2-(1<<k)+1][y1]|dp[k][x1][y2-(1<<k)+1]).count();
}
ll cal(int k)
{
    if(k==0) return 0;
    ll ans=0;
    rep(i,1,n)
        rep(j,1,m)
        {
            int l=1,r=min(n-i+1,m-j+1);
            while(l<r)
            {
                int m=(l+r+1)>>1;
                if(query(i,j,i+m-1,j+m-1)<=k) l=m;
                else r=m-1;
            }
            ans+=l;
        }
    return ans;
}
int read()
{
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return x;
}
void sol(int cas)
{
    for(int i=1;i<N;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i),lg[i-1]--;
    // n=read();m=read();k=read();
    scanf("%d%d%d",&n,&m,&k);
    ast(n,1,1500);ast(m,1,1500);ast(k,1,n*m);
    rep(i,1,n)
        rep(j,1,m)
    {
        int x;
        // x=read();
        scanf("%d",&x);
        ast(x,1,100);
        dp[0][i][j][x-1]=1;
    }
    st();
    printf("%lld\n",cal(k)-cal(k-1));
}
int main()
{
    srand(time(0));
    int t=1,cas=0;
    // scanf("%d",&t);
    while(t--)
    {
        sol(++cas);
    }
}