CodeForces 582D Number of Binominal Coeficients

https://codeforces.com/contest/582/problem/D

给出 \(p\) ,和 \(\alpha,A\) ,求有多少 \(0 \le k \le n \le A\) 满足

答案对 \(10^9+7\) 取模

\(1 \le p \le \alpha \le 10^9\)

\(0 \le A < 10^{1000}\)

Tutorial

如何求最大的 \(\alpha\) 使得 \(p^{\alpha} \mid n!\) .

其中 \(m\) 为最大的使得 \(p^m \le n\) 的数.

那么 \(\binom nk\) 的 \(\alpha\) 就是

由于 \(n = k + (n - k)\) ,所以这可以看作 \(k+(n-k)\) 做 \(k\) 进制加法时的进位次数.

所以当 \(\alpha \ge m\) 时无解.

设 \(dp[i][x][e][r]\) 表示考虑了\(A\) 的 \(p\) 进制前 \(i\) 位,当前的 \(n\) 的前缀是否等于 \(A\) 的前缀(\(e\)),共进位了 \(x\) 次,当前位置是否需要进位 \(r\) .

若枚举 \(n,k\) 这一位的取值,复杂度无法接受.

发现转移时合法的 \(n,k\) 是一个算术级数的形式,可以直接 \(O(1)\) 转移.

复杂度 \(O(|A|^2)\)

Code

参考博客 https://codeforces.com/contest/582/submission/13390698

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
template<class T> inline void read(T &x) {
	x=0; int f=1,ch=getchar();
	while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
	while(ch>=‘0‘&&ch<=‘9‘){x=x*10-‘0‘+ch;ch=getchar();}
	x*=f;
}
typedef long long ll;
const int mod=1e9+7;
const int maxn=3400;
int p;
int alpha;
int dp[maxn][maxn][2][2];
char s[maxn];
inline int sub(int x) {return x<0?x+mod:x;}
inline int Add(int &x,int y) {x+=y; if(x>=mod) x-=mod;}
int div(vector<int> &a,int b,vector<int> &re) {
	re.clear();
	ll rest=0;
	for(int i=0;i<a.size();++i) {
		rest=rest*10+a[i];
		if(re.size()||rest>=b) re.push_back(rest/b);
		rest%=b;
	}
	return rest;
}
inline int calw(int c,int r,int nr)
{
	if(r) return p-calw(c,!r,nr);
	return c+1-nr;
}
inline int calW(int c,int r,int nr)
{
	if(r) return sub((ll)p*(c+1)%mod-calW(c,!r,nr));
	return sub((ll)(c+2)*(c+1)/2%mod-nr*(c+1));
}
int main()
{
	// freopen("in.txt","r",stdin);
	// freopen("out.txt","w",stdout);
	read(p),read(alpha);
	scanf("%s",s);
	vector<int> a; a.resize(strlen(s));
	for(int i=0;i<a.size();++i) {
		a[i]=s[i]-‘0‘;
	}
	vector<int> b,c;
	while(a.size()) {
		c.push_back(div(a,p,b));
		a=b;
	}
	reverse(c.begin(),c.end());
	int n=c.size();
	if(alpha>n){puts("0"); return 0;}
	dp[0][0][1][0]=1;
	for(int i=0;i<n;++i) {
		for(int x=0;x<=alpha;++x) {
			for(int e=0;e<2;++e) {
				for(int r=0;r<2;++r) if(dp[i][x][e][r]) {
					for(int nr=0;nr<2;++nr) {
						int nx=min(x+nr,alpha);
						if(!e) Add(dp[i+1][nx][e][nr],(ll)calW(p-1,r,nr)*dp[i][x][e][r]%mod);
						else {
							if(c[i]) Add(dp[i+1][nx][!e][nr],(ll)calW(c[i]-1,r,nr)*dp[i][x][e][r]%mod);
							Add(dp[i+1][nx][e][nr],(ll)calw(c[i],r,nr)*dp[i][x][e][r]%mod);
						}

					}
				}
			}
		}
	}
	int re=0;
	for(int e=0;e<2;++e) Add(re,dp[n][alpha][e][0]);
	printf("%d\n",re);
	return 0;
}

CodeForces 582D Number of Binominal Coeficients

原文：https://www.cnblogs.com/ljzalc1022/p/13045646.html