这道题十分坑爹，上面一大堆没用的废话，还没分背景！让我差点漏了关键的模数：“神的电话”。
题目大意给出两个正整数n,m。
求出所有满足条件的序列的个数
设A为序列，则
1：对于任意一对i, j，A[i] mod m !=A[j] mod m
2： ∑|A|i=1A[i]=n
简单的来说就是整个数列的和为n，所有数mod m各不相同
对于 20% 的数据 ，n≤20，m≤5。
对于 40%的数据 ，n≤300，m≤10。
对于 70 %的数据， n≤10^18，m≤20。
对于 100% 的数据， n≤10^18，m≤100。
40分肯定很容易拿啦，DP，设F[i,j,s]表示序列长度为i，和为j，数列mod m结果的情况（S为二进制）的方案数，答案就是 ∑F[i,n,s]∗（i的全排列） 。
一定要记得mod 那个神的电话号码再看70%以上的数据，n就变成10^18 了，很明显，上面dp的不足就是j它是会达到N的，严重超时，有没有办法把 j 转化得更小呢？
我们发现，可以把 j 的表示换一换，代表所有数分别mod m再加起来的和，
这下子，有效的j就不止一个了，所有(n-j) mod m=0的j都是合法的。而j 最大也就是1..m的和，即最大5050，做完之后只用再算出 (n-j)/m 个m的分配方案，即考虑给每个数加几个m的方案，乘起来，就能还原原来的样子了（因为一个数 mod m就等于删去若干个m嘛）。
可是这样还是不行，还得继续优化。我们看到40分dp的 s， 明显他已经不需要了，因为我们这个时候只用枚举取0..m-1 这些数，用01背包的思路，弄好取的顺序，就不怕取重了。
这时，dp的时间复杂度降为O( m4 )，枚举状态O( m3 )，转移O(m)
dp考虑完了，再来考虑分配m的问题。
我们现在有 (n-1)/m个m，要分配给i个数，求方案数。
这就转化为另一个问题了，记cnt=(n-1)/m 我们可以理解为：有 cnt个棒子，有i-1个挡板，把棒子分成i堆，求组合数。
这下简单了，这个问题可以简单理解为：有cnt+i-1个数（把棒子和挡板当作同一类的东西），从中选i-1个，求组合数。很显然，就是求 Ci−1cnt+i−1 。这个O(i)就能求出来了。所有问题完全解决（至于c在模意义下怎么求，自己百度去，总之要用到逆元与费马小定理【这个我想了很久，因为忘了···】）
综合起来，就是先做一次DP，再用每个满足(n-j) mod m=0的F[i,j]（这是组合的个数），乘以i的全排列（i的阶乘），再乘以 Ci−1cnt+i−1 (cnt=(n-1)/m)，得出ans[i,j]，最后加起来就OK了。
一定要记得mod 那个神的电话号码（很重要说三遍）呵呵哒，写完了。其实这道题打起来十分快，但是想要想比较久，主要还是dp后面的部分比较烦，做比赛时，一开始没有想好就开始乱搞了，错了挺多次，搞的为了满分打了2个多钟头···
下面贴出代码（别看dp，是水的，O( m5 )，其他都是正常的） const mo=905229641; //这是电话号码，大家打一下试试，看看会不会空号，但记得加日本区号，^_^var m,mx,i,j,k,l,yu:longint; n,dur,ans,xl,xd:int64; ny,pre:Array[0..101]of int64; f:array[0..101,0..5050,0..101]of longint; function ksm(x,y:int64):int64; begin if y=0 then exit(1); if y=1 then exit(x); ksm:=ksm(x,y div 2); ksm:=ksm*ksm mod mo; exit(ksm*ksm(x,y mod 2)mod mo); end; function c(x,y:int64):int64; begin c:=1; xl:=y; while xl>y-x do begin c:=c*xl mod mo; xl:=xl-1; end; for l:=2 to x do c:=c*ny[l] mod mo; exit(c); end;begin assign(input,'alpha.in');reset(input); assign(output,'alpha.out');rewrite(output); readln(n,m); f[0,0,m]:=1; mx:=(m+1)*m div 2; for i:=0 to m-1 do for j:=0 to mx do for k:=m-i downto 1 do if f[i,j,k]>0 then for l:=k-1 downto 0 do f[i+1,j+l,l]:=(f[i+1,j+l,l]+f[i,j,k])mod mo; for i:=1 to m+1 do ny[i]:=ksm(i,mo-2); yu:=n mod m; pre[1]:=1; for i:=2 to m do pre[i]:=pre[i-1]*i mod mo; for i:=1 to m do begin j:=yu; while (j<=n)and(j<=mx) do begin dur:=0; for k:=m-i downto 0 do dur:=(dur+f[i,j,k])mod mo; dur:=dur*pre[i]mod mo; xd:=(n-j)div m mod mo; dur:=dur*c(i-1,xd+i-1)mod mo; ans:=(ans+dur)mod mo; j:=j+m; end; end; writeln(ans);end.