统计方案数，要么组合数，要么递推（dp）了。
这是有模拟赛历史以来爆炸最狠的一次
- T1写了正解，也想到开long long，但是开错了地方然后数组开大了结果100->0
- T3看错题本来简单模拟又给我搞成0分
- T5差分约束本来很简单但是又被我胡搞炸掉了.....
本题T4，难到爆炸的T2把我困住了.....
先讲讲考试看道题的想法：
思考了一会吗，推出几个结论，然后准备写了，感觉可以短时间A掉，结果被T2困住，一小时只优化掉了一个没啥用的n..（n^5logn的复杂度用爱过题）
然后现在来讲讲正解（也是时候背高精板子了）
首先，很容易想到，对于有0出现的数字，其结果一定是0，从而得出一个结论，对于0的结果就是10^n-9^n（不要让我证明）
然后进一步想到，对于给定k进行质因数分解，然后组合&&排列算方案数（我就是这里走了与dp不同的路）
但是发现这样并不好处理，进一步发现，如果k的质因数有大于10的，那么直接输出0（因为一个数位没法装下两个数）
然后，我在这里就暴毙了。
接下来就是正解了。
有了以上结论，我们能非常不容易地想到dp方程式：
$f[i][j][k][m][l]$表示在前i位中，2,3,5,7分别用了几次；
这个转移是真的令人折服。
for (int i = ; i <= n;i++)
{
for (int j = a2; j >= ;j--)
{
for (int k = a3; k >= ;k--)
{
for (int l = a5; l >= ;l--)
{
for (int m = a7; m >= ;m--)
{
if(j>=)
f[j][k][l][m] = f[j - ][k][l][m] + f[j][k][l][m];//
if(k>=)
f[j][k][l][m] = f[j][k - ][l][m] + f[j][k][l][m];//
if(j>=)
f[j][k][l][m] = f[j - ][k][l][m] + f[j][k][l][m];//
if(l>=)
f[j][k][l][m] = f[j][k][l - ][m] + f[j][k][l][m];//
if(j&&k)
f[j][k][l][m] = f[j - ][k - ][l][m] + f[j][k][l][m];//
if(m>=)
f[j][k][l][m] = f[j][k][l][m - ] + f[j][k][l][m];//
if(j>=)
f[j][k][l][m] = f[j - ][k][l][m] + f[j][k][l][m];//
if(k>=)
f[j][k][l][m] = f[j][k - ][l][m] + f[j][k][l][m];//
}
}
}
}
}
对每一位数进行分解，从而得出的方程，其实也不难想，只是没接触过所以想不到
于是，就可以开心地dp了吗？
不，你想死。
当n<=6的时候，方案数就已经上10万了，那么五十....
嘶~~
没有模数？？
只能写高精了。
$$但！是！$$
高精*5维数组，会炸空间的....
所以，还要像01背包那样滚掉一维，所以就出现了上述的4维方程式。
于是，代码（这个高精的缺点就在：它太长了！！！！）：
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
#define re register
#define max(x,y) ((x)>(y)?(x):(y))
struct node
{
int len,s[];
node(){memset(s,,sizeof(s)); len=;}
node(int val) {*this=val;}
node(const char *val) {*this=val;}
node operator = (const int &val)
{
re char s[];
sprintf(s,"%d",val);
*this=s;return *this;
}
node operator = (const char *val)
{
len=strlen(val);
while(len>&&val[]=='') ++val,len--;
for(re int i=;i<len;++i) s[i]=val[len-i-]-'';
return *this;
}
inline void deal()
{
while(len>&&!s[len-]) len--;
}
node operator + (const node &a) const
{
node res;res.len=;
re int top=max(len,a.len),add=;
for(re int i=;add||i<top;++i)
{
re int now=add;
if(i<len) now+=s[i];
if(i<a.len) now+=a.s[i];
res.s[res.len++]=now%;
add=now/;
}
return res;
}
node operator - (const node &a) const
{
node res; res.len=;re int del=;
for(re int i=;i<len;++i){
re int now=s[i]-del;
if(i<a.len) now-=a.s[i];
if(now>=) del=;
else del=,now+=;
res.s[res.len++]=now;
}
res.deal(); return res;
}
node operator * (const node &a) const
{
node res; res.len=len+a.len;
for(re int i=;i<len;++i)
for(re int j=;j<a.len;++j)
res.s[i+j]+=s[i]*a.s[j];
for(re int i=;i<res.len;++i)
res.s[i+]+=res.s[i]/,res.s[i]%=;
res.deal(); return res;
}
node operator / (const node &a) const
{
node res,cur=;res.len=len;
for(re int i=len-;~i;--i){
cur=cur*,cur.s[]=s[i];
while(cur>=a)
cur-=a,res.s[i]++;
}
res.deal(); return res;
}
node operator % (const node &a) const
{
node res=*this/a;
return *this-res*a;
}
node operator += (const node &a) {*this=*this+a; return *this;}
node operator -= (const node &a) {*this=*this-a; return *this;}
node operator *= (const node &a) {*this=*this*a; return *this;}
node operator %= (const node &a) {*this=*this%a; return *this;}
bool operator < (const node &a) const
{
if(len!=a.len) return len<a.len;
for(re int i=len-;~i;i--)
if(s[i]!=a.s[i]) return s[i]<a.s[i];
return false;
}
bool operator > (const node &a) const {return a<*this;}
bool operator <= (const node &a) const {return !(*this>a);}
bool operator >= (const node &a) const {return !(*this<a);}
bool operator == (const node &a) const {return !(*this>a||*this<a);}
bool operator != (const node &a) const {return *this>a||*this<a;}
}; inline void print(const node &a)
{
for(re int i=a.len-;~i;--i)
printf("%d",a.s[i]); puts("");
}
int n,k,m;
node f[][][][];
int a2,a3,a5,a7;
void solve()
{
node a,b;
a.s[]=;
b.s[]=;
for(int i=;i<=n;i++)
{
a*=;
b*=;
}
b-=a;
print(b);
}
int main()
{
scanf("%d%d", &n, &k);
if(k==)
{
solve();
return ;
}
int t = k;
while (k % == )
a2++,k /= ;
while (k % == )
a3++, k /= ;
while (k % == )
a5++, k /= ;
while (k % == )
a7++, k /= ;
if(k!=)
{
printf("");
return ;
}
f[][][][].s[] = ;
f[][][][].len = ;
for (int i = ; i <= n;i++)
{
for (int j = a2; j >= ;j--)
{
for (int k = a3; k >= ;k--)
{
for (int l = a5; l >= ;l--)
{
for (int m = a7; m >= ;m--)
{
if(j>=)
f[j][k][l][m] = f[j - ][k][l][m] + f[j][k][l][m];//
if(k>=)
f[j][k][l][m] = f[j][k - ][l][m] + f[j][k][l][m];//
if(j>=)
f[j][k][l][m] = f[j - ][k][l][m] + f[j][k][l][m];//
if(l>=)
f[j][k][l][m] = f[j][k][l - ][m] + f[j][k][l][m];//
if(j&&k)
f[j][k][l][m] = f[j - ][k - ][l][m] + f[j][k][l][m];//
if(m>=)
f[j][k][l][m] = f[j][k][l][m - ] + f[j][k][l][m];//
if(j>=)
f[j][k][l][m] = f[j - ][k][l][m] + f[j][k][l][m];//
if(k>=)
f[j][k][l][m] = f[j][k - ][l][m] + f[j][k][l][m];//
}
}
}
}
}
print(f[a2][a3][a5][a7]);
return ;
}