二项式定理+前缀Sigma
2024-10-06 20:12:21
https://hihocoder.com/problemset/problem/1430
思路:
要用前缀去推Sigma总公式,比较方便。https://blog.csdn.net/weixin_37517391/article/details/83821752
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#include <cstdio>//sprintf islower isupper
#include <cstdlib>//malloc exit strcat itoa system("cls")
#include <iostream>//pair
#include <fstream>//freopen("C:\\Users\\13606\\Desktop\\草稿.txt","r",stdin);
#include <bitset>
//#include <map>
//#include<unordered_map>
#include <vector>
#include <stack>
#include <set>
#include <string.h>//strstr substr
#include <string>
#include <time.h>//and(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
#include <cmath>
#include <deque>
#include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
#include <vector>//emplace_back
//#include <math.h>
//#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
#include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
#define rint register int
#define fo(a,b,c) for(rint a=b;a<=c;++a)
#define fr(a,b,c) for(rint a=b;a>=c;--a)
#define mem(a,b) memset(a,b,sizeof(a))
#define pr printf
#define sc scanf
#define ls rt<<1
#define rs rt<<1|1
typedef long long ll;
void swapp(int &a,int &b);
double fabss(double a);
int maxx(int a,int b);
int minn(int a,int b);
int Del_bit_1(int n);
int lowbit(int n);
int abss(int a);
const double E=2.718281828;
const double PI=acos(-1.0);
//const ll INF=(1LL<<60);
const int inf=(<<);
const double ESP=1e-;
const int mod=(int)1e9+;
const int N=(int)5e4+; long long C[][];
void Init() {
C[][] = ;
for(int i = ;i <= ;++i) {
C[i][] = ;
for(int j = ;j <= i;++j) {
C[i][j] = (C[i-][j-] + C[i-][j]) % mod;
}
}
}
//======================================================Cnk预处理;
ll S[][N],SS[][N],ans[N];
char s[N]; void solve()
{
ll n,k;
sc("%lld%lld",&n,&k);
sc("%s",s); for(int i = ;i <= n;++i) S[][i] = ;
for(int i = ;i <= n;++i) S[][i] = (s[i-]-'') + S[][i-] ;
for(int i = ;i <= k;++i)
for(int j = ;j <= n;++j)
S[i][j] = S[][j] * S[i-][j] % mod; SS[][] = ; for(int i = ;i <= k;++i) {
for(int j = ;j <= n;++j)
SS[i][j] = (SS[i][j-] + S[i][j])%mod;
} for(int i=;i<=n;++i)
{
ll sum=;
for(int j=;j<=k;++j)
{
ll temp=C[k][j]*S[k-j][i]%mod*SS[j][i-]%mod;
if(j&)
sum=(sum-temp+mod)%mod;
else
sum=(sum+temp)%mod;
}
ans[i]=sum;
}
for(int i=;i<=n;++i)
pr("%lld%c",ans[i],i==n?'\n':' ');
} int main()
{
Init();
int T;
sc("%d",&T);
while(T--)solve();
return ;
} /**************************************************************************************/ int maxx(int a,int b)
{
return a>b?a:b;
} void swapp(int &a,int &b)
{
a^=b^=a^=b;
} int lowbit(int n)
{
return n&(-n);
} int Del_bit_1(int n)
{
return n&(n-);
} int abss(int a)
{
return a>?a:-a;
} double fabss(double a)
{
return a>?a:-a;
} int minn(int a,int b)
{
return a<b?a:b;
}
最新文章
- ASP.NET MVC 5 Web编程1 -- 入门
- maven install Failed to execute goal org.apache.maven.plugins:maven-war-plugin:2.1.1:war (default-war) on project web_nanchang
- 安装Office 2010后出现正在配置
- SQL Server 的通用分页显示存储过程
- Too many connections解决方案
- 作业七:团队项目——Alpha版本冲刺阶段-05
- is A和has A的区别
- struts2 零配置
- android 后台附件下载
- oracle行号排序问题
- LeetCode_Letter Combinations of a Phone Number
- 在Android中改动快捷方式的图标
- ruby 删除文件夹(包括文件夹中的文件夹和文件)
- LeetCode——Longest Palindromic Substring
- flash Ane
- NHibernate Criteria中 Restriction与Expression的差别
- pwnable.tw calc
- springclound
- 【webpack】中file-loader和url-loader使用方法
- Listbox的操作,数据源变化时要及时更新listbox要先把数据源置空,在给数据源绑定数据