排列组合 QWQ
当我第一眼看见这到题,K 才 15???,于是默默的打出了暴搜。
以我这么高(la)超(ji)的水平,当然是
TLE.....
对着屏幕一呆,70行代码。。。。
步入正题:
再打深搜,那是不可能的。
发现:总方案数不就是对于每一个数的方案数乘起来吗?
注意:
- 对于数字a,b,c, 若a可以变成b,b可以变成c,那么a就可以变成c。如何解决呢?_____(
水水的floyd)。 - 注意到(n < $10^{30}$) 。 所以...高精度?(
没错)no~ no~ no~,可以用__int128。
算法设计:
- 读入,顺便将u , v存入二维表$vis$, $vis[i][j]$表示 i 到 j是否可变。
- 跑一遍floyd;
- 将点 i (0 <= i <= 9)的出度个数用be[]数组存起来。
- ans将$be[i]$ 一个一个乘起来
- 完美输出
AC Code:
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int N = 100,INF=1e9,mod=INF+7;
int be[N];
bool vis[N][N];
__int128 read()
{
__int128 f=1,w=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
w=w*10+ch-'0';
ch=getchar();
}
return f*w;
}
void print(__int128 x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)print(x/10);
putchar(x%10+'0');
}
int main()
{
__int128 ans=1,n;
int k,a,b;
n = read();
cin >> k;
rep(i,1,k){
cin >> a >> b;
vis[a][b] = 1;
}
rep(k,0,9)rep(i,0,9)rep(j,0,9)if(i==j || (vis[i][k] && vis[k][j]))vis[i][j] = true;
rep(i,0,9)
rep(j,0,9)
if(vis[i][j])be[i]++;
while(n){
ans *= be[n%10];
n/=10;
}
print(ans);
return 0;
}
记得点个赞哟~~
标签:__,10,ch,洛谷,NOIP2002,int,rep,P1037,vis From: https://www.cnblogs.com/Vanczyx/p/16598551.html