233 B

题意

有一个方程\[x^2+s(x)*x-n=0\]

现在给你参数 \(n(1\le n\le 10^{18})\) ，求方程的最小正整数解。

\(s(x)\) 表示 \(x\) 十进制位数码按位相加的和。

Examples

input

2

output

1

input

110

output

10

input

4

output

-1

解

首先将方程化为 \(x(x+s(x))=n\)

然后想到 \(O(\sqrt{n})\) 枚举 \(n\) 的因子

然后我们发现 \(s(x)<200\)

所以只需要枚举 \(\sqrt{n}±200\) 的所有因子即可

233 C

题意

给你一个 \(k\) ，要你构造一张节点数 \(\le 100\) 的图，使得图中三元环（由三个点构成的一个△）的个数恰好为 \(k\) 。 \((1\le k\le 10^5)\)

Examples

input

1

output

3

011

101

110

input

10

output

5

01111

10111

11011

11101

11110

解

我们发现节点数为 \(n(n≥3)\) 的完全图的三元环个数为 \(C^{n}_{3}\) 。

解 1（仅在节点数 \(\le 200\) 的情况下适用）

把构造的那张图看成是若干张完全图用割边连接而成的，可以用背包构造出一种方案，然后就好办了，然而发现当 \(k=100000\) 时，节点数明显超过了 \(100\) ……

解 2

\(n^3\) 枚举

#include
    
     #define maxn 103#define INF 1050000000using namespace std;bool g[maxn][maxn];int main(){    int i,j,l,k,n=100,tot=0;    scanf("%d",&k);    for(i=1;i<=n&&tot
    

233 D

题意

在 \(n*m\) 的矩阵中满足在每一个 \(n*n\) 的矩阵里有 \(k\) 个点，一共有几种画法。膜 \(10^9+7\) 。 \((n\le 100,n\le m\le 10^{18},0\le k\le n^2)\)

Examples

input

5 6 1

output

45

解

对于每一种方案，第 \(i\) 和第 \(i+n\) 行的点的个数一定相同。

所以只需要考虑 \(n*n\) 的矩阵中的情况即可。

所以我们把所有的第 \(i+k*n(k≥0)\) 列的情况一起考虑。

设 \(dp[i][j]\) 表示第 \(i\) 列及前面共放了 \(j\) 个点的方案数。

转移方程：

\(dp[i][j]=\sum_{l\in [0,\min (n,k)]} dp[i][j-l]*(C^{n}_{l})^T\) （ \(T\) 为 \(i+k*n\) 满足条件的 \(k\) 的个数）

Code

#include
    
     #define maxn 103#define maxk 10003#define INF 1050000000#define mod 1000000007using namespace std;int n,k,dp[maxn][maxk],C[maxn][maxn];long long m;int Plus(int x,int y){return (x+=y)>=mod?x%mod:x;}int mul(long long x,int y){return (x*=y)>=mod?x%mod:x;}int qpow(int x,long long y){    int ans=1;    while(y){        if(y&1)ans=mul(ans,x);        x=mul(x,x);        y>>=1;    }    return ans;}int main(){    C[1][0]=C[1][1]=1;    for(int i=2;i<=100;i++){        C[i][0]=1;        for(int j=1;j<=i;j++){            C[i][j]=Plus(C[i-1][j],C[i-1][j-1]);        }    }    cin>>n>>m>>k;    long long T=(m-1)/n;    dp[0][0]=1;    for(int i=1;i<=n;i++){        for(int l=0;l<=min(n,k);l++){            int syk=qpow(C[n][l],T+(T*n+i<=m));            for(int j=l;j<=k;j++){                dp[i][j]=Plus(dp[i][j],mul(dp[i-1][j-l],syk));            }        }    }    cout<
     
      <
     
    

233 E

感谢

题意

\(D(0)\) 是只有一个编号为 \(1\) 的结点的图。 \(D(1)\) 是只有两个编号分别为 \(1\) 和 \(2\) 的点与一条连接这两个点的边的图。 \(D(n)\) 以如下方法构造：将 \(D(n-2)\) 中所有点的编号加上 \(|D(n-1)|\) （即第 \(n-1\) 个图中的点数，或者说是最大的点的编号），在点 \(|D(n-1)|\) 与点 \(|D(n-1)|+1\) 之间连边.在点 \(|D(n-1)|+1\) 与点 \(1\) 之间连边.现在已经构造出了 \(D(n)(n≤100)\) ,她会询问 \(m\) 次在这张图中 \(a,b\) 两点间的最短路。

Examples

input

10 5

1 2

1 3

1 4

1 5

2 3

2 4

2 5

3 4

3 5

4 5

output

1

1

1

2

1

2

3

1

2

1

解

\[\color{white}{看上面链接里的博客吧。}\]