题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=5936
题目大意:
(y每位上的数字的K次幂之和)
X=f(y,K)-y。现在给定X和K,求有多少Y满足题意。
数据范围
题目思路:
【中途相遇法】
数据范围x在[0,10],y的位数不会超过10位。
所以想直接对半分,先枚举前5位,记下相应的值,再枚举后5位,与前面的匹配看是否能够凑成x,最后统计答案即可。
一开始用map写,T了。一脸懵逼。
后来改成将每个出现的值都记下来,排序,正反扫一遍。。过了。
可以预处理一些操作、运算。
//
//by coolxxx
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<bitset>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//#include<stdbool.h>
#include<math.h>
#pragma comment(linker,"/STACK:1024000000,1024000000")
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define eps (1e-8)
#define J 10000
#define mod 1000000007
#define MAX 0x7f7f7f7f
#define PI 3.14159265358979323
#define N 14
#define M 100004
using namespace std;
typedef long long LL;
double anss;
LL aans;
int cas,cass;
int n,m,lll,ans;
LL e[N];
LL mi[N][N],c[N][M],d[N][M];
bool cmp(int a,int b)
{
return a<b;
}
void init()
{
int i,j;
for(e[]=,i=;i<;i++)e[i]=e[i-]*;
for(i=;i<;i++)
{
mi[i][]=;
for(j=;j<;j++)mi[i][j]=mi[i][j-]*i;
}
for(j=;j<;j++)
{
for(i=;i<e[];i++)
c[j][i]=mi[i/e[]][j]+mi[i%e[]/e[]][j]+mi[i%e[]/e[]][j]+mi[i%e[]/e[]][j]+mi[i%e[]][j]-i*e[],
d[j][i]=mi[i/e[]][j]+mi[i%e[]/e[]][j]+mi[i%e[]/e[]][j]+mi[i%e[]/e[]][j]+mi[i%e[]][j]-i;
sort(c[j],c[j]+e[],cmp);
sort(d[j],d[j]+e[],cmp);
}
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k;
int x,y,z;
init();
// for(scanf("%d",&cass);cass;cass--)
for(scanf("%d",&cas),cass=;cass<=cas;cass++)
// while(~scanf("%s",s))
// while(~scanf("%d%d",&n,&m))
{
printf("Case #%d: ",cass);
ans=;
scanf("%d%d",&n,&m);
for(i=,j=e[]-;i<e[] && j;)
{
if(c[m][i]+d[m][j]>n)j--;
else if(c[m][i]+d[m][j]<n)i++;
else
{
x=y=;
while(c[m][++i]==c[m][i-] && i<e[])x++;
while(d[m][--j]==d[m][j+] && j)y++;
ans+=x*y;
}
}
printf("%d\n",ans-(n==));
}
return ;
}
/*
// //
*/