欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

717 Bubble Cup 9 - Finals [Online Mirror]

程序员文章站 2022-05-09 21:15:45
...

签到题：

C. Potions Homework

题意：n个人，n个任务，第i个人和第i个任务权值相同，现要求重新分配任务，令每个人和它做的任务的权值之积的和最小

直接最小和最大，次小和次大乘起来完事，微扰可证

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int _=1e2;
const int maxn=1e5+_;
 
LL a[maxn];
int main()
{
	int n;LL ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
		ans+=a[i]*a[n-i+1]%10007,ans%=10007;
	printf("%d\n",ans);
	
	return 0;
}
D. Dexterina’s Lab

题意：多堆nim游戏，任意取石子。共n个石子堆，每个石子堆的石子数是[0,x]中一个整数，给出每个石子数的概率，问先手胜的概率。

只要知道sg函数是石子堆异或起来就行了吧。

设f[i][j]f[i][j]表示枚举到第i堆，sg值为j的概率，矩乘优化即可。

注意虽然x<=100，但是异或和可以到127

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int _=1e2;
const int maxn=1e5+_;
int n,m;
 
struct Matrix
{
    double mp[210][210];
    Matrix(){memset(mp,0,sizeof(mp));}
    friend Matrix operator *(Matrix a,Matrix b)
    {
        Matrix c;
        memset(c.mp,0,sizeof(c.mp));
        for(int i=0;i<=127;i++)
            for(int j=0;j<=127;j++)
                for(int k=0;k<=127;k++)
                    c.mp[i][j]+=a.mp[i][k]*b.mp[k][j];
        return c;
    }
}ans,A;
 
double p[210];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<=m;i++)scanf("%lf",&p[i]);
	
	for(int i=0;i<=127;i++)
	{
		for(int j=0;j<=127;j++)//由i转移到j 
			A.mp[i][j]+=p[i^j];
	}
	ans.mp[0][0]=1;
	while(n!=0)
	{
		if(n%2==1)ans=ans*A;
		A=A*A;n/=2;
	}
	printf("%.8lf\n",1.0-ans.mp[0][0]);
			
	return 0;
}
E. Paint it really, really dark gray

题意：给一棵树，树点有黑白色，访问一次变色，询问从1出发把整棵树染黑的任意方案

1开始搜一次，经过就变色，每个子树保证它全黑了（除了根）再回溯。假如子树的根是白的就再去一次，如果最后1是白的就和随便一个孩子来回一下

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int _=1e2;
const int maxn=1e5+_;
 
struct node
{
	int x,y,next;
}a[2*maxn];int len,last[maxn];
void ins(int x,int y)
{
	len++;
	a[len].x=x;a[len].y=y;
	a[len].next=last[x];last[x]=len;
}
 
int c[maxn];
void dfs(int x,int fa)
{
	c[x]^=1,printf("%d ",x);
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y!=fa)
        {
	        dfs(y,x);
			c[x]^=1,printf("%d ",x);
	        if(c[y])
			{
				c[y]^=1,printf("%d ",y);
				c[x]^=1,printf("%d ",x);
			}
		}
    }
    if(x==1&&!c[x])
    {
    	int k=last[x];
    	int y=a[k].y;
		c[y]^=1,printf("%d ",y);
		c[x]^=1,printf("%d ",x);
		c[y]^=1,printf("%d ",y);
	}
}
 
int main()
{
    int n,x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(x==-1)c[i]=1;
        else c[i]=0;
    }
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        ins(x,y),ins(y,x);
    }
    dfs(1,0);
    
    return 0;
}
G. Underfail

题意：给一个串，给m个单词，若其被串识别有收益di，当前串同一位置只能被识别x次，单词不能被相同的一段识别多次，求最大收益。（识别的条件为单词出现在串[l,r]位置）

费用流。原点和汇点分别连1位置和n位置，位置之间相邻相连，流量为x，单词若能被串的[l,r]识别，l向r+1连流量为1，费用为收益的边，跑最大费用流即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int _=1e2;
const int maxn=1e5+_;
 
struct node
{
    int x,y,c,d,next;
}a[20*maxn];int len,last[maxn];
void ins(int x,int y,int c,int d)
{
//	printf("%d %d %d %d\n",x,y,c,d);
    len++;
    a[len].x=x;a[len].y=y;a[len].c=c;a[len].d=d;
    a[len].next=last[x];last[x]=len;
    
    len++;
    a[len].x=y;a[len].y=x;a[len].c=0;a[len].d=-d;
    a[len].next=last[y];last[y]=len;
}
 
int st,ed;
int pre[maxn],c[maxn],ans,d[maxn];
int list[maxn];bool v[maxn];
bool spfa()
{
    memset(d,-63,sizeof(d));d[st]=0;c[st]=(1<<30);
    memset(v,false,sizeof(v));v[st]=true;
    int head=1,tail=2;list[1]=st;
    while(head!=tail)
    {
        int x=list[head];
        for(int k=last[x];k;k=a[k].next)
        {
            int y=a[k].y;
            if(a[k].c>0&&d[y]<d[x]+a[k].d)
            {
                d[y]=d[x]+a[k].d;
                c[y]=min(a[k].c,c[x]);
                pre[y]=k;
                if(v[y]==false)
                {
                    v[y]=true;
                    list[tail]=y;
                    tail++;if(tail==maxn)tail=1;
                }
            }
        }
        v[x]=false;
        head++;if(head==maxn)head=1;
    }
    if(d[ed]==d[ed+1])return false;
    else
    {
        int y=ed;ans+=c[ed]*d[ed];
        while(y!=st)
        {
            int k=pre[y];
            a[k].c-=c[ed];
            a[k^1].c+=c[ed];
            y=a[k].x;
        }
        return true;
    }
}
 
char ss[maxn],sa[maxn];
bool check(int len,int j)
{
	for(int i=1;i<=len;i++,j++)
		if(ss[j]!=sa[i])return false;
	return true;
}
int main()
{
	int n,m,x;
	scanf("%d%s%d",&n,ss+1,&m); len=1;
	st=0,ed=n+1;
	for(int i=1;i<=m;i++)
	{
		scanf("%s%d",sa+1,&x);int len=strlen(sa+1);
		for(int j=1;j<=n-len+1;j++)
			if(check(len,j))ins(j,j+len,1,x);
	}
	scanf("%d",&x);
	for(int i=1;i<=n+1;i++)ins(i-1,i,x,0);
	
	ans=0;
    while(spfa());
    printf("%d\n",ans);
    return 0;
}

中档题

H. Pokermon League challenge

题意：有n个人，有e个人之间相互讨厌，每个人能够加入某些团队（16<=能加入的团队数<=20）。现在需要把团队分成两组，然后每个人加入自己能加入的团队的其中一个，要求不同组且相互讨厌的人对数>=e/2，n≤5e4,e≤1e5n\leq5e4,e\leq1e5

由于数据过弱，直接随机团队分组和人加入的团队并暴力验证的运行速度几乎等同正解

对于一个给定方案，由于能加入的团队>=16的限制存在大量增广路，其必定有解，否则必定没有合法方案

我们先确定人在哪个组，然后再用团队去满足它。枚举每个人，然后让其选择当前讨厌的人较少的组加入，由于每次讨厌的人的对数均大于等于当前决策的一半，所以能够满足e/2那个条件

考虑分配团队的方式，如果我们使用随机化分配的方式，对于一个人来说，它没能加入它想要的组只有它所有能够加入的团队都去了另一个组，这种情况出现的最大概率为12161\over 2^{16}，n个中随便有一个出锅的概率为n216≈77%{n\over 2^{16}}\approx77\%，随机三十次出锅的概率为0.7730≈0.00040.77^{30}\approx0.0004。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int _=1e2;
const int maxn=5e4+_;
const int maxm=1e5+_;
 
int as[maxn],ans[maxn],c[maxm],g[maxn][22];
vector<int>h[maxn];
int main()
{
	int n,m,x,y,L=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		if(x<y)swap(x,y);
		h[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&g[i][0]);
		for(int j=1;j<=g[i][0];j++)
			scanf("%d",&g[i][j]),L=max(L,g[i][j]);
	}
	
	for(int i=1;i<=n;i++)
	{
		int aa=0,bb=0;
		for(int j=0;j<h[i].size();j++)
			if(as[h[i][j]]==0)aa++;
			else bb++;
		as[i]=aa>=bb;
	}
	srand(252628);
	bool bk=false;
	while(bk==false)
	{
		for(int i=1;i<=L;i++)c[i]=rand()%2;
		bk=true;
		for(int i=1;i<=n;i++)
		{
			bool flag=false;
			for(int j=1;j<=g[i][0];j++)
				if(c[g[i][j]]==as[i]){ans[i]=g[i][j];flag=true;break;}
			if(!flag)
				{bk=false;break;}
		}
	}
	for(int i=1;i<n;i++)printf("%d ",ans[i]); printf("%d\n",ans[n]);
	for(int i=1;i<L;i++)printf("%d ",c[i]+1); printf("%d\n",c[L]+1);
	
	return 0;
}
B. R3D3’s Summer Adventure

题意：你需要构造一个大小为n的01密码表，要求密码表中没有一个密码是另一个的前缀，一个密码的代价为0的个数 *c0+1的个数 *c1，求最小代价。

容易想到一个贪心做法，初始将空(0费)压入堆，然后每次取堆中费用最小的元素，将其复制并在尾分别加0或1。进行n-1次即为为答案。关于正确性每次分裂增加费用为c1+c0+模版总费用。

这题并不需要输出方案，那么我们可以将相同费用的密码同时分裂。利用map将费用为i的密码出现次数保存，由小到大分裂即可。关于时间复杂度，据说增长速度和斐波那契数列相若。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
 
map<LL,int>mp; map<LL,int>::iterator it;
int main()
{
	int n,c0,c1;
	scanf("%d%d%d",&n,&c0,&c1);
	if(c0==0||c1==0){printf("%lld\n",(LL)(n-1)*(c0+c1));return 0;}
	
	mp[0]=1;int u=n-1;
	it=mp.begin();
	while(1)
	{
		if(u>it->second)
			mp[it->first+c0]+=it->second,mp[it->first+c1]+=it->second;
		else
		{
			mp[it->first+c0]+=u,mp[it->first+c1]+=u;
			it->second-=u;
			break;
		}
		u-=it->second;
		it++;
	}
	LL ans=0;
	for(;it!=mp.end();it++)
		ans+=(it->first)*(it->second);
	printf("%lld\n",ans);
		
	return 0;
}

较难题：

F. Heroes of Making Magic III

题意：给一行n个格子，格子上有小鬼，两个操作：给格子加小鬼；询问能否击败[l,r]的所有小鬼。（注意问完小鬼不消失）击败指从l出发，击败当前位置一个小鬼，然后向[l,r]中的相邻位置走，最后走到r。

发现小鬼数目代表了若能成功击败所有小鬼的路径中对应位置的度数。对于所有的点，一定要向左右都走固定次。

那么我们可以在左边界和它右边的位置来回走，直到把边界的度数消耗完，然后把边界右边的位置当作新的边界继续进行。只要满足了度数限制就可以了。

仅仅知道这个是不够的，进行进一步分析。假设我们现在把这一段取出来放在a1,a2……ana_1,a_2……a_n，需要满足以下不等式：

a1−1≥0a_1-1\geq 0（第一步）a2−a1≥0a_2-a1\geq 0 （能够在1、2之间来回走并到达2位置）

（这两个比较特殊）

a3−1−(a2−a1)≥0a_3-1-(a_2-a1)\geq 0 （先从2走到3，然后能够消去2剩下的）

a4−1−[a3−1−(a2−a1)]≥0a_4-1-[a_3-1-(a_2-a1)]\geq 0 （先从3走到4，然后能够消去3剩下的）

…………

整理可得：

∑j=1i(−1)i−jaj≥i%2\sum^i_{j=1}(-1)^{i-j}a_j\geq i\%2 (0≤i&lt;n)(0\leq i&lt; n)， ∑j=1i(−1)i−jaj=i%2\sum^i_{j=1}(-1)^{i-j}a_j=i\%2 (i=n)(i=n) (最后要消完)

于是初始时我们可以从左到右令ai−=ai−1a_i-=a_{i-1}，然后按下标分奇偶建线段树，询问就是问区间内最小值然后拿去和0或1比较，增加对于偶数长度相当于给 和这个区间左界奇偶性相同的点都增加k，对于奇数的情况我们可以先进行一次单点修改，即令该点以后和它奇偶性相同的点都加k，不同的都减k

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define lc (now<<1)
#define rc (now<<1)|1
#define mid (ql+qr)/2
using namespace std;
const int _=1e2;
const int maxn=2e5+_;
const int fbin=(1<<18);
 
struct TR
{
	int n;
	struct trnode
	{
		int c,la;
	}tr[2*fbin];int num[maxn];
	void update(int now){tr[now].c=min(tr[lc].c,tr[rc].c);}
	void pushdown(int now)
	{
		tr[lc].c+=tr[now].la,tr[lc].la+=tr[now].la;
		tr[rc].c+=tr[now].la,tr[rc].la+=tr[now].la;
		tr[now].la=0;
	}
	void bt(int now,int ql,int qr)
	{
		if(ql==qr)tr[now].c=num[ql];
		else bt(lc,ql,mid),bt(rc,mid+1,qr),update(now);
	}
	void change(int now,int ql,int qr,int l,int r,int k)
	{
		if(l>r||r>qr)return ;
		if(ql==l&&qr==r)
		{
			tr[now].c+=k;tr[now].la+=k;
			return ;
		}
		pushdown(now);
			 if(r<=mid)  change(lc,ql,mid,l,r,k);
		else if(mid+1<=l)change(rc,mid+1,qr,l,r,k);
		else change(lc,ql,mid,l,mid,k),change(rc,mid+1,qr,mid+1,r,k);
		update(now);
	}
	int getmin(int now,int ql,int qr,int l,int r)
	{
		if(l<ql)return 0;
		if(l>r||r>qr)return (1<<30);
		if(ql==l&&qr==r)return tr[now].c;
		pushdown(now);
			 if(r<=mid)  return getmin(lc,ql,mid,l,r);
		else if(mid+1<=l)return getmin(rc,mid+1,qr,l,r);
		else return min(getmin(lc,ql,mid,l,mid),getmin(rc,mid+1,qr,mid+1,r));
		update(now);
	}
}T[2];
 
inline int id(int x){return (x+1)/2;}
int main()
{
	int n,x,la=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x),x-=la,la=x;
		T[i%2].num[id(i)]=x;
	}
	T[0].n=n/2,T[0].bt(1,1,T[0].n);
	T[1].n=(n+1)/2,T[1].bt(1,1,T[1].n);
	int Q,op,l,r,w,k;
	scanf("%d",&Q);
	while(Q--)
	{
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d%d%d",&l,&r,&k); l++,r++;
			w=l%2;
			if((r-l+1)%2==1)
			{
				T[w].change(1,1,T[w].n,id(l),T[w].n,k);
				T[w^1].change(1,1,T[w^1].n,id(l+1),T[w^1].n,-k);
				l++;
			}
			w=l%2;
			if(l<r)
				T[w].change(1,1,T[w].n,id(l),id(r-1),k);
		}
		else
		{
			bool bk=true;
			scanf("%d%d",&l,&r); l++,r++;
			w=l%2;
			if(l==r)bk=(T[w].getmin(1,1,T[w].n,id(l),id(l))==1);
			else
			{
				if((r-l+1)%2==1)
				{
					int B=T[w^1].getmin(1,1,T[w^1].n,id(l-1),id(l-1));
					bk&=(T[w].getmin(1,1,T[w].n,id(l),id(r))+B>=1);
					bk&=(T[w^1].getmin(1,1,T[w^1].n,id(l+1),id(r-1))-B>=0);
					bk&=(T[w].getmin(1,1,T[w].n,id(r),id(r))+B==1);
				}
				else
				{
					int B=T[w^1].getmin(1,1,T[w^1].n,id(l-1),id(l-1));
					bk&=(T[w].getmin(1,1,T[w].n,id(l),id(r-1))+B>=1);
					bk&=(T[w^1].getmin(1,1,T[w^1].n,id(l+1),id(r))-B>=0);
					bk&=(T[w^1].getmin(1,1,T[w^1].n,id(r),id(r))-B==0);
				}
			}
			puts(bk?"1":"0");
		}
	}
	
	return 0;
}
A. Festival Organization

题意：长度在[l,r]中的01串，在长度相同的串中选出k个的总方案数k≤200,l、r≤1e18k\leq 200,l、r\leq1e18

长度为i的不同01串个数为fibifib_i，即问∑i=lr(kfibi+2)\sum^r_{i=l}{k\choose fib_{i+2}}

稍微改改输入的lr，然后分开算，即问∑i=1n(kfibi)\sum^n_{i=1}{k\choose fib_{i}}

KaTeX parse error: Got function '\underline' with no arguments as superscript at position 27: …\sum^n_{i=1}fib^̲\underline k_i

KaTeX parse error: Got function '\underline' with no arguments as superscript at position 27: …\sum^n_{i=1}fib^̲\underline k_i

=1k∑i=1n∑j=0k[kj](−1)k−jfibij={1\over k}\sum^n_{i=1}\sum^k_{j=0}{k\brack j}(-1)^{k-j}fib_i^j（换入第一类斯特林数）

=1k∑j=0k[kj](−1)k−j∑i=1nfibij={1\over k}\sum^k_{j=0}{k\brack j}(-1)^{k-j}\sum^n_{i=1}fib_i^j

令G(n,j)=∑i=1nfibijG(n,j)=\sum^n_{i=1}fib_i^j 只要快速算出这个东西就行了，前面只有O(k)O(k)的花费

（下面用G(n,k)G(n,k)推）

G(n,k)=∑i=1nfibikG(n,k)=\sum^n_{i=1}fib_i^k

=∑i=1n[(1+52)i−(1−52)i5]k=\sum^n_{i=1}[{({1+\sqrt 5\over2})^i-({1-\sqrt 5\over2})^i\over \sqrt 5}]^k

=(15)k∑i=1n[(1+52)i−(1−52)i]k=({1\over \sqrt 5})^k\sum^n_{i=1}[{({1+\sqrt 5\over2})^i-({1-\sqrt 5\over2})^i}]^k

=(15)k∑i=1n∑j=0k(kj)∗(1+52)i(k−j)∗[−(1−52)i]j=({1\over \sqrt 5})^k\sum^n_{i=1}\sum^k_{j=0}{k\choose j}*{({1+\sqrt 5\over2})^{i(k-j)}*[-({1-\sqrt 5\over2})^i}]^j（二项式展开）

=(15)k∑i=1n∑j=0k(kj)∗(−1)j∗(1+52)i(k−j)∗(1−52)ij=({1\over \sqrt 5})^k\sum^n_{i=1}\sum^k_{j=0}{k\choose j}*(-1)^j*{({1+\sqrt 5\over2})^{i(k-j)}*({1-\sqrt 5\over2})^{ij}}

=(15)k∑j=0k(kj)∗(−1)j∗∑i=1n(1+52)i(k−j)∗(1−52)ij=({1\over \sqrt 5})^k\sum^k_{j=0}{k\choose j}*(-1)^j*\sum^n_{i=1}{({1+\sqrt 5\over2})^{i(k-j)}*({1-\sqrt 5\over2})^{ij}}

前面的还是一个k，后面这个是一个等差数列，等差数列求和就可以了（注意q=1的情况）总复杂度O(k2)O(k^2)

还有就是5没有二次剩余，所以需要扩域，类似复数的做法把数设设成a+b∗5a+b*\sqrt5的形式再定义一下运算即可，注意fib是整数那么G一定也是的。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int _=1e2;
const int maxK=210;
const int mod=1e9+7;
inline int ad(int x,int y){return x>=mod-y?x-mod+y:x+y;}
inline int re(int x,int y){return x<y?x-y+mod:x-y;}
inline int mu(int x,int y){return (LL)x*y%mod;}
inline int qp(int x,int y){int r=1;while(y){if(y&1)r=mu(r,x);x=mu(x,x),y>>=1;}return r;}
inline int iv(int x){return qp(x,mod-2);}
inline int dv(int x,int y){return mu(x,iv(y));}
struct complex
{
	int a,b;
	complex(){};complex(int A,int B){a=A,b=B;}
	friend complex operator +(complex x,complex y){return complex(ad(x.a,y.a),ad(x.b,y.b));}
	friend complex operator -(complex x,complex y){return complex(re(x.a,y.a),re(x.b,y.b));}
	friend complex operator *(complex x,complex y){return complex( ad(mu(x.a,y.a),mu(5,mu(x.b,y.b))) , ad(mu(x.a,y.b),mu(x.b,y.a)) );}
	friend complex operator ^(complex x,LL p){complex r=complex(1,0);while(p){if(p&1)r=r*x;x=x*x;p>>=1;}return r;}
	friend bool operator ==(complex x,complex y){return x.a==y.a&&x.b==y.b;}
};
 
int S1[maxK][maxK],fac[maxK],fac_inv[maxK];
int C(int n,int m){return mu(fac[n],mu(fac_inv[m],fac_inv[n-m]));}
void yu()
{
	fac[0]=1;for(int i=1;i<maxK;i++)fac[i]=mu(fac[i-1],i);
	fac_inv[maxK-1]=iv(fac[maxK-1]);
	for(int i=maxK-2;i>=0;i--)fac_inv[i]=mu(fac_inv[i+1],i+1);
	S1[0][0]=1;
	for(int i=1;i<maxK;i++)
		for(int j=1;j<=i;j++)
			S1[i][j]=ad(S1[i-1][j-1],mu(S1[i-1][j],(i-1)));
}
int fib[maxK];
int getsum(LL n,int k)
{
/*	int ret=1;fib[1]=1;
	for(int i=2;i<=n;i++)fib[i]=ad(fib[i-1],fib[i-2]),ret=ad(ret,qp(fib[i],k));
	printf("%d\n",ret);
	return ret;*/
 
	complex ret=complex(0,0),q,u,d,t;
	for(int j=0;j<=k;j++)
	{
		q=(complex(fac_inv[2],fac_inv[2])^(k-j))*(complex(fac_inv[2],re(0,fac_inv[2]))^j);
		
		if(q==complex(1,0))q=complex(n%mod,0);
		else
		{
			u=(q^n)-complex(1,0),d=q-complex(1,0);
			
			t=d,t.b=re(0,t.b);
			u=u*t,d=d*t;
			
			q=q*u*complex(iv(d.a),0);
		}
		
		if(j&1)ret=ret-q*complex(C(k,j),0);
		else ret=ret+q*complex(C(k,j),0);
	}
	ret=ret*(complex(0,dv(1,5))^k);
	if(ret.b)puts("error");
	return ret.a;
}
int calc(LL n,int k)
{
	int ret=0;
	for(int j=1;j<=k;j++)
	{
		if((k-j)&1)ret=re(ret,mu(S1[k][j],getsum(n,j)));
		else ret=ad(ret,mu(S1[k][j],getsum(n,j)));
	}
	return mu(ret,fac_inv[k]);
}
int main()
{
	int K;LL l,r;
	scanf("%d%lld%lld",&K,&l,&r);yu();
	printf("%d\n",re(calc(r+2,K),calc(l+1,K)));
 
	return 0;
}
I. Cowboy Beblop at his computer 几何题待填

上一篇： urllib库（二）parse模块：urlparse()/urlsplit()，parse_qs()/parse_qsl()，urlunparse()/urlunsplit()

下一篇： SQL必知必会 第一篇

推荐阅读