2022春训第四场
补题链接
总结另外写了，这里只是题解(补题记录)。
[B]
题意：
求 \([x,y]\) 内所有数字（作为一个0~9数字串）的顺序对之和。\(1 \leq x \leq y \leq 10^{14}\) 。
分析：
数位DP。可以预处理一个 \(f[i][t]\) 表示后面有 \(i\) 位数字可以任选，对当前位选 \(t\) 的贡献。那么
$ f[i][t] = \sum_{k=1}^{i} C_{i}^{k} (9-t)^k (t+1)^{i-k} k $
还有各种边角情况，都写在代码注释里了。此题比较核心的思路就是分开每一位算贡献，然后预处理和dfs结合。
代码如下
#include
using namespace std;
#define ll long long
int const N=20;
ll f[N][N],c[N],fac[N];
int a[N];
ll rd()
{
char ch=getchar(); ll ret=0,f=1;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();
return ret*f;
}
ll pw(ll x,int y)
{ll ret=1; while(y){if(y&1)ret*=x; x*=x; y>>=1;} return ret;}
ll C(int n,int m){return fac[n]/fac[m]/fac[n-m];}
void Init()
{
fac[0]=1;
for(int i=1;i<=14;i++)fac[i]=fac[i-1]*i;
for(int i=1;i<=14;i++)
for(int t=0;t<=9;t++)
{
for(int k=1;k<=i;k++)
f[i][t] += C(i,k)*pw(9-t,k)*pw(t+1,i-k)*k; // i位可以自由选择，对当前位数字t的贡献
c[i] += f[i][t]; // i位可以自由选择，对当前数字(0~9)的贡献
}
}
ll get(ll x,int p){return x/pw(10,p);} // 第p位前面的数(不含p)
ll get2(ll x,int p){return x%pw(10,p-1);} // 第p位后面的数(不含p)
ll dfs(ll x,int p,int t) // 当前为第p位，前面已达到最大值，求对t的贡献
{
if(p==0)return 0;
ll ret=0;
for(int k=0;kt) ret += get2(x,p)+1; // 第p位取a[p]时，第p位对t的贡献
// printf("get2(%lld,%d)=%lld\n",x,p,get2(x,p));
ret += dfs(x,p-1,t); // 第p位取a[p]时，后面p-1位对t的贡献
// printf("dfs:p=%d t=%d ret=%lld\n",p,t,ret);
return ret;
}
ll solve(ll x)
{
int n=0; ll ret=0,tx=x;
while(tx) a[++n]=tx%10, tx/=10;
for(int i=1;i<=n;i++)
{
for(int t=1;t