建设通网站有建筑公司名录大全,天津市建设工程监理公司网站,团购网站模板html,网站搭建设计方案黑客#xff08;续#xff09;descriptionsolutioncodedescription
【问题描述】 在破解了世界首富 Bychaha 的银行账户后#xff0c;知名黑客 pks 发现#xff0c;要得到 Bychaha 的全部财产#xff0c;必须再破解一道密码。
作为客户账户安全的最后一道防线#xff0…
黑客续descriptionsolutioncodedescription
【问题描述】 在破解了世界首富 Bychaha 的银行账户后知名黑客 pks 发现要得到 Bychaha 的全部财产必须再破解一道密码。
作为客户账户安全的最后一道防线这一次的密码将由长达 N 位的数码组 成每一位的数码范围为[1,K]。
pks 想要估算自己破解密码的大致时间所以他想要你帮他快速计算出总 共有多少种满足条件的密码同时pks 还对每一种密码视为十进制数之后求 和的结果很感兴趣希望你也能告诉他。
当然作为世界知名黑客pks 不会傻傻的枚举他已经从银行系统中窃取 到了关于密码的 M 个信息每个信息由两个数字表示代表数码不会出 现在数码之前。
【输入格式】 第一行三个整数 NMK含义如题面所述。 接下来 M 行每行两个数。
【输出格式】 输出共两行。 第一行一个整数表示有多少种满足条件的密码。 第二行一个整数表示所有密码视为十进制数之后求和的结果。
【样例输入输出】
4 4 3
1 1
1 2
2 2
3 1 7
19020 【数据规模与约定】 对于 20%的数据, ≤ 6 对于 30%的数据, ≤ 50 对于 40%的数据, ≤ 200 另有 50%的数据 0 对于 100%的数据1 ≤ ≤ 5000 ≤ ≤ 100 , K ≤ 9
solution
当你发现没有模数的那一刻可能心脏已经跳脱了
这该死的 甜美 大数还是来了
N6
直接暴力搜索每一位选择[1,k][1,k][1,k]最后组合出来再判断 m0
没有限制条件摆明了说个数就是knk^nkn答案就是每一个数字固定在每一位的数值乘以这种形式的密码个数
直接脱光了说答案都跟你说了你写出大数就有一半的分再加上最原始的暴力就算是很不错的分了
没想到自己在考场上真的把大数敲出来了 最后就是正解了
很简单可以预处理出已经出现了sss集合内的数字且是合法的能接在后面的所有数字
设fi,s/gi,s:f_{i,s}/g_{i,s}:fi,s/gi,s: 在第iii位已经出现了sss集合内的数字的所有密码和/个数
这个状压转移应该都能写吧
但是会发现答案特别大就需要——压位高精
这里好巧不巧选择压171717位(1e171e171e17)就能过
之前以为压位很难结果发现就是将是十七位当成一位(mod1e17)\pmod {1e17}(mod1e17)就行
最后输出再每一位扩充出来%17lld\text{\%17lld}%17lld171717是表示输出是171717位不够的自动填充000
当然注意最高的一位不能扩充ta是多少位就是多少位 所以这道题的难点是压位高精
code
#pragma GCC optimize(2)
#include cstdio
#include vector
#include cstring
using namespace std;
#define int long long
const int mod 1e17;
int n, m, k;
bool vis[10][10];
vector int nxt[1 9];struct Int {int len;int c[60];Int(){ memset( c, 0, sizeof( c ) ); }Int operator * ( int x ) {Int ans;ans.len len;int add 0;for( int i 1;i len;i ) {int ret c[i] * x add;ans.c[i] ret % mod;add ret / mod;}if( add ) ans.c[ ans.len] add;return ans;}Int operator ( Int x ) {Int ans;int ip 1;while( ip x.len or ip len ) {int ret ans.c[ip] x.c[ip] c[ip];if( ret mod ) {ans.c[ip 1] ;ans.c[ip] ret - mod;}elseans.c[ip] ret; ip;}ans.len ip;if( ! ans.c[ans.len] ) ans.len --;return ans;}void print() {printf( %lld, c[len] );for( int i len - 1;i 0;i -- ) printf( %017lld, c[i] );printf( \n );}void init() {for( int i 1;i len;i ) c[i] 0;len 0;}
}f[2][1 9], g[2][1 9];signed main() {scanf( %lld %lld %lld, n, m, k );for( int i 1, a, b;i m;i ) {scanf( %lld %lld, a, b );vis[a][b] 1;}int lim 1 k;for( int s 0;s lim;s )for( int i 1;i k;i ) {for( int j 1;j k;j )if( ( 1 j - 1 s ) and vis[j][i] ) goto opt;nxt[s].push_back( i );opt :;}g[0][0].c[g[0][0].len 1] 1;for( int i 1;i n;i ) {int o i 1;for( int s 0;s lim;s )for( int j : nxt[s] ) {f[o][1 j - 1 | s] f[o][1 j - 1 | s] f[o ^ 1][s] * 10 g[o ^ 1][s] * j;g[o][1 j - 1 | s] g[o][1 j - 1 | s] g[o ^ 1][s];}for( int s 0;s lim;s )f[o ^ 1][s].init(), g[o ^ 1][s].init();}g[n 1][0].c[1] 0;for( int i 1;i lim;i ) {f[n 1][0] f[n 1][i] f[n 1][0];g[n 1][0] g[n 1][i] g[n 1][0];}g[n 1][0].print();f[n 1][0].print();return 0;
}
